带条件的逻辑与运算符

Question

给定阈值 T 和一组位图，我想创建一个结果位图 "br"，这样 "br" 的第 i 位仅当 i'在 >=T 个位图中第 bit 被设置为 1。

我将尝试用一个例子来说明我的问题：假设我们有 4 个位图（等长）并且 T=3：

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

然后我生成的位图 br = (00010) - 因为在 >=3 个位图中只有第 4 位设置为 1。如果 T=2，则 br = (10110)。

一种简单的方法是遍历每个位图并保留一个向量，该向量在第 i 个索引中存储位 'i' 的计数。之后，可以迭代这个 "count" 向量。

另一种方法（我认为）是实现修改后的逻辑 AND 运算符，这样，在生成的位图中，如果第 i 位在 >=T 位置设置为 1，则它设置为 1。

还有其他有效的方法吗？我正在使用 C++ 和 EWAHBoolArray (https://github.com/lemire/EWAHBoolArray) 库。目前，他们不具备在多个位图之间进行 AND 运算的能力。非常感谢任何回复！

Answer 1

您可以通过一些操作和添加来完成此操作。您实际上是在尝试获取各个位的总和。为了通过正常加法做到这一点，您需要为每列可以获得的最大总和腾出空间。您可以通过使用掩码将每个值分成 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;

带条件的逻辑与运算符

Logical AND operator with a condition

c++

bit-manipulation

bitmap

bitwise-operators