应用一. O(1)时间检测2的幂次
题目：
用 O(1) 时间检测整数 n 是否是 2 的幂次。
样例：
n=4，返回 true;
n=5，返回 false.
挑战：
O(1) time
思路：
x & (x - 1) 用于消去x最后一位的1, 比如x = 12, 那么在二进制下就是(1100)2
x = 1100
x - 1 = 1011
x & (x - 1) = 1000
代码：
public class Solution {
/*
* @param n: An integer
* @return: True or false
*/
public boolean checkPowerOf2(int n) {
return n > 0 && (n & n - 1) == 0;
}
}
应用二. 二进制中有多少个1：
题目：
计算在一个 32 位的整数的二进制表示中有多少个 1.
样例：
给定 32 (100000)，返回 1
给定 5 (101)，返回 2
给定 1023 (1111111111)，返回 10
挑战：
If the integer is n bits with m 1 bits. Can you do it in O(m) time?
思路：
由x & (x - 1)消去x最后一位的1可知。不断使用 x & (x - 1) 消去x最后一位的1，
计算总共消去了多少次即可。
代码：
public class Solution {
/*
* @param num: An integer
* @return: An integer
*/
public int countOnes(int num) {
int count = 0;
while (num != 0) {
num = num & (num - 1);
count++;
}
return count;
}
}
应用三. 将整数A转换为B
题目：
如果要将整数A转换为B，需要改变多少个bit位？
注意事项：
Both n and m are 32-bit integers.
样例：
如把31转换为14，需要改变2个bit位。
(31)10=(11111)2
(14)10=(01110)2
思路：
将整数A转换为B，如果A和B在第i（0 <=i < 32）个位上相等，则不需要改变这个BIT位，
如果在第i位上不相等，则需要改变这个BIT位。
所以问题转化为了A和B有多少个BIT位不相同！
联想到位运算有一个异或操作，相同为0，相异为1，
所以问题转变成了计算A异或B之后这个数中1的个数!
代码：
public class Solution {
/*
* @param a: An integer
* @param b: An integer
* @return: An integer
*/
public int bitSwapRequired(int a, int b) {
return countOnes(a ^ b);
}
public int countOnes(int num) {
int count = 0;
while (num != 0) {
num = num & (num - 1);
count++;
}
return count;
}
}
