英文原文链接 https://catonmat.net/low-level-bit-hacks

我决定写一篇关于嵌入式系统程序员的第二天性的文章——低级位黑客。Bit hacks 是巧妙的小程序设计技巧，它以一种智能且高效的方式操纵整数。这些编程技巧不是通过循环各个位来执行操作（例如计算整数中的 1 位的数量），而是通过一两个精心选择的位操作来执行相同的操作。
为了让事情顺利进行，我假设您知道整数的二进制补码表示是什么，并且您知道所有的按位运算。在本文中，我将使用以下符号进行按位运算：

  1. & - 按位与
  2. | - 按位或
  3. ^ - 按位异或
  4. ~ - 按位非
  5. << - 按位左移
  6. >> - 按位右移

本文中的数字是 8 位有符号整数（尽管操作适用于任意长度的有符号整数），表示为二进制补码，通常命名为“x”。结果通常是’y’。’x’ 的各个位被命名为 b7、b6、b5、b4、b3、b3、b2、b1 和 b0。位 b7 是最高有效位（或在有符号算术中 - 符号位），而 b0 是最低有效位。
我将从最基本的小技巧开始，然后逐渐发展到更难的小技巧。我将使用示例来解释每个 bithack 的工作原理。
如果你喜欢这个主题，你可以订阅我的博客，或者你可以继续阅读。在本文的第二部分中，我将介绍更高级的位技巧，我还将发布一份包含所有这些位技巧的备忘单。
开始了！

位黑客#1。检查整数是偶数还是奇数。

  1. if ((x & 1) == 0) { 
  2.   x 是偶数
  3. } 
  4. else { 
  5.   x 是奇数
  6. }

我很确定每个人都看过这个技巧。这里的想法是，当且仅当最低有效位b0为 1 时，整数才是奇数。它遵循“x”的二进制表示，其中位b0对 1 或 0 有贡献。通过与“x”与1 我们消除了除b0之外的所有其他位。如果此操作后的结果为 0，则“x”为偶数，因为位b0为 0。否则“x”为奇数。
让我们看一些例子。让我们取整数 43，它是奇数。二进制 43 是 0010101 1。请注意，最低有效位b0为 1（粗体）。现在让我们与 1 相加：

  1.     00101011 
  2. &   00000001（注：1与00000001相同）
  3.     -------- 
  4.     00000001

看看 AND-ing 是如何擦除所有高阶位 b1-b7 但保留位b0的？因此结果是 1，它告诉我们整数是奇数。
现在让我们看看-43。提醒一下，在二进制补码表示中找到给定数字的负数的一种快速方法是将所有位反转并加一个。所以 -43 是二进制的 11010101。再次注意最后一位是 1，整数是奇数。（请注意，如果我们使用一个补码，那将是不正确的！）
现在让我们看一下偶数 98。二进制 98 是 1100010。

  1.     01100010 
  2. &   00000001 
  3.     -------- 
  4.     00000000

AND-ing 后的结果为 0。这意味着原始整数 98的b0位为 0。因此给定的整数是偶数。
现在负-98。是 10011110。同样，b0位为 0，经过与运算后，结果为 0，即 -98 为偶数，确实如此。

位黑客#2。测试是否设置了第 n 位。

  1. if (x & (1<<n)) {
  2.   第 n 位已设置
  3. } 
  4. else {
  5.   第 n 位未设置
  6. }

在前面的 bit hack 中，我们看到 (x & 1) 测试是否设置了第一位。此位破解改进了此结果并测试是否设置了第 n 位。它通过将第一个 1 位 n 位置向左移动，然后执行相同的 AND 操作来实现，这消除了除第 n 位之外的所有位。
如果将 1 向左移动几个位置，会发生以下情况：

  1. 1 00000001 （与 1<<0 相同）
  2. 1<<1 00000010 
  3. 1<<2 00000100 
  4. 1<<3 00001000 
  5. 1<<4 00010000 
  6. 1<<5 00100000 
  7. 1<<6 01000000 
  8. 1<<7 10000000

现在，如果我们将“x”与 1 向左移动 n 个位置进行与运算，我们有效地消除了“x”中除第 n 位之外的所有位。如果与运算后的结果为 0，则该位必须为 0，否则该位已设置。
让我们看一些例子。
122 是否设置了第三位？我们要找出它的操作是：
122 & (1<<3)
现在，122 是二进制的 01111010。并且 (1<<3) 是 00001000。

  1.     01111010 
  2. &   00001000 
  3.     -------- 
  4.     00001000

