来自 'Bit Twiddling Hacks' 的 SWAR 字节计数方法 - 为什么它们有效？
SWAR byte counting methods from 'Bit Twiddling Hacks' - why do they work?
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)
但是，它并没有解释为什么它们起作用。这些宏背后的逻辑是什么？
我们来分析一下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.
让我们在 countmore.
上尝试凭直觉
首先，~0UL/255*(127-n) 是一种将值 127-n 并行复制到字中所有字节的巧妙方法。为什么它有效？ ~0 在所有字节中都是 255。因此，~0/255 在所有字节中都是 1。乘以 (127-n) 就是开头提到的“复制”。
~0UL/255*127 项只是上面的一个特例，其中 n 为零。它将 127 复制到所有字节中。如果单词是 4 个字节，那就是 0x7f7f7f7f。 x 的“Anding”将每个字节中的高位清零。
这是第一项 (x)&~0UL/255*127)。结果与 x 相同，只是每个字节中的高位被清零。
第二项~0UL/255*(127-(n))如上：127-n复制到每个字节。
对于任何给定字节 x[i]，如果 x[i]<=127，将这两项相加得到 127-n+x[i]。每当 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+...
相同
哎呀。我们完成了。
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)
但是，它并没有解释为什么它们起作用。这些宏背后的逻辑是什么？
我们来分析一下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.
让我们在 countmore.
首先，~0UL/255*(127-n) 是一种将值 127-n 并行复制到字中所有字节的巧妙方法。为什么它有效？ ~0 在所有字节中都是 255。因此，~0/255 在所有字节中都是 1。乘以 (127-n) 就是开头提到的“复制”。
~0UL/255*127 项只是上面的一个特例，其中 n 为零。它将 127 复制到所有字节中。如果单词是 4 个字节，那就是 0x7f7f7f7f。 x 的“Anding”将每个字节中的高位清零。
这是第一项 (x)&~0UL/255*127)。结果与 x 相同，只是每个字节中的高位被清零。
第二项~0UL/255*(127-(n))如上：127-n复制到每个字节。
对于任何给定字节 x[i]，如果 x[i]<=127，将这两项相加得到 127-n+x[i]。每当 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+...
相同哎呀。我们完成了。