Bit Operation

Algorithm

---

Bit Operation

1. Basic Operation

1.1

    x ^ 0s = x      x & 0s = 0      x | 0s = x
  **x ^ 1s = ~x        x & 1s = x      x | 1s = 1s
    x ^ x = 0       x & x = x       x | x = x

1.2 Tell Odd/Even: check the last bit

if(a&1)==0

1.3 Exchange two number without the temporary variable

• 第一步 a^=b 即a=(a^b);
• 第二步 b^=a 即b=b^(a^b)，由于^运算满足交换律，b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。
• 第三步 a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值。

    if(a!=b):
        a^=b;  // a = (a^b)
        b^=a;  // b = b^(a^b)
        a^=b;  // a = (a^b)^a

1.4 Change sign

如对于-11和11，可以通过下面的变换方法将-11变成11
- 1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制)
同样可以这样的将11变成-11
- 0000 1011(二进制) –取反-> 0000 0100(二进制) –加1-> 1111 0101(二进制)

       ~a + 1

1.5 Get Absolute Value

(2)对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。

    (1)
    int i = a >> 31;
    return i == 0 ? a : (~a + 1);
    OR
    (2)
    int i = a >> 31;  
    return ((a ^ i) - i);  

1.6

去掉最后一位(101101->10110)	x>>1
在最后加一个0(101101->1011010)	x<<1
在最后加一个1(101101->1011011)	(x<<1)+1
把最后一位变成1(101100->101101)	x
把最后一位变成0(101101->101100)	(x
最后一位取反(101101->101100)	x ^ 1
右数第k位取反(101101->101001,k=3)	x ^ (1 << (k-1))
取末三位(1101101->101)	x & 7
取末k位(1101101->1101,k=5)	x & ((1 << k)-1)
把末k位变成1(101001->101111,k=4)	x
末k位取反(101001->100110,k=4)	x ^ ((1 << k)-1)
把右边连续的1变成0(100101111->100100000)	x & (x+1)
把右起第一个0变成1(100101111->100111111)	x
把右边连续的0变成1(11011000->11011111)	x or (x-1)
取右边连续的1(100101111->1111)	(x^(x+1)) >> 1
去掉右起第一个1的左边(100101000->1000,树状数组)	x & (x ^ (x-1))

2. Adavanced Questions:

2.1 Signle Number (LeetCode)

(1) Given an array of integers, every element appears twice except for one. Find that single one.

    int singleNumber(int[] A) {
        if(A==null || A.length==0)  
        return 0;  
        int res = A[0];  
        for(int i=1;i<A.length;i++)  
        {  
            res ^= A[i];  // 通过异或！！ 出现俩次后变为零
        }  
        return res; 
    }

(2) Given an array of integers, every element appears three times except for one. Find that single one.

    public int singleNumber(int[] A) {
        int ones = 0, twos = 0;
        for(int i = 0; i < A.length; i++){
            ones = (ones ^ A[i]) & ~twos;
            twos = (twos ^ A[i]) & ~ones;
        }
        return ones;
    }

2.2 Subsets: Given a set of distinct integers, S, return all possible subs

    public List<List<Integer>> subsets(int[] S) {
            List<List<Integer>> results = new ArrayList<List<Integer>>();
            Arrays.sort(S);
            for (int i=0;i<1<<S.length;i++){ // 1<<S.length 可写成 pow(2,S.length)
            // 假设原集合有n个元素，那么原集合的子集合的个数是2的n次方，记为2 ^ n。
            // 对应着从0~2 ^ n - 1这2 ^ n个数。这2 ^ n个数如果用二进制表示，可以发现一共有n位。
            // 每位要么取0，要么取1。如果第i位取0，则说明元集合的第i个元素不出现在当前新生成的子集合中，
            // 反之，如果第i位取1，则说明元集合的第i个元素出现在当前新生成的子集合中。
                List<Integer> result =  new ArrayList<Integer>();
                for(int j=0;j<S.length;j++){ 
                // 让数组元素 匹配上 在i的bit位置
                    if ((i&(1<<j))!=0) result.add(S[j]);
                }
                results.add(result);
            }
            return results;
    }

3 Gray Code:

    private int binaryToGray(int num){ 
        // num is kind of index in gray sequence
        // return the gray code in that sequence
        return (num>>1)^num;
    }
    public static List<Integer> grayCode(int n) {
        List<Integer> li = new ArrayList<Integer>();
        for (int i = 0; i < Math.pow(2, n); i++) {
            li.add((i>>1)^i);
        }
        return li;
    }