[译]你必须知道的基本位运算技巧

编辑于2018年07月18日

原文链接

我决定写一篇关于嵌入式系统工程师第二习性的文章-基本的位运算技巧。位运算是精妙的编程小技巧,以聪明高效的方式操作整数。在执行某些操作(例如对整数二进制中的 1 进行计数)时,这些技巧通过一或两个精挑细选的位操作来完成,而不是通过遍历整数的每一位。

为了后面的内容能顺利进行,我假设你知道一个整数如何用二进制补码的形式表示并且你知道所有的位运算。

在本文中,我将使用以下符号来表示位运算:

&   -  与
|   -  或
^   -  异或
~   -  取反
<<  -  左移
>>  - 右移

文章中的数字是以二进制补码形式表示的 8 位有符号整数(尽管这些操作可以在任意长度的有符号整数上工作),他们通常被命名为 “x”,结果通常为命名为 “y”。“x” 的每一位被命名为 b7, b6, b5, b4, b3, b3, b2, b1 and b0。b7 是符号位(最高位),b0 是最低位。

我将从最基本的技巧开始,逐渐的提升难度。我将通过具体的例子来解释每个位运算技巧的工作原理。

如果你对这个主题感兴趣,我强烈建议你订阅我的博客。我可以分享一个秘密,这篇文章还有第二部分,包含更多的高级的位运算技巧,并且我还将发布一个包含所有这些技巧的备忘。这很值得订阅。

现在开始吧。

1. 判断一个整数是奇数还是偶数

if ((x & 1) == 0) {
  x is even
}
else {
  x is odd
}

我十分确信每个人都见过这个技巧。核心思路是如果整数的最低位 b0 是 1,那么这个数就是奇数。这是因为 ‘x’ 的二进制表示中,b0 位只是能是 1 或者 0。将 ‘x’ 和 1 进行与运算可以消除除了 b0 以外的其他位。如果这个操作的结果是 0,那么 ‘x’ 就是偶数,因为 b0 是 0
,否则 ‘x’ 是奇数。

我们来看一些例子。我们选择整数 43,它是一个奇数,二进制表示是 00101011,它的最低位 b0 是 1(重点)。现在将它和 1 相与:

    00101011
&   00000001   (注释: 1 的二进制是 00000001)
    --------
    00000001

看到与运算是如何消除高位 b1-b7 而留下 b0 的吗?结果是 1,这告诉我们整数是奇数。

现在我们看一下 -43。温馨提示一下,获取一个数的负数的二进制补码的快速方法是用该数的绝对值取反加 1(注意符号位,正数省略了前面的 0)。所以 -43 的二进制是 11010101,可以看到它的最低位仍是 1,并且这个数是奇数(敲黑板:如果我们不使用补码的话,就不是这样)。

我们再来看下 98,它的二进制码为 1100010

    01100010
&   00000001
    --------
    00000000

与运算后的结果是 0,这表示 98 的 b0 位是 0,所以是偶数。
再试一下负数 -98,二进制码为 10011110,b0 位是 0,与运算后的结果是 0,说明 -98 是偶数。

2. 判断第 n 位是否是 1

if (x & (1<<n)) {
  n-th bit is set
}
else {
  n-th bit is not set
}

在上一个技巧中,我们通过 x&1 判断第一位是否是 1。这个技巧对此进行了改善,可以判断任意位是否是 1。它的原理是,将 1 左移 n 位,然后与给定的数进行与运算,这将会消除除了第 n 位之外的其他位。

下面是 1 进行左移的结果:

1         00000001    (same as 1<<0)
1<<1      00000010
1<<2      00000100
1<<3      00001000
1<<4      00010000
1<<5      00100000
1<<6      01000000
1<<7      10000000

如果我们将 ‘x’ 与左移 n 位的 1 进行与运算,就可以有效的排除 ‘x’ 中除了第 n 位之外的其他位。如果运算的结果是 0,说明第 n 位是 0,否则是 1。

我们来看一些具体例子。

122 的第三位是 1 吗?我们要执行的操作是:122 & (1<<3)
122 的二进制码是 011110101<<3 的结果是 00001000

    01111010
&   00001000
    --------
    00001000

可以看到结果不是 0,说明 122 的第三位是 1。

注意:在我的文章中,位从 0 开始计数。

那 -33 呢?它的第 5 位是 1 吗?

    11011111      (-33 in binary)
&   00100000     (1<<5)
    --------
    00000000

结果是 0,所以第 5 位不是 1。

3. 将第 n 位设为 1

y = x | (1<<n)

