1、特殊数字的16进制与二级制对应关系

1. 0xaaaaaaaa = 10101010101010101010101010101010(偶数位为1，奇数位为0）
2. 0x55555555 = 1010101010101010101010101010101 (偶数位为0，奇数位为1）
3. 0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)
4. 0xcccccccc  = 11001100110011001100110011001100 (0和1每隔两位交替出现)
5. 0x0f0f0f0f    = 00001111000011110000111100001111 (1和0每隔四位交替出现)
6. 0xf0f0f0f0    = 11110000111100001111000011110000 (0和1每隔四位交替出现)

利用上述具有特殊二进制的整数，可以很方便进行位操作，而且该整数的十六进制形式比较好记，也不用写那么多的0，1。

2、二进制运算

2.1 求余运算

取余操作中如果除数是2的幂次方则等价于其除数减一的与操作 也就是说hash % length == hash & (length - 1)的前提是length 是 2的n次方，并且采用二进制位操作&，相对于%能够提高运算效率，这就解释了hashmap的长度为什么是2的幂次方。

• 普通的求余运算为:  n % m，优化之后为n & (m - 1)。

/**
 * 求模运算
 * 求一个数n模m的值，也就是求n除以m之后的余数，这里m为2的幂次方。
 * 普通的求余运算为:  n % m
 * 优化之后为:  n & (m - 1)
 * 
 * @param n 被除数
 * @param m 除数
 * @return
 */
public static int getMod(int n, int m) {
	return n & (m-1);
}

2.2 计算给定数字的二进制表示中1出现的个数

Count the number of ones in the binary representation of the given number（计算给定数字的二进制表示中1出现的个数）。

算法1： 每次n&(n-1)操作都是将n最末尾的1反转为0，因此反转个数即为1的个数

public static int count_one(int n) {
    int count = 0;
    while (n > 0) {
        // n&(n-1)作用是消除最低位的1，如二级制 111010&111001=111000
        n = n & (n - 1);
        count++;
    }
    return count;
}

算法2： 给定数字与1按位与，如果数字的最后一位为1，则结果为1，每次计算后将数字右移一位，循环计算，直到数字为0。

public static int count_one2(int n) {
    int count = 0;
    while (n > 0) {
        if ((n & 1) == 1) {
            count++;
        }
        n >>= 1;
    }
    return count;
}

算法3： java API中的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.3 将数字n的第bit位 置1

public static int resetBit_1(int n, int bit) {
    return n |= 1 << bit;
}

2.4 将数字n的第bit位 置0

public static int resetBit_0(int n, int bit) {
    return n &= ~(1 << bit);
}

2.5 数字n的第bit位是否为0

public static boolean isBit0(int n, int bit) {
    return (n & (1 << bit)) != 0;
}

2.6 删除从右边起第一个为1的bit（将该位的1置为0）

public static int resetLowBit1To0(int n) {
    return n & (n - 1);
}

2.7 判断一个数是否是2的幂次方

判断一个数是否是2的幂次方，这个数用二进制数表示时，只有一位为1

public static boolean isPower(int n) {
    if ((n & (n - 1)) == 0)
        return true;
    else
        return false;
}

2.8 判断一个数是否是4的幂次方

判断一个数是否是4的幂次方。这个数用二进制数表示时，只有一位为1并且只可能出现在偶数位置。

/**
 * 判断一个数是否是4的幂次方 这个数用二进制数表示时，只有一位为1并且只可能出现在偶数位置
 * 
 * 0x55555555是16进制，2进制是1010101010101010101010101010101
 * 
 * 式子左边的是判断n是否为2的幂次方，因为4的幂次方一定是2的幂次方，如果2的幂次方都不是，
 * 那就一定不是2的四次方了。第二个条件就是0x55555555，5的二进制位0101，又因为该数与n进行与运算，
 * 因此，也就是奇数位全部为与0进行与——置0，偶数位全部与1进行与——保留原本比特位。
 * 
 * @param n
 * @return
 */
public static boolean isPowerOfFour(int n) {
    return ((n & (n - 1)) == 0) && ((n & 0x55555555) != 0);
}

2.9 计算2个数的和，递归方法

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

2.10 计算2个数的差，递归方法

public static int getSubstract(int a, int b) {
    return b == 0 ? a : getSubstract(a ^ b, (~a & b) << 1);
}

2.11 计算2个数的和，循环方法

让我们以2+3为例来看一下： 0010（2），0011（3），首先看最右边的第一位，0+1为1，不进位，接着1+1=2，要进位。我们如何判断相加的两个bit只有一个1？答案是使用异或操作。 我们如何判断相加的两个bit为两个1？答案是使用与操作。因此 a&b的结果使得所有该进位的位置为1，a^b的结果使得所有该进位的位置0，不该进位的位置为其应该有的数。在进行初步的计算之后，我们需要把该进位的位置加上，因此进位之后，是在其前面的bit位加1，因此，需要将b左移1位，然后与初步计算结果相加，也就是我们递归方法的核心。

• 说说为什么最后b会变成0： 首先，carry <<1一定会使得carry中多一个0，因为左移之后最右边的位置一定为0，但是其前面可能舍弃了一个1，因此carry<<1使得carry的bit位的0的个数逐渐增加。其次，carry = a & b 这个使得b中的0得以保存，因为0 & 任何数都为0 因此，这两个条件使得最后b一定为0.同理，两个数相减也是一样的道理。首先a^b得到bit位上位数相同的位置全部为0，不同的位置为1，因为0-0=0，1-1=0；其次，_{a&b得到需要借位的bit位，因此只有0-1需要借位，1-0不需要借位，因此}a & b刚好符合。

public static int getSum(int a, int b) {
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }
    int carry = 0;
    while (b != 0) {
        // If both bits are 1, we set the bit to the left (<<1) to 1 -- this is the
        // carry step
        carry = (a & b) << 1;
        // If both bits are 1, this will give us 0 (we will have a carry from the step
        // above)
        // If only 1 bit is 1, this will give us 1 (there is nothing to carry)
        a = a ^ b;
        b = carry;
    }

    return a;
}

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

