Home

Matrix

1. Use formula (i, j) => (j, n - 1 - i) to rotate a n*n matrix 90 degrees clockwise.

   • [Problem 10855] (http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1796)

   • [Sample code here] (https://gist.github.com/alcedo/6334323#file-javasnippets-java)

2. Use formulae (i,j) => (j, r - i) to rotate a r*c (non-square) matrix 90degress clockwise. **Draw on a piece of paper to derive the above r/s yourself. **

Binary numbers

1's Complement

1. Java uses 2's complement as their internal representation

2. 1's Complement has the following properties:

   • MSB signify the sign in use. eg: (11110) MSB => 1, which implies this is -ve number
   • 011 -> Largest +ve number for a 3 bit number (MSB = 0, all other bits are 1)
   • 100 -> Smallest -ve number for a 3 bit number (negate the +ve number)
   • To convert from -ve to +ve number, simply invert all the bits. Vice versa
   • 111 -> -0
   • 000 -> +0 (yes, 1's complement has 2 ways to represent 0)

Examples:

* 001 //1 
* 110 //-1
* 110 + 1 // 111 (-ve 0)
* 001 - 1 // 000 (+ve 0)

Addition:

• Align the values on the LSB and add, propagating any carry to the bit one position left.
• When the carry extends past the end of the word it is said to have "wrapped around", a condition called an "end-around carry". When this occurs, the bit must be added back in at the LSB. This phenomenon does not occur in two's complement arithmetic.

Eg: ADD -1 + 2 :

 110
  10 (+)
1000 (ANS)

Shift MSB to LSB, hence we have final answer to be 001 (001 = +1)

Subtraction:

subtraction can be done by negating the number that is to be subtracted, and adding them up.

So 1 - 2 == (001 - 010) == (001 + 101) == (110) == -ve

2's Complement

• A 2's complement +ve number is == 1's complement +ve number

• To Convert from 1's complement -ve number to 2's complement, simply add 1 to the number (this is kind of like doing a wrap around in advance)

  • Eg: for 1's complement, -3 (100), converting it to 2's complement by adding 1: 100 + 1 => 101

  • System.out.println(Integer.toBinaryString( -2 ) + " " + -2); // -2

  • System.out.println(Integer.toBinaryString( ~2 +1 ) + " " + (~2 + 1)); // -2 (~2 returns 1's complement. we then +1 to turn it to a -ve 2's complement number )

• Subtraction is done, simply by adding the 2 numbers up. ie: 1-3 == 1 + -3 == (001 + 101) == 110

• IF The left two carry bits after addition (the ones on the far left of the top row in these examples) are both 1s or both 0s, the result is valid; If the left two carry bits are "1 0" or "0 1", a sign overflow has occurred.

• Convert a -ve 2's complement to a -ve 1's complement by inverting the number, add 1, and negate it again. eg: 2's Comp -2 (110) == (001 + 1) == (010) == 1's Comp (101)