这个技巧同样使用了移位运算(1<<n)来将第 n 位置为1,只是将前面的 & 替换成了 |。将一个变量和第 n 位为 1 的数进行或运算的结果是该变量的第 n 位会被置为 1。这是因为任何数与 0 相或,结果是 0;与 1 相或结果位 1()。让我们来看看这是如何工作的:

假设我们有一个数是 120,并且想把它的第 2 位置为 1。

    01111000    (120 in binary)
|   00000100    (1<<2)
    --------
    01111100

如果将 -120 第 6 位置为 1 呢?

    10001000   (-120 in binary)
|   01000000   (1<<6)
    --------
    11001000

4. 将第 n 为设为 0

y = x & ~(1<<n)

这个技巧的核心是 ~(1<<n),它除了第 n 位是 0,其他位都是 1。

它看起来像这样:

~1        11111110  (same as ~(1<<0))
~(1<<1)   11111101
~(1<<2)   11111011
~(1<<3)   11110111
~(1<<4)   11101111
~(1<<5)   11011111
~(1<<6)   10111111
~(1<<7)   01111111

将其与变量 ‘x’ 相与的结果是 ‘x’ 的第 n 位会置 0。无论这个数的第 n 位是 0 还是1,和 0 相与的结果都是 0。

这是一个例子,让我们把 127 的第 4 位设为 0:

    01111111    (127 in binary)
&   11101111    (~(1<<4))
    --------
    01101111

5. 将第 n 位的值取反

y = x ^ (1<<n)

这个技巧仍然是“设置第 n 位的值”,但是这次是与变量 ‘x’ 进行异或运算。如果两个数的每一位都相同,异或的结果是 0,否者是 1。那它是如何使第 n 位取反的呢?如果第 n 位是 1,那么与 1 进行异或运算的结果是 0;相反地,如果第 n 位是 0,那么和 1 进行异或的结果是 1。看到没,位会被翻转。

下面这个例子将 01110101 的第 5 位取反:

    01110101
^   00100000
    --------
    01010101

如果其他位相同,但是第 5 位是 0 呢?

    01010101
^   00100000
    --------
    01110101

注意到了吗?执行两次异或运算后返回最迟的值。这个漂亮的异或运算用来计算 RAID 矩阵的奇偶性和简单的加密计算,更多内容见其他文章。

6. 将最右边的 1 设为 0

y = x & (x-1)

现在终于变得更加有趣!!!说实话前面 5 个技巧有点无聊。

这个技巧将将最右边的 1 设为 0。例如,给出一个整数 00101010(最右边的 1 被加粗),结果变为 00101000。或者将 00010000 变为 0,因为它只有一个 1。

下面是更多的例子:

    01010111    (x)
&   01010110    (x-1)
    --------
    01010110

    01011000    (x)
&   01010111    (x-1)
    --------
    01010000

    10000000    (x = -128)
&   01111111    (x-1 = 127 (with overflow))
    --------
    00000000

    11111111    (x = all bits 1)
&   11111110    (x-1)
    --------
    11111110

    00000000    (x = no rightmost 1-bits)
&   11111111    (x-1)
    --------
    00000000

为什么这样可以呢?

如果你仔细观察并思考上面的例子,可以发现有两种情况:

  1. 最右边存在值为 1 的位。在这种情况下,减一会使比该位低的位的值变为 1,而自身变为 0(所以如果你加一,可以得到原来的值)。这一步已经屏蔽了最右边的 1,接着将它与原来的值进行与运算,最右边的 1 就被设为了 0。
  2. 最右边不存在值为 1 的位(全都是 0)。这种情况下减一,值会溢出,所有的位被设位 1,将其和 0 相与,结果为 0。

7. 分离最右边的 1

y = x & (-x)

这个技巧找出最右边的 1 并将其他为设为 0。例如:01010100 会变为 00000100。

下面是一些例子:

    10111100  (x)
&   01000100  (-x)
    --------
    00000100

    01110000  (x)
&   10010000  (-x)
    --------
    00010000

    00000001  (x)
&   11111111  (-x)
    --------
    00000001

    10000000  (x = -128)
&   10000000  (-x = -128)
    --------
    10000000

    11111111  (x = all bits one)
&   00000001  (-x)
    --------
    00000001

    00000000  (x = all bits 0, no rightmost 1-bit)
&   00000000  (-x)
    --------
    00000000

