HAKMEM漢明重量bithack有一個錯誤，任何方式來保存它？

;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位的位。HAKMEM漢明重量bithack有一個錯誤，任何方式來保存它？

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將是理想的）。修復此功能的最佳方法是什麼？

來源

2016-02-29 OmnipotentEntity

從[這篇文章]（http://www.hackersdelight.org/corres.txt）的項目8有幫助嗎？ – njuffa

@njuffa不是真的，它是一個完全不同的算法？ – OmnipotentEntity

我瞭解你的問題，尋找基於HAKMEM的代碼計數1位，是不是這樣？項目8下的'popcnt32（）'將計算一個整數實體中的1位，最大爲32位，同時避免了昂貴的分割。 – njuffa

在下面我假設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; 
}

來源

2016-02-29 20:27:04 njuffa

HAKMEM漢明重量bithack有一個錯誤，任何方式來保存它？

回答

相關問題