最近在反思工作第四年的深度，故而写此系列。
其他Java系列文章：

• ​​Java学习之编译、反编译以及字节码入门​​
• ​​Java学习之String​​
• ​​Java学习之JDK9新特性​​

位操作，简单确强大，有一两拨千金奇效；可是平时工作中用得真心不多，故此文章也有备份回顾之意。
在计算机中所有数据都是以二进制的形式储存的。位运算其实就是直接对在内存中的二进制数据进行操作，因此处理数据的速度非常快。

基础概念

进制：位操作是基于二进制；
位运算符，有与、或、异或、取反、左移、右移这6种，只有​​​~​​取反是单目操作符，其它都是双目操作符。注意运算符的优先级。

位操作复合操作符：&=、|=、 ^=、<<=、>>=；
位操作只能用于整形数据；

原码、反码、补码

反码：符号位不变，数值位分别"按位取反"；
补码：符号位不变，数值位分别"按位取反"，再+1，即反码+1；

已知补码求原码：符号位不变，数值位按位取反,末位再加1，即补码的补码等于原码；

二进制应用

交换两数

先给出代码：

int c = 1, d = 2;
c ^= d;
d ^= c;
c ^= d;
System.out.println("c=" + c + "d=" + d);

简单分析：

c = c ^ d;
d = d ^ c = d ^ c ^ d = c;
c = c ^ d = c ^ d ^ c = d;

判断奇偶

根据最未位来决定，为0就是偶数，为1就是奇数：
​​​if ((a & 1) == 0)​​​代替​​if (a % 2 == 0)​​来判断a是不是偶数。

二进制中1的个数

很经典的面试题：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

分析：如果一个整数不为0，则此数至少有一位是1。如果把这个整数减1，那原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1（如果最右边的1后面还有0的话），其余所有位将不会受到影响。

举例：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成1，而前面的1保持不变，因此得到的结果是1011。发现减1的结果是把最右边的一个1开始的所有位都取反。此时如果再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。即​​1100&1011=1000​​，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

public static int getNum(int input) {
    int res = 0;
    while(input != 0) {
        res += 1;
        input = input & (input- 1);
    }
    return res;
}

变换符号

变换符号（学术一点的说法，求补码）就是正数变成负数，负数变成正数。根据高中（亦或是大学）知识，补码=源码的反码 + 1：​​~a + 1;​​

2的n次幂

2的n次幂，是一个极其特殊的等比数列，在算法题中使用这个特性，有时候会有奇效；

// 初始化，可以是任意有效值
int val = 111;
//  计算2的n次方
int result1 = 2 << (n - 1);


// 判断一个数是否为2的幂次方，是的话，二进制表示时其最高位为1，其余位为0，&一定是0；(val & -val)就是获取最右1的位
int result1 = (val & (val - 1)) == 0;
int result2 = (val & -val) == val;
// 判断一个无符号数是2的n次方-1
int result3 = (val & (val + 1)) == 0;

筛素数法

筛素数法，百度百科定义：是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。
筛选思路：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。
算法：埃拉托斯特尼筛法、欧拉筛法；不同算法的时间复杂度不同，空间复杂度也不尽相同。
实际上，我们可以使用位操作来实现，使用素数表进行优化来减小其空间占用。

// 打印100以内素数
int max = 100;
// 用bool数组来作标记的，bool型数据占1个字节（8位）
boolean[] flags = new boolean[max];
int [] primes = new int[max / 3 + 1];
int pi = 0;
for (int m = 2; m < max ; m ++) {
    if (!flags[m]) {
        primes[pi++] = m;
        for(int n = m; n < max; n += m) {
            flags[n] = true;
        }
    }
}
System.out.println(Arrays.toString(primes));

用位操作来压缩空间占用将会使空间的占用减少八分之七

int max = 100;
int[] flags2 = new int[max / 32 + 1];
pi = 0;
for (int m = 2; m < max ; m ++) {
    if ((((flags2[m / 32] >> (m % 32)) & 1) == 0)) {
        primes[pi++] = m;
        for(int n = m; n < max; n += m) {
            flags2[n / 32] |= (1 << (n % 32));
        }
    }
}
System.out.println(Arrays.toString(primes));

求绝对值

上面的知识点的延伸，负数取反加1得正数，正数不变，即得绝对值。
因此先移位来取符号位，int i = a » 31;要注意如果a为正数，i等于0，为负数，i等于-1。然后对i进行判断——如果i等于0，直接返回。否之，返回~a+1：
int i = a >> 31;
System.out.println(i == 0 ? a : (~a + 1));
对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：
int j = a >> 31;
System.out.println((a ^ j) - j);

不用加法求两数之和

或运算；异或运算，同为假，异为真！0和1的异或运算如下：0^0 = 0， 1^0 = 1， 0^1 = 1，1^1 = 0
0和1的二进制加法，
不考虑进位：1+1=0，1+0=1，0+1=1，0+0=0，
在不考虑进位的时候，加法可以用异或实现；考虑有进位，0+0进位是0，1+0、0+1进位是0，1+1进位是1，与运算：0&0=0，0&1=0，1&0=0，1&1=1，在考虑进位运算时，加法和&运算类似；
加法运算可以这样实现：
1）先不考虑进位，按位计算各位累加（用异或实现），得到a；
2）然后计算进位，并将进位的值左移，得到值b。若b为0，则a就是加法运算的结果；若b不为0，则a+b即得结果（递归调用这个过程）。

public int bitAdd(int a, int b) {
    if (b == 0) {
        return a;
    }
    int sum = a ^ b;
    int carry = (a & b) << 1;
    return bitAdd(sum, carry);
}

BitSet

BitSet类：大小可动态改变，取值为true或false的位集合。用于表示一组布尔标志。此类实现一个按需增长的位向量。位 set 的每个组件都有一个 boolean 值。用非负的整数将 BitSet 的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作，可以使用一个 BitSet 修改另一个 BitSet 的内容。默认情况下，set 中所有位的初始值都是 false。
每个位 set 都有一个当前大小，也就是该位 set 当前所用空间的位数。这个大小与位 set 的实现有关，所以它可能随实现的不同而更改。位 set 的长度与位 set 的逻辑长度有关，并且是与实现无关而定义的。
除非另行说明，否则将 null 参数传递给 BitSet 中的任何方法都将导致 NullPointerException。在没有外部同步的情况下，多个线程操作一个 BitSet 是不安全的。

JDK源码

JDK源码中有许多巧妙利用位运算的地方，翻看源码，会有很大收获的。

ConcurrentHashMap

实例化ConcurrentHashMap时带参数时，会根据参数调整table的大小，确保table的大小总是2的幂次方，调用tableSizeFor的时候每次返回的都是大于等于离该数最近的2的幂次方的数。

// The largest possible table capacity.
private static final int MAXIMUM_CAPACITY = 1 << 30;
// constructor
public ConcurrentHashMap(int initialCapacity) {
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}
// Returns a power of two table size for the given desired capacity.
private static int tableSizeFor(int c) {
    int n = c - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

拓展：求小于等于给定数的最大的一个2的幂次方的数？

private static int tableSizeFor(int n) {
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return  n - (n >> 1);
}