0 
;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 位是理想的）。修复此功能的最佳方法是什么？

4

1 回答 1

1

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

问题是代码原样错过了第 5 位的累积，a其中第 5 位映射到乘积的第 32 位，这在 32 位机器中是无法表示的。同时，产品的第 8 位未使用。所以我们可以隔离第 5 位a并将其移动到产品的第 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;
}
于 2016-02-29T20:27:04.223 回答