HAKMEM 汉明重量 bithack 有一个错误，任何保存它的方法

Question

;if A is a 9 bit quantity, B gets number of 1's (Schroeppel)
  IMUL A,[1001001001] ;4 copies
  AND A,[42104210421] ;every 4th bit
  IDIVI A,17 ;casting out 15.'s in hexadecimal

此函数似乎需要第 33 位来计算 32s 位置的位。

uint32_t i = 0b11101011;
uint32_t u = i * (uint32_t)01001001001;
uint32_t x = u & (uint32_t)042104210421;
v = x % 017;
std::cout << "i: " << std::bitset<8>(i) << ", u: " << std::bitset<32>(u) <<
", x: " << std::bitset<32>(x) << ", v: " << v << std::endl;

给：

i: 11101011
u: 01011011101011011101011011101011
x: 00010001000000010001000000000001
v: 5

但：

uint64_t v = i;
uint64_t u = v * (uint64_t)01001001001;
uint64_t x = u & (uint64_t)042104210421;
v = x % 017;
std::cout << "i: " << std::bitset<8>(i) << ", u: " << std::bitset<33>(u) <<
", x: " << std::bitset<33>(x) << ", v: " << v << std::endl;

给：

i: 11101011
u: 101011011101011011101011011101011
x: 100010001000000010001000000000001
v: 6

由于绝对指令的数量非常少（尽管 idiv 函数很昂贵，但在我的用例中，指令数很重要），我想使用这个或类似的函数。 但我不太明白模数 15 是如何工作的。

我只需要数到 7 位（尽管 8 位是理想的。 修复此功能的最佳方法是什么？

Answer 1

在下文中，我假设 8 位a .最初的 HAKMEM 代码可能是为具有 36 位字的机器设计的，这在创建时很常见。

问题在于，代码按原样丢失了映射到产品的第 32 位的a的第 5 位的累积，这在 32 位机器中不可表示。 同时，产品的第 8 位未使用。因此，我们可以隔离a的第 5 位，并将其移动到乘积的第 8 位。然后屏蔽每个半字节中的最低位，并通过乘法对半字节求和，因此总和最终会变成最高的半字节。生成的 C 代码如下所示。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int reference_popc (uint32_t a)
{
    int res = 0;
    while (a) {
        a &= a - 1;
        res++;
    }
    return res;
}
// based on HAKMEM item 167
int hakmem_popc_byte (uint8_t a)
{
    int r;
    r = (((((uint32_t)a * 01001001001) | ((a & 0x20) << 3)) & 0x11111111) * 0x11111111) >> 28;
    return r;
}
int main (void)
{
    uint8_t a = 0;
    do {
        if (hakmem_popc_byte(a) != reference_popc (a)) {
            printf ("error @ %08x: res=%d  ref=%dn", 
                    a, hakmem_popc_byte(a), reference_popc (a));
            return EXIT_FAILURE;
        }
        a = a + 1;
    } while (a);
    return EXIT_SUCCESS;
}

在进一步查看了初始乘法产生的位模式后，我观察到我们可以比上述快速修复做得更好。初始乘法将位 8、17 和 26 设置为零。为了避免在通过掩码选择每四个位时遇到其中任何一个，我们可以使用掩码0x88888888 .但是，这需要对提取的数据进行下移，以避免在求和过程中溢出最重要的半字节。生成的代码为：

// based on HAKMEM item 167
int hakmem_popc_byte (uint8_t a)
{
    int r;
    r = (((((uint32_t)a * 01001001001) & 0x88888888) >> 3) * 0x11111111) >> 28;
    return r;
}