位运算（Bit manipulation）

1.计算二进制数中1的个数

1.1 判断最低位是否为1

int bitCount(int i){
    int count=0;
    while(i>0){
        if(i&1==1)
            count++;
        i>>=1;
    }
    return count;
 }

1.2 清除最低位的1

int bitCount(int i){
    int count=0;
    while(i>0){
        i=i&(i-1);
        count++;
    }
    return count;
}

1.3 java中的Integer.bitCount,将相邻位的1相加，存储1的个数，五次就可以加完整个32位数

public static int bitCount(int i) {
         // HD, Figure 5-2
         i = i - ((i >>> 1) & 0x55555555);
         i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
         i = (i + (i >>> 4)) & 0x0f0f0f0f;
         i = i + (i >>> 8);
         i = i + (i >>> 16);
         return i & 0x3f;
 }

2.是否是4的次方

用二进制数表示时，只有一位为1并且只可能出现在偶数位置

boolean isPowerOfFour(int n) {
         return (n&(n-1))==0&&(n&0x55555555)!=0;
     }

3. 异或运算符号

3.1 计算两个数的和

int getSum(int a, int b) {
     return b==0? a:getSum(a^b, (a&b)<<1); 
 }

3.2 找到丢失的数字,与相同的数异或两次后为0

int missingNumber(int[] nums) {
         int ret = 0;
         for(int i = 0; i < nums.length; ++i) {
             ret ^= i;
             ret ^= nums[i];
         }
         return ret^=nums.length;
     }

4. 或运算符号

4.1 找到最高的一位数

int higestOneBit(int i) {
         i|=i>>1;
         i|=i>>2;
         i|=i>>4;
         i|=i>>8;
         i|=i>>16;
         return (i+1)>>1;
     }

4.2 反转

int reverseBit(int i) {
         int mask=1<<31,res=0;
         for(int k=0;k<32;k++) {
             if((i&1)!=0) res|=mask;
             mask>>=1;
             i>>=1;
         }
         return res;
     }