我决定写一篇关于嵌入式系统程序员的第二天性的文章——低级位黑客。Bit hacks 是巧妙的小程序设计技巧，它以一种智能且高效的方式操纵整数。这些编程技巧不是通过循环各个位来执行操作（例如计算整数中的 1 位的数量），而是通过一两个精心选择的位操作来执行相同的操作。 为了让事情顺利进行，我假设您知道整数的二进制补码表示是什么，并且您知道所有的按位运算。在本文中，我将使用以下符号进行按位运算：
& - 按位与
| - 按位或
^ - 按位异或
~ - 按位非
<< - 按位左移
>> - 按位右移
本文中的数字是 8 位有符号整数（尽管操作适用于任意长度的有符号整数），表示为二进制补码，通常命名为“x”。结果通常是'y'。'x' 的各个位被命名为 b7、b6、b5、b4、b3、b3、b2、b1 和 b0。位 b7 是最高有效位（或在有符号算术中 - 符号位），而 b0 是最低有效位。 我将从最基本的小技巧开始，然后逐渐发展到更难的小技巧。我将使用示例来解释每个 bithack 的工作原理。 如果你喜欢这个主题，你可以订阅我的博客，或者你可以继续阅读。在本文的第二部分中，我将介绍更高级的位技巧，我还将发布一份包含所有这些位技巧的备忘单。 开始了！
if ((x & 1) == 0) {
x 是偶数
}
else {
x 是奇数
}
我很确定每个人都看过这个技巧。这里的想法是，当且仅当最低有效位_b0_为 1 时，整数才是奇数。它遵循“x”的二进制表示，其中位_b0_对 1 或 0 有贡献。通过与“x”与1 我们消除了除_b0_之外的所有其他位。如果此操作后的结果为 0，则“x”为偶数，因为位_b0_为 0。否则“x”为奇数。 让我们看一些例子。让我们取整数 43，它是奇数。二进制 43 是 0010101 1。请注意，最低有效位_b0_为 1（粗体）。现在让我们与 1 相加：
00101011
& 00000001（注：1与00000001相同）
--------
00000001
看看 AND-ing 是如何擦除所有高阶位 b1-b7 但保留位_b0_的？因此结果是 1，它告诉我们整数是奇数。 现在让我们看看-43。提醒一下，在二进制补码表示中找到给定数字的负数的一种快速方法是将所有位反转并加一个。所以 -43 是二进制的 11010101。再次注意最后一位是 1，整数是奇数。（请注意，如果我们使用一个补码，那将是不正确的！） 现在让我们看一下偶数 98。二进制 98 是 1100010。
01100010
& 00000001
--------
00000000
AND-ing 后的结果为 0。这意味着原始整数 98的_b0位为 0。因此给定的整数是偶数。_ 现在负-98。是 10011110。同样，_b0_位为 0，经过与运算后，结果为 0，即 -98 为偶数，确实如此。
if (x & (1<<n)) {
第 n 位已设置
}
else {
第 n 位未设置
}
在前面的 bit hack 中，我们看到 (x & 1) 测试是否设置了第一位。此位破解改进了此结果并测试是否设置了第 n 位。它通过将第一个 1 位 n 位置向左移动，然后执行相同的 AND 操作来实现，这消除了除第 n 位之外的所有位。 如果将 1 向左移动几个位置，会发生以下情况：
1 00000001 （与 1<<0 相同）
1<<1 00000010
1<<2 00000100
1<<3 00001000
1<<4 00010000
1<<5 00100000
1<<6 01000000
1<<7 10000000
现在，如果我们将“x”与 1 向左移动 n 个位置进行与运算，我们有效地消除了“x”中除第 n 位之外的所有位。如果与运算后的结果为 0，则该位必须为 0，否则该位已设置。
让我们看一些例子。
122 是否设置了第三位？我们要找出它的操作是：
122 & (1<<3)
现在，122 是二进制的 01111010。并且 (1<<3) 是 00001000。
01111010
& 00001000
--------
00001000
我们看到结果不是 0，所以是的，122 设置了第 3 位。 注意：在我的文章中，位编号从 0 开始。所以它是第 0 位、第 1 位、...、第 7 位。 -33 呢？它是否设置了第 5 位？
11011111 (-33 in binary)
& 00100000 (1<<5)
--------
00000000
结果为 0，因此第 5 位未设置。
y = x | (1<<n)
这个位技巧结合了相同的 (1<<n) 技巧，即通过使用 OR 操作移位来设置第 n 位。将变量与设置了第 n 位的值进行或运算的结果是打开第 n 位。这是因为将任何值与 0 进行或运算会使值保持不变；但是用 1 对其进行 OR-ing 会将其更改为 1（如果还没有的话）。让我们看看它是如何工作的：
假设我们的值是 120，并且我们想要打开第 2 位。
01111000（二进制120）
| 00000100 (1<<2)
--------
01111100
-120 和第 6 位呢？
10001000（二进制-120）
| 01000000 (1<<6)
--------
11001000
y = x & ~(1<<n)
这个 bithack 的重要部分是 ~(1<<n) 技巧。它打开除第 n 个以外的所有位。
这是它的外观：
~1 11111110 (同 ~(1<<0))
~(1<<1) 11111101
~(1<<2) 11111011
~(1<<3) 11110111
~(1<<4) 11101111
~(1<<5) 11011111
~(1<<6) 10111111
~(1<<7) 01111111
用这个量与变量“x”进行与运算的效果是消除第 n 位。第 n 位是 0 还是 1 无关紧要，将其与 0 进行与运算会将其设置为 0。 这是一个例子。让我们取消设置 127 中的第 4 位：
01111111（二进制127）
& 11101111（~（1<<4））
--------
01101111
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 位：
01110101
^ 00100000
--------
01010101
相同的值但第 5 位最初为 0 呢？
01010101
^ 00100000
--------
01110101
注意到什么了吗？对同一位进行两次异或运算，会将其返回到相同的值。这个漂亮的 XOR 属性用于计算 RAID 阵列中的奇偶校验并用于简单的密码学密码，但在其他文章中对此进行了更多介绍。
y = x & (x-1)
现在终于变得更有趣了！！！Bit hacks #1 - #5 老实说有点无聊。
这个位黑客关闭最右边的一位。例如，给定一个整数 001010 1 0（最右边的 1 位以粗体显示），它会将其变为 00101000。或者给定 00010000，它将其变为 0，因为只有一个 1 位。
以下是更多示例：
01010111 (x)
& 01010110 (x-1)
--------
01010110
01011000 (x)
& 01010111 (x-1)
--------
01010000
10000000 (x = -128)
& 01111111 ( x-1 = 127 (溢出))
--------
00000000
11111111 (x = 所有位 1)
& 11111110 (x-1)
--------
11111110
00000000 (x = 没有最右边的 1 -bits)
& 11111111 (x-1)
--------
00000000
为什么它有效？ 如果您查看示例并思考一段时间，您会意识到有两种可能的情况：
y = x & (-x)
此位破解找到最右边的 1 位并将所有其他位设置为 0。最终结果只有一个最右边的 1 位集。例如，01010 1 00（最右边的粗体位）变为 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 = 所有位为一)
& 00000001 (-x)
---- ----
00000001
00000000（x = 所有位 0，没有最右边的 1 位）
& 00000000 (-x)
--------
00000000
由于二进制补码，这个位黑客有效。在二进制补码系统中，-x 与 ~x+1 相同。现在让我们检查两种可能的情况：
现在，当我们计算 -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 位。
我们已经严格证明这个 bithack 是正确的。
y = x | (x-1)
这最好通过一个例子来理解。给定一个值 01010000，它将它变成 01011111。从最右边的 1 位开始的所有 0 位都变成了 1。
但是，这不是一个干净的技巧，因为如果 x = 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
让我们证明它，虽然不像以前的 bithack 那样严格（因为它太耗时而且这不是科学出版物）。又有两种情况。让我们先从最简单的开始。
y = ~x & (x+1)
这个bithack与#7相反。它找到最右边的 0 位，关闭所有位，并将结果中的该位设置为 1。例如，它在这个数字 10101 0 11 中找到粗体的零，产生 00000100。
更多示例：
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 = 没有最右边的 0 位)
----- ---
00000000 (~x)
& 00000000 (x+1)
--------
00000000
00000000 (x)
--------
11111111 (~x)
& 00000001 (x+1)
--------
00000001
证明：假设有一个最右边的 0 位。然后 ~x 把这个最右边的 0 位变成 1 位。x+1 也是如此（因为最右边的 0 位更右边是 1）。现在 AND-ing ~x 与 x+1 蒸发所有位直到最右边的 0 位。这是结果中设置的最高位。现在最右边的 0 位右边的低位呢？它们也被蒸发掉了，因为 x+1 把它们变成了 0（它们是 1），而 ~x 把它们变成了 0。他们与 0 进行了与运算并蒸发了。
y = x | (x+1)
这个 hack 将最右边的 0 位更改为 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 = 没有最右边的 0 位)
| 00000000 (x+1)
--------
11111111
00000000 (x)
| 00000001 (x+1)
--------
00000001
这是一堆真实陈述的证明。将 x 与 x+1 进行或运算不会丢失任何信息。将 1 加到 x 填充最右边的第一个 0。结果是 max{x, x+1}。如果 x+1 溢出它是 x 并且没有 0 位。如果不是，它是 x+1，它的最右边的位被 1 填充。
有一本书 300 页长，完全是关于这些小技巧的。它被称为黑客的喜悦。看一看。如果你喜欢我帖子的内容，那么你会喜欢这本书的。
如果您决定更多地使用这些技巧，这里有一些实用程序函数可以在 Perl、Python 和 C中打印8 位有符号整数的二进制值。 在 Perl 中打印二进制表示：
sub int_to_bin {
my $num = shift;
print unpack "B8", pack "c", $num;
}
或者您可以立即从命令行打印它：
perl -wle 'print unpack "B8", pack "c", shift' <integer>
# For example:
perl -wle 'print unpack "B8", pack "c", shift' 113
01110001
perl -wle 'print unpack "B8", pack "c", shift' -- -128
10000000
在 Python 中打印二进制数：
def int_to_bin(num, bits=8):
r = ''
while bits:
r = ('1' if num&1 else '0') + r
bits = bits - 1
num = num >> 1
print r
在 C 中打印二进制表示：
void int_to_bin(int num) {
char str[9] = {0};
int i;
for (i=7; i>=0; i--) {
str[i] = (num&1)?'1':'0';
num >>= 1;
}
printf("%sn", str);
}
玩得开心。接下来我会写一些关于高级比特黑客的文章。回头见！