条件付き論理AND演算子

Question

しきい値Tとビットマップのセットが与えられたら、iのビットが "1"にセットされている場合にのみ "br"のi番目のビットが1になるように結果のビットマップ "br"第1ビットは1以上のビットマップに設定される。

私は一例で私の質問を説明しようとします

： 私たちは4ビットマップを持っている（の等長の）と仮定しましょうT = 3：

b1 (10000) 
b2 (01110) 
b3 (10110) 
b4 (00010) 

その後、私の結果のビットマップBR =（00010 ） - 4ビット目のみが> 3ビットマップで1に設定されているためです。 T = 2ならば、br =（10110）。

これを行う単純な方法は、各ビットマップを反復し、i番目のインデックスにビット 'i'の数を格納するベクトルを保持することです。その後、この「カウント」ベクトルを反復することができます。

もう一つの方法は、結果のビットマップでi> = Tの位置に1に設定されている場合、i番目のビットが1に設定されるように変更された論理AND演算子を実装することです。

他に効率的な方法がありますか？私はC++とEWAHBoolArray（https://github.com/lemire/EWAHBoolArray）ライブラリを使用しています。現在、複数のビットマップ間でAND演算を実行する機能はありません。 すべての応答は非常に高く評価されています！

Answer 1

これを行うには、少しのtwiddlingと追加があります。あなたは本当に個々のビットの合計を得ようとしています。通常の追加でそれを行うには、各列に対して得ることができる最大合計のためのスペースを確保する必要があります。各値をマスキングして3つの部分に分割することでそれを行います。次に、希望する合計が上位ビットを設定することを保証する定数を追加します。次に、マスクをオフに戻すことができます。

b1a = b1 & 0b01001; 
b1b = (b1 >> 1) & 0b01001; 
b1c = (b1 >> 2) & 0b01001; 
b2a = b2 & 0b01001; 
... 
bra = ((b1a + b2a + b3a + b4a + 0b01001) & 0b100100) >> 2; 
brb = ((b1b + b2b + b3b + b4b + 0b01001) & 0b100100) >> 1; 
brc = ((b1c + b2c + b3c + b4c + 0b01001) & 0b100100); 
br = bra | brb | brc;