HAKMEM Hamming Weight 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位来统计第32位的位

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 位字的机器设计的，这在其创建时很常见。

问题是代码原样错过了 a 的第 5 位的累加，它映射到产品的第 32 位，这在 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=%d\n", 
                    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;
}

HAKMEM Hamming Weight bithack 有一个错误，有什么办法可以解决吗？

HAKMEM Hamming Weight bithack has a bug, any way to save it?

bit-manipulation

hammingweight