我们看到结果不是 0，所以是的，122 设置了第 3 位。
注意：在我的文章中，位编号从 0 开始。所以它是第 0 位、第 1 位、…、第 7 位。
-33 呢？它是否设置了第 5 位？

  1.     11011111 (-33 in binary) 
  2. &   00100000 (1<<5) 
  3.     -------- 
  4.     00000000

结果为 0，因此第 5 位未设置。

位黑客#3。设置第 n 位。

y = x | (1<<n)
这个位技巧结合了相同的 (1<假设我们的值是 120，并且我们想要打开第 2 位。

  1.     01111000（二进制120）
  2. |   00000100 (1<<2) 
  3.     -------- 
  4.     01111100

-120 和第 6 位呢？

  1.     10001000（二进制-120）
  2. |   01000000 (1<<6) 
  3.     -------- 
  4.     11001000

位黑客#4。取消设置第 n 位。

y = x & ~(1<<n)
这个 bithack 的重要部分是 ~(1<这是它的外观：

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

用这个量与变量“x”进行与运算的效果是消除第 n 位。第 n 位是 0 还是 1 无关紧要，将其与 0 进行与运算会将其设置为 0。
这是一个例子。让我们取消设置 127 中的第 4 位：

  1.     01111111（二进制127）
  2. 和  11101111（~（1<<4））
  3.     -------- 
  4.     01101111

位黑客#5。切换第 n 位。

y = x ^ (1<<n)
这个 bit hack 还使用了美妙的“set n-th bit shift hack”，但这次它与变量 ‘x’ 进行异或运算。将某事物与其他事物进行异或运算的结果是，如果两个位相同，则结果为 0，否则为 1。它如何切换第 n 位？好吧，如果第 n 位为 1，则将其与 1 异或更改为 0；相反，如果它是 0，那么与 1 进行异或运算会将其更改为 1。看，该位被翻转了。
这是一个例子。假设您要切换值 01110101 中的第 5 位：

  1.     01110101 
  2. ^   00100000 
  3.     -------- 
  4.     01010101

相同的值但第 5 位最初为 0 呢？

  1.     01010101 
  2. ^   00100000 
  3.     -------- 
  4.     01110101

注意到什么了吗？对同一位进行两次异或运算，会将其返回到相同的值。这个漂亮的 XOR 属性用于计算 RAID 阵列中的奇偶校验并用于简单的密码学密码，但在其他文章中对此进行了更多介绍。

位黑客#6。关闭最右边的 1 位。

y = x & (x-1)
现在终于变得更有趣了！！！Bit hacks #1 - #5 老实说有点无聊。
这个位黑客关闭最右边的一位。例如，给定一个整数 001010 1 0（最右边的 1 位以粗体显示），它会将其变为 00101000。或者给定 00010000，它将其变为 0，因为只有一个 1 位。
以下是更多示例：

  1.     01010111 (x) 
  2. &   01010110 (x-1) 
  3.     -------- 
  4.     01010110 
  6.     01011000 (x) 
  7. &   01010111 (x-1) 
  8.     -------- 
  9.     01010000 
  11.     10000000 (x = -128) 
  12. &   01111111 ( x-1 = 127 (溢出)) 
  13.     -------- 
  14.     00000000 
  16.     11111111 (x = 所有位 1) 
  17. &   11111110 (x-1) 
  18.     -------- 
  19.     11111110 
  21.     00000000 (x = 没有最右边的 1 -bits) 
  22. &   11111111 (x-1) 
  23.     -------- 
  24.     00000000

为什么它有效？
如果您查看示例并思考一段时间，您会意识到有两种可能的情况：

  1. 该值具有最右边的 1 位。在这种情况下，从中减去 1 会将所有低位设置为 1，并将最右边的位更改为 0（因此，如果现在添加 1，则可以返回原始值）。这一步已经屏蔽了最右边的 1 位，现在将其与原始值进行与运算，将最右边的 1 位输出为零。

  2. 该值没有最右边的 1 位（全为 0）。在这种情况下，减一会使值下溢（因为它是有符号的）并将所有位设置为 1。将所有零与所有 1 进行与运算会产生 0。

    位黑客#7。隔离最右边的 1 位。

    y = x & (-x)
    此位破解找到最右边的 1 位并将所有其他位设置为 0。最终结果只有一个最右边的 1 位集。例如，01010 1 00（最右边的粗体位）变为 00000100。
    以下是更多示例：

    1.  10111100 (x) 
    2. &   01000100 (-x) 
    3.  -------- 
    4.  00000100 
    6.  01110000 (x) 
    7. &   10010000 (-x) 
    8.  -------- 
    9.  00010000 
    11.  00000001 (x) 
    12. &   11111111 (-x) 
    13.  -- ------ 
    14.  00000001 
    16.  10000000 (x = -128) 
    17. &   10000000 (-x = -128) 
    18.  -------- 
    19.  10000000 
    21.  11111111 (x = 所有位为一) 
    22. &   00000001 (-x) 
    23.  ---- ---- 
    24.  00000001 
    26.  00000000（x = 所有位 0，没有最右边的 1 位）
    27. &   00000000 (-x) 
    28.  -------- 
    29.  00000000

    由于二进制补码，这个位黑客有效。在二进制补码系统中，-x 与 ~x+1 相同。现在让我们检查两种可能的情况：

  3. 有一个最右边的 1 位 b i。在这种情况下，让我们以此位为中心，并将所有其他位分为两个侧面 - 右侧位和左侧位。请记住，右边的所有位 b i-1， b i-2 … b 0都是 0（因为 b i是最右边的 1 位）。左边的位就是它们的样子。我们称它们为 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 0都是 1，加一会使它们一直携带这个位到位 b i，这是第一个零位。
如果我们把它们放在一起，计算 -x 的结果是位 b i+1 , …, b n反转，位 b i保持不变，而位 b i-1 , …, b 0都是0。
现在，将 x 与 -x 与 -x 使位 b i+1 , …, b n全部为 0，保留位 b i原样，并将位 b i-1 , …, b 0设置为 0。仅剩下一位，它是位 b i - 最右边的 1 位。

  1. 没有最右边的 1 位。值为 0。二进制补码中 0 的负数也是 0。0 & 0 = 0。没有位被打开。

我们已经严格证明这个 bithack 是正确的。

位黑客#8。右传播最右边的 1 位。

y = x | (x-1)
这最好通过一个例子来理解。给定一个值 01010000，它将它变成 01011111。从最右边的 1 位开始的所有 0 位都变成了 1。
但是，这不是一个干净的技巧，因为如果 x = 0，它会产生全 1。
让我们看更多的例子：

  1.     10111100 (x) 
  2. |   10111011 (x-1) 
  3.     -------- 
  4.     10111111 
  6.     01110111 (x) 
  7. |   01110110 (x-1) 
  8.     -------- 
  9.     01110111 
  11.     00000001 (x) 
  12. |   00000000 (x-1) 
  13.     -------- 
  14.     00000001 
  16.     10000000 (x = -128) 
  17. |   01111111 (x-1 = 127) 
  18.     -------- 
  19.     11111111 
  21.     11111111 (x = -1) 
  22. |   11111110 (x-1 = -2) 
  23.     -------- 
  24.     11111111 
  26.     00000000 (x) 
  27. |   11111111 (x-1) 
  28.     -------- 
  29.     11111111

让我们证明它，虽然不像以前的 bithack 那样严格（因为它太耗时而且这不是科学出版物）。又有两种情况。让我们先从最简单的开始。

  1. 没有最右边的 1 位。在这种情况下，x = 0 且 x-1 为 -1。二进制补码中的 -1 是 11111111。OR-ing 0 与 11111111 产生相同的 11111111。（不是想要的结果，但就是这样。）

  2. 有最右边的 1 位 b i。让我们再次将所有位分成两组（如前面的示例所示）。计算 x-1 只修改右边的位，将 b i变为 0，所有低位变为 1。现在 OR-ing x 与 x-1 使所有高位（左侧）相同，将位 b i保留为 1，并且由于低位都是低 1，因此也将它们打开。结果是最右边的 1 位被传播到低位。

    位黑客#9。隔离最右边的 0 位。

    y = ~x & (x+1)
    这个bithack与#7相反。它找到最右边的 0 位，关闭所有位，并将结果中的该位设置为 1。例如，它在这个数字 10101 0 11 中找到粗体的零，产生 00000100。
    更多示例：

    1.  10111100 (x) 
    2.  -------- 
    3.  01000011 (~x) 
    4. &   10111101 (x+1) 
    5.  -------- 
    6.  00000001 
    8.  01110111 (x) 
    9.  -------- 
    10.  10001000 (~x) 
    11. &   01111000 (x+1) 
    12.  -------- 
    13.  00001000 
    15.  00000001 (x) 
    16.  -------- 
    17.  11111110 (~x) 
    18. &   00000010 (x+1) 
    19.  -------- 
    20.  00000010 
    22.  10000000 (x = -128) 
    23.  -------- 
    24.  01111111 (~x) 
    25. &   10000001 (x+1) 
    26.  -------- 
    27.  00000001 
    29.  11111111 (x = 没有最右边的 0 位) 
    30.  ----- --- 
    31.  00000000 (~x) 
    32. &   00000000 (x+1)
    33.  -------- 
    34.  00000000 
    36.  00000000 (x) 
    37.  -------- 
    38.  11111111 (~x) 
    39. &   00000001 (x+1) 
    40.  -------- 
    41.  00000001

    证明：假设有一个最右边的 0 位。然后 ~x 把这个最右边的 0 位变成 1 位。x+1 也是如此（因为最右边的 0 位更右边是 1）。现在 AND-ing ~x 与 x+1 蒸发所有位直到最右边的 0 位。这是结果中设置的最高位。现在最右边的 0 位右边的低位呢？它们也被蒸发掉了，因为 x+1 把它们变成了 0（它们是 1），而 ~x 把它们变成了 0。他们与 0 进行了与运算并蒸发了。

    位黑客#10。打开最右边的 0 位。

    y = x | (x+1)
    这个 hack 将最右边的 0 位更改为 1。例如，给定一个整数 10100011，它将其变为 10100111。
    更多示例：

    1.  10111100 (x) 
    2. |   10111101 (x+1) 
    3.  -------- 
    4.  10111101 
    6.  01110111 (x) 
    7. |   01111000 (x+1) 
    8.  -------- 
    9.  01111111 
    11.  00000001 (x) 
    12. |   00000010 (x+1) 
    13.  -------- 
    14.  00000011 
    16.  10000000 (x = -128) 
    17. |   10000001 (x+1) 
    18.  -------- 
    19.  10000001 
    21.  11111111 (x = 没有最右边的 0 位) 
    22. |   00000000 (x+1) 
    23.  -------- 
    24.  11111111 
    26.  00000000 (x) 
    27. |   00000001 (x+1) 
    28.  -------- 
    29.  00000001

    这是一堆真实陈述的证明。将 x 与 x+1 进行或运算不会丢失任何信息。将 1 加到 x 填充最右边的第一个 0。结果是 max{x, x+1}。如果 x+1 溢出它是 x 并且没有 0 位。如果不是，它是 x+1，它的最右边的位被 1 填充。

    黑客的喜悦

    有一本书 300 页长，完全是关于这些小技巧的。它被称为黑客的喜悦。看一看。如果你喜欢我帖子的内容，那么你会喜欢这本书的。

    奖金的东西

    如果您决定更多地使用这些技巧，这里有一些实用程序函数可以在 Perl、Python 和 C中打印8 位有符号整数的二进制值。
    在 Perl 中打印二进制表示：

    1. sub int_to_bin {
    2. my $num = shift;
    3. print unpack "B8", pack "c", $num;
    4. }

    或者您可以立即从命令行打印它： ```shell perl -wle ‘print unpack “B8”, pack “c”, shift’

For example:

perl -wle 'print unpack "B8", pack "c", shift' 113 01110001

perl -wle 'print unpack "B8", pack "c", shift' -- -128 10000000

  1. 在 Python 中打印二进制数：
  2. ```python
  3. def int_to_bin(num, bits=8): 
  4.  r = '' 
  5.  while bits: 
  6.   r = ('1' if num&1 else '0') + r 
  7.   bits = bits - 1 
  8.   num = num >> 1 
  9.  print r

在 C 中打印二进制表示：

  1. void int_to_bin(int num) {
  2.   char str[9] = {0};
  3.   int i;
  4.   for (i=7; i>=0; i--) {
  5.     str[i] = (num&1)?'1':'0';
  6.     num >>= 1;
  7.   }
  8.   printf("%s\n", str);
  9. }

玩得开心。接下来我会写一些关于高级比特黑客的文章。回头见！