为什么使用位运算

机器采用二进制对数值进行表示、存储和运算，在程序中恰当的使用二进制，可以提高运行效率。

十进制和二进制之间的转化

01

短除法（十进制转二进制）

示例：7的二进制是多少？

1. 第一步：7 除以 2 等于 3，余数为 1；

2. 第二步：3 除以 2 等于 1，余数为 1；

3. 第三步：1 除以 2 等于 0，余数为 1；

等于0时停止，倒着把余数连起来就是二进制，如上：7的二进制为 111。

02

幂次和（二进制转十进制）

示例：将二进制1101转为十进制是多少？

2^3 + 2^2 + 2^0 = 8 + 4 + 1 = 13

位运算符

注：在Java中，>> 为算术右移，移动时最高位补符号位，不一定是0。如果是负数（即最高位符号位为1）。如果需要右移时最高位补0，忽略符号位，那么应该使用逻辑右移 >>>，多了一个尖括号 。

01

异或运算

相同为0，不同为1。异或运算的特点和应用：

• x ^ 0 = x: 一个数与0异或，结果还是其自己。

• x ^ x = 0: 一个数与自己异或，结果为0。

• 结合律：a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c

• 成对变换：(0 ^ 1 = 1, 1 ^ 1 = 0), (2 ^ 1 = 3,  3 ^ 1 = 2), (4 ^ 1 = 5, 5 ^ 1 = 4) ...... (2n ^ 1 = 2n + 1, (2n + 1) ^ 1 = 2n)

• 交换两个数：如交换a与b,a = a ^ b; b = a ^ b; a = a ^ b;

1. a = a ^ b;

2. b = a ^ b = a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a;

3. a = a ^ b = a ^ b ^ a = a ^ a ^ b = 0 ^ b = b;

02

指定位置的位运算

二进制数，从右边数的第 n 位, n 从 0 开始。

• 获取 x 在二进制下的第 n 位：（x >> n）& 1)
• 将 x 在二进制下的第 n 位设置为 1 ：x | (1 << n)
• 将 x 在二进制下的第 n 位设置为 0 ：x & (~(1 << n))
• 将 x 在二进制下的第 n 位取反：x ^ (1 << n)
• 将 x 最右边的 n 位清零：x & (~0 << n)
• 将 x 的最高位到第 n 位（包含）清零：x & ((1 << n) - 1)

03

位运算实战要点

判断奇偶：

• 偶数：x % 2 == 0  =>  (x & 1) == 0

• 奇数：x % 2 == 1 等价于 (x & 1) == 1

  
  

除以2的幂次：

• x / 2 = x >> 1

• x / 2 ^ n = x >> n: x 除以 2 的 n 次方 等于 x 右移 n 位。

• mid = (left + right) / 2 = (left + right) >> 1

lowbit:

• 得到最低位的1: x & -x 或 x & (~x + 1)

• 清零最低位的1: x & (x - 1)
  

本篇文章来源于微信公众号: i余数