来自黑客的喜悦:第二版:
这里的公式看起来有点尴尬。当 x 小于 1 时,如何从 1 向量(大概是 0x1111 1111)中减去某个 x 向量? (例如:(如示例中给出的)0x0101 1000 - 0x0000 0000对我来说没有任何意义)前一个数字比第一个数字小,并且单词也不存储有符号向量。这是与 RISC 特定相关的东西吗?
如本书注释部分所指定。粗体字母对应于单词向量,如 x = 00000000。粗体字母与浅色字体 1 不同。如粗体 1 = 11111111,它是一个 8 位单词。
Edit2: 特别感谢 Paul Hankin 找出此处使用的非常规符号。粗体字表示 32 位大小的字,即 [00000001],浅色字 1 表示数字 1,如 C 中所示。
由于我们对十进制比二进制更熟悉,因此有时了解十进制会发生什么会有所帮助。
小数减 1 会发生什么?以
1786000 - 1 = 1785999
为例。
如果用十进制正数
1
减去 x
:
x
右边的所有零都变成9
;x
最右边的非零数字减1;现在,在二进制中,它的工作原理完全相同,只是我们只有
0 1
而不是 0 123456789
。
如果用二进制数
1
减去 x
:
x
右边的所有零都变成1
;x
最右边的非零位变为0
;负数呢?令人高兴的是,使用 2 的补码表示时,负数的表现与正数完全相同。事实上,当查看
x
的位时,您可以从 1
中减去 x
,而不需要知道 x
是有符号整型还是无符号整型。
x & (x-1)
让我们从一个例子开始:
x = 01011000
。我们可以按照我刚才解释的方式减去 1:
x = 01011000
x-1 = 01010111
现在按位与运算
x & (x-1)
的结果是什么?我们取每列中的两位;如果都是1,就写1;如果其中至少有一个为 0,则写 0。
x = 01011000
x-1 = 01010111
x&(x-1) = 01010000
发生什么事了?
x
右侧的所有零保持为零;x
最右边的1变成0,因为x-1
;x
和 x-1
中是相同的。结论:我们已将
x
最右边的 1 归零,并且所有其他位不受影响。
让我们看看
x-1
做了什么。
假设 x
是一个值 '???? 1000
(?是 0 或 1)=> x-1 = ???? 0111
=> x & (x-1) = ???? 0000
无论最右边的1放在
x
内的哪个位置,都非常相似。
要求的示例:
x=00001111
=> x-1=00001110
=> x & (x-1) = 00001110
P.s.
x-1 = 00001110 - 00000001 (<=> 00001110 + 11111111)
根据用于计算给定数字中设置位的Brian Kernighan 算法,从数字x中减去1将反转其最右边设置位中的所有位。
让,
x = 14
,二进制表示为1110
。
这里,从右数第 2 位是最右边的设置位。
x - 1 = 13
,二进制表示为1101
。
可以清楚地观察到,从右数第 2 位开始的位被反转。
现在,如果我们对这两个数字进行按位 AND 运算, 即 x & (x-1) 我们将从数字 x 最右边设置的位中取消设置。看看下面的例子,
1 1 1 0 (14)
& 1 1 0 1 (13)
1 1 0 0 (12)
如果数字 x 原本是 2 的幂,那么与 (x-1) 进行按位 AND 将得到 0。例如,
1 0 0 0 (8)
& 0 1 1 1 (7)
0 0 0 0 (0)
这是因为,数字 x 是 2 的幂,在其二进制表示中仅具有 单个 设置位。
类似地,如果我们尝试将数字 x 与数字 (x-1) 的
(~) negation
进行按位 AND 操作,那么它只会 set 结果数字中最右边的位。即 x & [~(x-1)]。检查下面的例子,
x = 14
x - 1 = 13
因此,
~(x-1)
将会是,
1 1 0 1 (13)
0 0 1 0 (~13)
因此,
1 1 1 0 (14)
& 0 0 1 0 (~13)
0 0 1 0 (2)
右起第 2 位是数字 x 的二进制表示形式中最右边的设置位,即 14,是结果数字中唯一的 set 位。另外, 是 2 的幂,因为结果中只有一个设置位。