一个正常数组包括0,1,2,3,4,5…n-1，但是现在这个数组中少了一个数，求这个数是多少？例如：[0,1,3]输出结果为2。

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

2.13 找到最高的一位数

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

2.14 反转二进制位

/**
 * 反转二进制位 翻转的顺序表示：abcdefgh -> efghabcd -> ghefcdab -> hgfedcba
 * 
 * @param n
 * @return
 */
public static int reverseBit(int n) {
	n = (n >> 16) | (n << 16);
	n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
	n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
	n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
	n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
	return n;
}
/**
 * 反转二进制位
 * 
 * 该解法的主要思路是：一个32位的mask，并且其32位中只有一个位为1，开始时，使其置1位位于最左端，
 * 并依次向最右移动，同时，从最右端开始检测n，如果n的对应位为1，则将结果或上mask。
 * 
 * @param n
 * @return
 */
public static int reverseBits(int n) {
	int mask = 1 << 31, res = 0;
	for (int i = 0; i < 32; ++i) {
		if ((n & 1) != 0)
			res |= mask;
		mask >>= 1;
		n >>= 1;
	}
	return res;
}

2.15 找到从右边起，第一个为1的位，其余位置0

找到从右边起，第一个为1的位，其余位置0（注：主要利用补码 = 反码 + 1）

public static int getFirstOneFromRight(int n) {
    return n &= (-n);
}

2.16 范围[m,n]之间所有数字与的结果

多个数字相与，只要其中有一个数字为0，结果就是0，而且，我们知道在数字递增的过程中，低位的数字总是在不断地变化，因此，我们只需要找到m与n相同的高位数字就行。例如,5,6,7的二进制分别为：101       110       111，全部一样的部分为第三位，都为1，因此最后输出的结果为4。

public static int rangeBitwiseAnd(int m, int n) {
    int i = 0;
    while (m != n) {
        m >>= 1;
        n >>= 1;
        ++i;
    }
    return (m << i);
}