縦のビット単位のCOUNT（同じ位置にあるものの合計）

Question

多くの変数で同じ位置にCOUNT個のCOUNTを実行する効率的な方法はありますか？ count関数は、対応するビット数の1の和で配列を満たす必要があります。私はなく、上記の問題のために、全体の単一の変数でものを合計するための多くの解決策を見つけた

uint8_t a = 0xF; // 0000 1111 
uint8_t b = 0x3C; // 0011 1100 
uint8_t c = 0xF0; // 1111 0000 

int result[8]; 

// some operations ... 

count << result[0] << result[1] << .... // prints 1122 2211 

：たとえば、私たちは三つの変数（私はそれを簡単にするために8ビットの変数を使用する）は、次のしています。

Answer 1

この小さなコードは、まさにあなたが望むものです。小さなルックアップ配列を使ってN変数をサポートするように簡単に展開できます。 double not操作の使用に注目してください。これは、どちらかに出力をドラッグして0または1

#include <iostream> 

using namespace std; 

int main() { 
    uint8_t a = 0xF; // 0000 1111 
    uint8_t b = 0x3C; // 0011 1100 
    uint8_t c = 0xF0; // 1111 0000 

    unsigned result[8]; 
    for(int i = 0; i < 8; ++i) { 
     unsigned mask = 1 << i; 
     result[i] = !!(a & mask) + !!(b & mask) + !!(c & mask); 
    } 

    for(int i = 0; i < 8; ++i) 
     cout << result[i]; 
} 

Answer 2

変数の特定の位置に1があるかどうかを判断するのは、通常の人口カウントよりもはるかに簡単です。

bool hasOneAtPosition(int position, int target) { 
    int mask = 1 << position; 
    return (target & mask) != 0; 
} 

...すべての入力でそれを呼び出し、trueを返すたびにカウンタを増やしてください。シンプレズ。

Answer 3

uint32_t 16進数に各uint8_t二進数を展開し、「それらを追加」することです。 1ビットあたり15を超えないように長い。

#include <stdio.h> 
#include <stdint.h> 

// See below for tighter code 
uint32_t shift_nibble(uint8_t x) { 
    uint32_t y = 0; 
    uint32_t mask = 1; 
    while (x) { 
    if (x & 1) { 
     y |= mask; 
    } 
    mask <<= 4; 
    x >>= 1; 
    } 
    return y; 
} 

void PrintVerticalBitwiseCount(const uint8_t *x, size_t size) { 
    uint32_t y = 0; 
    for (size_t i=0; i<size; i++) { 
    y += shift_nibble(x[i]); 
    } 
    printf("%08lX\n", (unsigned long) y); 
} 

int main(void) { 
    const uint8_t a[] = { 0xF, 0x3C, 0xF0 }; 
    PrintVerticalBitwiseCount(a, sizeof a/sizeof *a); 
    return 0; 
} 

出力

11222211 

---

候補shift_nibble()速いです。あなたの8進数の帽子を置く

uint32_t shift_nibble(uint8_t x) { 
    uint32_t y; 
    y = UINT32_C(0x01010101) & (UINT32_C(0001010101) * (x & 0x55)); 
    y |= UINT32_C(0x10101010) & (UINT32_C(0010101010) * (x & 0xAA)); 
    return y; 
} 

Answer 4

テンプレートとして私は以下の関数をC++ 11で提案します。返されるリストには、各ビットの適切な場所にビットカウントがあります。つまり、最下位ビットカウントは0の位置にあり、次に1番目の位置にあります。 これは誰かを助けることを望みます。

template<typename T> 
std::list<long> 
vertical_bit_sum(std::vector<T> items) 
{ 
    size_t bits = sizeof(T) * 8; 
    std::list<long> result; 
    do 
    { 
     long count = 0; 
     for (T item : items) 
     { 
      count += (0x1 & (item >> (bits-1))); 
     } 

     result.push_front (count); 
     --bits; 
    } 
    while(bits > 0); 

    return result; 
} 

std::list<long> result= vertical_bit_sum<uint8_t>({ 0xF, 0x3C, 0xF0 }); 

Answer 5

このような何か：全くのスピードについて

uint64_t accum = 0; 
uint64_t table[0x100] = {.. precomputed vals ...}; 
int count = 0xFF; 
while(bytes_available()) { 
    if(--count == 0) { 
    count = 0xFF; 
    for(int i = 0; i < 8; i++) 
     result[i] = ((uint8_t*)&accum)[i]; 
    accum = 0; 
    } 
    accum += table[(uint8_t)get_next_byte()]; 
} 

Answer 6

を、あなたは、単一の64ビットのアキュムレータにパックされた8つのバイトを保つことによって、並列に8つのカウントを処理することができます。

元の8ビットをバイトに展開した256個の64ビットエントリでルックアップテーブルを初期化します。 （例えば、エントリLookup[0x17u]は0x0000000100010101ulにマップ。）

カウントはあなたが64ビットで8バイトの配列をマッピングすることにより、個々のカウンタを取得

Acc+= Lookup[Byte]; 

用いて行われます。

オーバーフローが発生する前に256回の累算を実行できます。さらに必要な場合は、256のブロックに累積し、ブロックが処理された後、そのカウントをより大きなアキュムレータに転送します。

16回まで蓄積する必要がある場合は、32ビットのアキュムレータで十分です。