这个技巧的利用了二进制补码。在二进制补码系统中,-x 等于 ~x+1。现在我们来检查两种可能的情况:

  1. 最右边存在值为 1 的位 b(i)。我们将所有的位分成两部分,b(i)右边位b(i-1),b(i-2),b(0),左边位 b(i+1),...,b(n)。现在我们来计算 -x:首先将 x 取反,则 b(i) 为 0 ,b(i-1),...,b(0) 为 1,并反转了 b(i+1),...,b(n)。接着执行加 1,则 b(i-1),b(i-2),...,b(0) 变为 0,b(i) 变为 1。最后,与原始的 x 相与,则 bi 左边全部为 0 (高位取反),bi右边也全为 0,只有 bi 为 1。
  2. 最右边不存在 1。值为 0 ,0 的二进制补码仍是 0,0&0=0,没有位会被设为 1。

8. 将最右边的 1 后面都设位 1

y = x | (x-1)

例如:01010000 变为 01011111。

这个技巧并不完善,因为 0 会变成 1,而 0 中没有 1。

    10111100  (x)
|   10111011  (x-1)
    --------
    10111111

    01110111  (x)
|   01110110  (x-1)
    --------
    01110111

    00000001  (x)
|   00000000  (x-1)
    --------
    00000001

    10000000  (x = -128)
|   01111111  (x-1 = 127)
    --------
    11111111

    11111111  (x = -1)
|   11111110  (x-1 = -2)
    --------
    11111111

    00000000  (x)
|   11111111  (x-1)
    --------
    11111111
  1. 不存在 1。这种情况下 x=0,并且 x-1 等于 -1。-1 的二进制补码为 11111111,将其与 0 相或得到的结果为 1。
  2. 存在 1。参考第 6 个技巧,x-1 会将最右边的 1 设为 0,并将该位后面的位设位 1,这里和原来的值进行或运算,该位后面的位也会被设位 1,并且因为原本该位是 1 ,现在是 0,或运算后结果还是 1。

9. 分离最右边的 0

y = ~x & (x+1)

这个技巧和第 7 个是相反地,它找到最右边的 0,将其值设为 1 并将其他为设置 0。

    10111100  (x)
    --------
    01000011  (~x)
&   10111101  (x+1)
    --------
    00000001

    01110111  (x)
    --------
    10001000  (~x)
&   01111000  (x+1)
    --------
    00001000

    00000001  (x)
    --------
    11111110  (~x)
&   00000010  (x+1)
    --------
    00000010

    10000000  (x = -128)
    --------
    01111111  (~x)
&   10000001  (x+1)
    --------
    00000001

    11111111  (x = no rightmost 0-bit)
    --------
    00000000  (~x)
&   00000000  (x+1)
    --------
    00000000

    00000000  (x)
    --------
    11111111  (~x)
&   00000001  (x+1)
    --------
    00000001

证明:假设最右边存在 0。~x 将最右边的 0 设置 1,x+1 也一样。接着将 ~xx+1 相与,比该位高的都会被设为 0 (因为取反了,高位变了,而x+1操作不会修改高位),x+1 将比该位低的都设位 0,然后将该位设为 1,所以相与后,比该为低的都会被设为 0。

10. 将最右边的 0 设为 1

y = x | (x+1)

例如:10100011 变成 10100111。

    10111100  (x)
|   10111101  (x+1)
    --------
    10111101

    01110111  (x)
|   01111000  (x+1)
    --------
    01111111

    00000001  (x)
|   00000010  (x+1)
    --------
    00000011

    10000000  (x = -128)
|   10000001  (x+1)
    --------
    10000001

    11111111  (x = no rightmost 0-bit)
|   00000000  (x+1)
    --------
    11111111

    00000000  (x)
|   00000001  (x+1)
    --------
    00000001

证明:将 x 和 x+1 相或不会丢失任何信息。x+1使最右边的 0 变成 1,最右边 0 右边的结果为 0。两者相或的结果为 max{x, x+1},而 x+1最右边的 0 被设为了 1。

技巧总结

  1. 判断一个整数是奇数还是偶数:将该数与 1 相与,结果为 0 则是偶数,结果为 1 则是奇数。
  2. 判断第 n 位是否是 1:x & (1<<n),结果为 1 说明是,为 0 说明不是。
  3. 将第 n 位设为 1:y = x | (1<<n)
  4. 将第 n 为设为 0:y = x & ~(1<<n)
  5. 将第 n 位的值取反:y = x ^ (1<<n)
  6. 将最右边的 1 设为 0:y = x & (x-1)
  7. 分离最右边的 1:y = x & (-x)
  8. 将最右边的 1 后面都设位 1:y = x | (x-1)
  9. 分离最右边的 0:y = ~x & (x+1)
  10. 将最右边的 0 设为 1:y = x | (x+1)

希望对您能有帮助,打赏随意