1

Bit Twiddling Hacks包含以下宏，用于计算单词x中小于或大于n：

#define countless(x,n) \
(((~0UL/255*(127+(n))-((x)&~0UL/255*127))&~(x)&~0UL/255*128)/128%255)

#define countmore(x,n) \
(((((x)&~0UL/255*127)+~0UL/255*(127-(n))|(x))&~0UL/255*128)/128%255)

但是，它并没有解释它们为什么起作用。这些宏背后的逻辑是什么？

4

2 回答 2

2

让我们尝试一下直觉countmore。

首先，~0UL/255*(127-n)是一种将值127-n并行复制到字中所有字节的巧妙方法。为什么它有效？ ~0所有字节为 255。因此，~0/255是1所有字节。乘以(127-n)一开始提到的“复制”。

该术语只是上述零~0UL/255*127的特例。n它将 127 复制到所有字节中。那就是0x7f7f7f7f如果单词是4个字节。“Anding”x将每个字节中的高位清零。

这是第一个学期(x)&~0UL/255*127)。x结果与除了每个字节中的高位清零之外的结果相同。

第二项~0UL/255*(127-(n))如上：127-n复制到每个字节。

对于任何给定的字节x[i]，将这两项相加就可以得到127-n+x[i]if x[i]<=127。该数量将在任何时候设置高位x[i]>n。最容易将其视为添加两个 7 位无符号数。结果“溢出”到第 8 位，因为结果为 128 或更多。

所以看起来该算法将使用每个字节的第 8 位作为布尔值指示x[i]>n。

那么另一种情况x[i]>127呢？在这里我们知道字节多是n因为算法规定的n<=127。第 8 位应该始终为 1。令人高兴的是，和的第 8 位无关紧要，因为下一步“或”的结果是x。由于x[i]第 8 位设置为 1 当且仅当它为 128 或更大时，此操作仅在总和可能提供错误值时“强制”第 8 位为 1。

总结到目前为止，“或”结果在其第 i 个字节中的第 8 位设置为 1 当且仅当x[i]>n。好的。

下一个操作&~0UL/255*128将所有内容设置为零，除了所有那些感兴趣的第 8 位。这是与 0x80808080 的“与”...

现在的任务是找到设置为 1 的这些位的数量。为此，countmore使用一些基本的数论。首先它右移 7 位，所以感兴趣的位是 b0、b8、b16... 这个字的值是

b0 + b8*2^8 + b16*2^16 + ...

一个美丽的事实是 1 == 2^8 == 2^16 == ... mod 255。换句话说，每个 1 位是 1 mod 255。因此找到移位结果的 mod 255 与求和 b0+b8+b16+...

哎呀。我们完成了。

于 2021-07-10T05:46:27.837 回答
1

让我们来分析countless宏观。我们可以将此宏简化为以下代码：

#define A(n) (0x0101010101010101UL * (0x7F+n))
#define B(x) (x & 0x7F7F7F7F7F7F7F7FUL)
#define C(x,n)     (A(n) - B(x))
#define countless(x,n)  ((  C(x,n)  &  ~x  & 0x8080808080808080UL) / 0x80 % 0xFF )

A(n)将会：

A(0) = 0x7F7F7F7F7F7F7F7F
A(1) = 0x8080808080808080
A(2) = 0x8181818181818181
A(3) = 0x8282828282828282
....

而对于B(x)， 的每个字节x都会用0x7F. 如果我们假设x = 0xb0b1b2b3b4b5b6b7和n = 0，那么C(x,n)将等于0x(0x7F-b0)(0x7F-b1)(0x7F-b2)...

例如，我们假设x = 0x1234567811335577和n = 0x50。所以：

A(0x50) = 0xCFCFCFCFCFCFCFCF
B(0x1234567811335577) = 0x1234567811335577
C(0x1234567811335577, 0x50) = 0xBD9B7957BE9C7A58
~(0x1234567811335577) = 0xEDCBA987EECCAA88
0xEDCBA987EECCAA88  & 0x8080808080808080UL = 0x8080808080808080
C(0x1234567811335577, 0x50) & 0x8080808080808080 = 0x8080000080800000
(0x8080000080800000 / 0x80) % 0xFF =  4 //Count bytes that equal to 0x80 value.
于 2021-07-08T08:32:19.517 回答