位运算-基础

算法中位运算的一些常见操作

1. 异或操作

x ^ 0  = x
x ^ 1s = ~x  // 1s  = ~0
x ^ ~x = 1s
x ^ x  = 0
c = a ^ b  => a ^ c = b,  b ^ c = a    // 交换两个数
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c  // associate

2. 指定位置的 位运算

1. 将 x 最右边的 n位清零 : x & (~0 << n)
2. 获取 x 的第n位的值(1|0): (x >> n) & 1
3. 获取 x 的第n位的幂值 : x &(1 << n)
4. 仅将第 n 位置 1 : x | (1<< n)
5. 仅将第 n 位置 0 : x & ~(1<< n)
6. 仅将第 n 位取反 : x ^ (1<< n)
7. 将x最高位至第n(含)位清零: x&((1<<n) - 1)
8. 获取x 最右边的 1 : x & -x (lowbit操作)

• a = 00110100
• ~a = 11001011
• -a = 11001100
• a & -a = 00000100

3. 常用操作

1. 判断奇偶

• x % 2 == 0 => (x & 1) == 0
• x % 2 == 1 => (x & 1) == 1

2. x >> 1 == x / 2
   mid = (left + right) / 2 == mid = (left + right) >> 1

3. x = x &(x-1) 清零最低位的1

4. x & -x 得到最低位的 1

5. x & ~x == 0

4. 应用

• bloomFilter