Bit Manipulation

消去二进制中最右侧的那个“1”

x & (x - 1) // 消去 x 最后一位的 1，比如 x = 12，那么在二进制下就是 (1100)2

x           = 1100
x - 1       = 1011
x & (x - 1) = 1000

LintCode: 142. O(1) Check Power of 2

Using O(1) time to check whether an integer n is a power of 2.

满足要求的N有两个条件：

1. N > 0

2. N 的二进制表示有且只有一个1

所以用“技巧一”可以写出如下Java代码

Check_Power_of_2

public class Solution {
    /**
     * @param n: An integer
     * @return: True or false
     */
    public boolean checkPowerOf2(int n) {
        // write your code here
        return (n > 0) && ((n & (n - 1)) == 0);
    }
}

LintCode: 365. Count 1 in Binary

Count how many 1 in binary representation of a 32-bit integer.

上一道题目的变体咯，既然要看有多少个1，那我就一直算下去，直到它变成0

Count_1_in_Binary

public class Solution {
    /*
     * @param num: An integer
     * @return: An integer
     */
    public int countOnes(int num) {
        // write your code here
        int count = 0;
        while (num != 0) {
            num = num & (num - 1);
            count++;
        }
        return count;
    }
};

LintCode: 181. Flip Bits

Determine the number of bits required to flip if you want to convert integer n to integer m.

Solution 1

Flip_Bits

public class Solution {
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: An integer
     */
    public int bitSwapRequired(int a, int b) {
        // write your code here
        String bit = Integer.toBinaryString(a ^ b);
        int num = 0;
        for (int i = 0; i < bit.length(); i++) {
            num += (bit.charAt(i) - '0');
        }
        return num;
    }
}

Solution 2

class Solution {
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    public int countOnes(int num) {
        int count = 0;
        while (num != 0) {
            num = num & (num - 1);
            count++;
        }
        return count;
    }

    public int bitSwapRequired(int a, int b) {
        // write your code here
        return countOnes(a ^ b);
    }
};

Solution 3

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

class Solution {
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    public static int bitSwapRequired(int a, int b) {
        // write your code here
        int count = 0;  
        for (int c = a ^ b; c != 0; c = c >>> 1) {
            count += c & 1;
        }
        return count;
    }
};

巧用异或XOR运算

a ^ b ^ b = a  // 对一个数异或两次等价于没有任何操作

LintCode: 82. Single Number

Given 2*n + 1 numbers, every numbers occurs twice except one, find it.

XOR Operator

• O(n) Time

• O(1) Space

Single_Number

public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int singleNumber(int[] A) {
        // write your code here
        int result = 0, n = A.length;
        for (int i = 0; i < n; i++) {
            result ^= A[i];
        }
        return result;
    }
}

Python collections.Counter()

• O(n) Time at least

• O(n) Space

Single_Number

class Solution:
    """
    @param A: An integer array
    @return: An integer
    """
    def singleNumber(self, A):
        # write your code here
        dict = collections.Counter(A)
        for key in dict:
            if dict[key] == 1:
                return key

将两个数不同的位设置为“1”，其余为“0”

int bitFlag = (AXORB & (~ (AXORB - 1)));

这一行代码的作用是：找到数字 A 和数字 B 中不相同的一位，并将该位设置为 1，其他位设置为 0； 根据 XOR 的定义，我们知道，在 AXORB 中，为 1 的位即 A 和 B 不相同的位，AXORB 中为 0 的位即 A 和 B 中相同的位 所以，要找到 A 和 B 中不相同的位，只需要找到在 AXORB 中从右往左第一个为 1 的位，保留该位并将其他位置为 0 即可。

LeetCode: 260. Single Number III

public class Solution {
    public int[] singleNumber(int[] nums) {
        int AXORB = 0;
        for (int num : nums) {
            AXORB ^= num; 
        }
        // pick one bit as flag
        int bitFlag = (AXORB & (~ (AXORB - 1)));
        int[] res = new int[2];
        for (int num : nums) {
            if ((num & bitFlag) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }
}

假设数组中两个不同的数字为 A 和 B；

1. 通过遍历整个数组并求整个数组所有数字之间的 XOR，根据 XOR 的特性可以得到最终的结果为 AXORB = A XOR B；

2. 通过某种特定的方式，我们可以通过 AXORB 得到在数字 A 和数字 B 的二进制下某一位不相同的位；因为A 和 B 是不相同的，所以他们的二进制数字有且至少有一位是不相同的。我们将这一位设置为 1，并将所有的其他位设置为 0，我们假设我们得到的这个数字为 bitFlag；

3. 那么现在，我们很容易知道，数字 A 和 数字 B 中必然有一个数字与上 bitFlag 为 0；因为bitFlag 标志了数字 A 和数字 B 中的某一位不同，那么在数字 A 和 B 中的这一位必然是一个为 0，另一个为 1；而我们在 bitFlag 中将其他位都设置为 0，那么该位为 0 的数字与上 bitFlag 就等于 0，而该位为 1 的数字与上 bitFlag 就等于 bitFlag

4. 现在问题就简单了，我们只需要在循环一次数组，将与上 bitFlag 为 0 的数字进行 XOR 运算，与上 bitFlag 不为 0 的数组进行独立的 XOR 运算。那么最后我们得到的这两个数字就是 A 和 B。