1

在 HAKMEM 169 中，有一个步骤可以总结相邻八位字节中 1 的数量。

准确地说，我指的是以下链接：http ://www.verious.com/qa/fast-implementation-of-operations-on-large-sets-of-quite-big-integers/

// This is accomplished by right-shifting tmp by three bits, adding
// it to tmp itself and ANDing with a suitable mask. This yields a number in
// which groups of six adjacent bits (starting from the LSB) contain the number
// of 1¡äs among those six positions in n.

* (tmp + (tmp >> 3)) & 030707070707

我想知道的是，从八位字节（3 位）到双八位字节（6 位）是否真的需要这种 DOUBLING。如果没有加倍，做模数 7 会不会给出预期的结果？

假设没有 DOUBLING 操作的 temp 值为 00000002153（八位字节）。模数 7 (2^3-1) 将给我们 2+1+5+3，这是设置的位数。那么真的需要DOUBLE操作吗？

4

2 回答 2

0

我想出了这个的原因。答案是每个八位字节可以有一个从 0 到 7 的值。如果我们添加两个八位字节并进行模数 7，我们可能会丢失一些位。例如，

2158H 前加倍步骤意味着有 2+1+5+8 很好。但是，如果在加倍步骤之前该值为 7676H，会发生什么情况。在这种情况下，结果将是 0+6+0+6。那是错的。

因此，将八位字节加倍以考虑 6 位是必不可少的。

于 2013-06-18T11:23:53.350 回答
0

在基数n（在这种情况下为基数 64）中，取模数(n-1)会得到该基数中数字的总和；但这就是 sum mod- (n-1)。Mod-7 总是会给你一个小于 7 的答案，一个 32 位的字可能有 7 位或更多位。

根据相同原理工作的更熟悉的技巧是测试可被 9 整除。如果所有十进制数字的总和是九的倍数，则该数字可以被九整除。如果总和不能被 9 整除（因为它很大），您可以对结果使用相同的技术来减少它，直到结果为一位数。

不幸的是，除法是一项昂贵的操作，因此使用这种通用形式可能更有效：

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
于 2013-06-18T14:42:32.067 回答