位运算的小技巧

2022-10-16

Algo

在 移位运算和 异或运算中讨论了这两种位运算。计算机中还有一些其他的位运算，它们比较简单，但也还有一些巧妙的作用，本文将逐一介绍它们。

按位与 #

按位与（bitwise and）记作&，只有2个操作数都为1时，结果才为1，否则为0。按位与的真值表为：

1&1 = 1
1&0 = 0
0&1 = 0
0&0 = 0

看来，通过与1进行与运算，可以判断该位是0或者是1；通过与0进行位运算，可以将该位置为0。利用这些性质，可以用来：

1. 判断奇偶性：一个数&1，为0则为偶数，为1则为基数；

val a = 0xf5
println(a and 1 == 0)

2. 取一个数中的指定位；

1// 取低4位
2val a = 0xf5
3var b = a and 0xf
4println("0x${b.toString(16)") // 0x5

3. 清零：将一个数&0，即可清零。

按位或 #

按位或（bitwise or）记作|，两个操作数任意一个为1，则结果为1，其真值表为：

1|1 = 1
1|0 = 1
0|1 = 1
0|0 = 0

和按位与相反，一个数|1，则可以将其置为1。

按位取反 #

按位取反（bitwise not）记作~，即0变成1，1变成0

位运算的小技巧 #

位运算程序中运行最高效的代码，在实际编程经验中使用颇少。而复杂的位运算代码往往晦涩难懂（Java集合框架源码就大量使用了位运算）。这里总结一些和位运算有关的小技巧，增强对位运算的理解。

1. >>>和<<的简单乘除法

2. &操作的奇偶性判断

3. ^操作的交换2个数

4. ~操作的取相反数：-x = ~x + 1

5. 取绝对值

   正数的绝对值是其本身，负数的绝对值是其正数。对于一个任意数，先判断其符号，之后即可取得其绝对值。

   1fun abs(a:Int): Int {
   2var i = a shr 31 // a >> 31 
   3return if (i == 0 ) a else a.inv() + 1
   4}
   

   将一个Int型整数逻辑右移31位，若为0，则为正数，若为负数，则为1。

   因i的值为0或-1（0xffffffff），而异或运算有如下性质：

   一个数与0异或，返回其自身；与1异或，相当于取反。故上述代码还可以进行优化：

   1fun abs(a:Int):Int {
   2    var i = a shr 31
   3    return (a.xor(i)) - i
   4}
   

6. 位操作进行高低位交换

   给定一个16位的无符号数，将其高8位和低8位进行交换，求交换后的值。

   1var j = 0x86c8
   2var k = ((j shr 8) or (j shl 8))
   3println("0x${(k and 0xffff).toString(16)}") // 0xc886
   

   将一个数右移8位，即可得到低8位的数；将一个数左移8位，即可得到高8位的数。然后将两个数进行按位或（|）运算，即可。

   kotlin/java中无法表示无符号数¹，因此例子中使用整型参与运算，最后的结果与0xffff进行按位与（&）操作，将高位置0，即可得到反转的数。

7. 位操作二进制逆序

8. 位操作统计二进制中1的个数

9. 位运算计算2个整数的和： (a ^ b) + (a & b << 1)

• 位操作有哪些奇淫技巧？