算法小结--Bit Manipulation解法

0. 常用代码
1.Integer.bitCount(n)
2.String运算 ： sum%2（得到不是0就是1）carry = sum/2 来加新的bit 例子
3.2^h ==> (int)Math.pow(2,h) or (2>>(h-1))or(1>>h)//shift is after '-','+'

1. 基本操作
http://stackoverflow.com/questions/6385792/what-does-a-bitwise-shift-left-or-right-do-and-what-is-it-used-for
不和++一样，需要assign c = c>>1
1&0 =0
1 | 0 = 1
XOR // find the different bit
1^0 = 1; 1^1 = 0; 0^0= 0; x^x = 0; x^0=x
shift (for signed)
2>>1 = 1 ; 1>>2 =0
(0010)
 2<<2 = 8
//preserve the first bit

1100 1100 >> 1
1110 0110 

 unsigned operation >>>(convert non number to number)
//not perserve the first bit

1100 1100 >>> 1
0110 0110 

negative number 2's compliement

1111 is -1, in two's complement

1110 is -2, which is ~2 + 1, ~0010 => 1101, 1101 + 1 = 1110 => 2

1101 is -3, which is ~3 + 1

so if you want to get a negative number, you can simply do ~x + 1

~Not
~2(0010) is  -3(1101)

---

Ex：
» 461. Hamming Distance F家
# of different bits in x,y
 return Integer.bitCount(x^y);

1.number of 1 bits
https://leetcode.com/problems/number-of-1-bits/

     while(n>0){
            ones += (n&1);
            n = n>>1;
        }

2.Find the difference
https://leetcode.com/problems/find-the-difference/

方法1： 顺序打乱，但是char的ascill总和不变 ，相减得到新加的letter
方法2： 建一个char c=0；两次loop 不停xor当前letter of string,return c

3. Add sum
https://leetcode.com/problems/sum-of-two-integers/
https://discuss.leetcode.com/topic/49771/java-simple-easy-understand-solution-with-explanation/2

while(b!=0) {
    int carry = a &b; //1.find the carry要进位
    a = a^b; //2. find different bit
    b  = carry<<1; // 3. left shift
}

//get subtract a-b
while( b ! = 0){
    int borrow =  (~a)&b;
    a = a^b;
    b = borrow<<1;
}

4.power of two （F，G家）
详解

http://rainykat.blogspot.com/2016/12/leetcodefg-power-of-two.html