位运算

常见的位运算

常见的编程语言中最小的数据类型是 byte，没有直接操作bit的，下面都是基于byte类型操作bit

byte num = 10;  // 0000 1010

• 将数的某一个bit设置成0

// 假设对应的位是 index（从低到高，低位从0开始）
// 假设 index=4
// num = num & (1111 0111);  // num & (1111 0111 .... 1111) 即可将该位置0
//1 << index  得到 0000 1000
//~(1 << index) 就能得到 1111 0111
num &= ~(1 << index);

• 将某一个bit置1

//num = num | (0000 0100); 就能将某位置1
num |= 1 << index;

• n & (n - 1)

//假设n 的 二进制是 0... .... .... ...1
// n-1 的二进制 是    0... .... .... ...0
//按位与之后，会将最低位1置0，高位不变

//假设n的二进制是     0... .100 .... ...0
//n-1 的二进制表示是 0... .011 .... 1111
//按位与之后，会将第一个1置0，（其他低位本来就是0），也是将最低位1置0，1之前的高位不变

使用场景，判断一个数是不是2的次幂

$n \& (n - 1) == 0$, 第一个1（0不存在1的位，所以排除）之前的高位都是0，一定是2的次幂

• n & (-n)

//假设n 的 二进制是 0... .... .... ...1
// -n 的二进制 是      1... .... .... ...1
//按位与之后，除最低位的1，其他位都变成0

//假设n的二进制是     0... .100 .... ...0
//-n 的二进制表示是  1...  100 .... ...0
//按位与之后，处理最低位的1，其他位都会变成0