比较两个整数列表中每个位置的比特数

Question

我遇到了一个问题，可能可以通过重新排列我的算法来解决，但这很有趣，也许你们中的某个人有一个好主意。

情况如下：我有两个无符号长整数列表，两个列表的大小相同，如果这有帮助，您可以假设这个大小是2的幂。这些列表的大小通常在几百范围内。现在，我想计算一个整数，该整数在第一个列表比第二个列表有更多的设置位的每个位置上都有一个设置位。

速度就是一切。

Simplified example:

list1   list2

1010    0101
1111    0000
1100    0011
1010    0101

result: 1010
because of 4>0, 2<=2, 3>1, 1<=3

编辑：数据的替代安排会导致位向量中包含现在某个位置的位于多个向量中。在这种情况下，我可以使用比特计数算法，然后进行比较，这将在两个列表的每64位中少于30次操作。基本上，我有一个位矩阵，可以使用列或行的位向量。

额外结构：John Willemse的评论让我意识到我可以计算第三个列表，这样这三个列表就会按位互补。尽管我不知道这有何帮助。

- BlindKungFuMaster

---

如果您当前的实现有效，并且正在寻找替代方案，则（1）概述当前算法，（2）删除标签 [tag:c] 并添加 [tag:algorithm]。 - Jongware

一个将数字映射到其二进制位为 1 的数量的查找表怎么样？这可以用于最多 16 位数字，具体取决于空间限制等因素。请告诉我们更多关于这个问题的信息。 - Jabberwocky

我还没有实现，我仍在思考如何构建数据结构。如果我以某种方式构建数据结构，这个问题就会出现，这可以节省算法的一部分时间，但似乎会在这里浪费时间。 - BlindKungFuMaster

你的列表有多长？列表中的数字范围是什么？ - Jabberwocky

我的列表的长度在几百个的范围内。这些数字实际上不是真正的数字，它们是位向量，一切皆有可能。 - BlindKungFuMaster

Answer 1

你可以使用转置计数器来完成 - 不是为数据的每个位位置设置一个int，而是为每个计数的位位置设置一个uint。希望你不需要太多的位。

然后，您可以按照位向量定义的方式执行加法/减法，其中每个“位”实际上是该位位置在所有计数中的一个切片。

也许这听起来有点模糊，所以让我们直接开始吧：（未经测试）

// add in item from list2
carry0 = count0 & item2;
count0 ^= item2;
carry1 = count1 & carry0;
count1 ^= carry0;
.. etc for however many bits you need in your counters
// subtract item from list1
borrow0 = ~count0 & item1;
count0 ^= item1;
borrow1 = ~count1 & borrow0;
count1 ^= borrow0;
.. etc

结果是符号，因此您正在使用的是最后一个计数器。

---

或者，完全不同的方法：也许您可以使用 int 的子字段，采用 SWAR 风格。这仅适用于字段较小或您不需要太多字段的情况，因为空间有限。使用 4 位项并不那么糟糕，使用 uint32_t 可以提供 4 个计数器，范围从 -128 到 127，这可能足够了（最终差异必须在该范围内，中间结果可以安全地包装）。无论如何，它是如何工作的，您可以使用查找表或 pdep（未经测试）来展开比特。

uint32_t spread = _pdep_u32(item, 0x01010101);
// or
uint32_t table[] = {
    0x00000000, 0x00000001, 0x00000100, 0x00000101,
    0x00010000, 0x00010001, 0x00010100, 0x00000101,
    0x01000000, 0x01000001, 0x01000100, 0x00000101,
    0x01010000, 0x01010001, 0x01010100, 0x01010101 };
uint32_t spread = table[item];

然后进行SWAR加法或减法，但可以进行一些优化，因为您知道它们是增量、减量或不变的（未经测试）。

// add in spread item 2
uint32_t H = 0x80808080;
count = ((count &~H) + sp2) ^ (count & H);
// subtract spread item 1
count = ((count | H) - sp1) ^ (~count & H);

结果是每个子字段的符号，很容易提取但压缩起来很麻烦（除非你有 pext）。

- harold

Answer 2

这可能不是最有效的解决方案，但这是我首先想到的解决方案，其时间复杂度为O(n)。

int list1[4] = {10, 15, 12, 10};
int list2[4] = {5, 0, 3, 5};

int i, j;
int result = 0;
int num_bits = 4;
int num_elements = 4;

for (i = num_bits - 1; i >= 0; i--)
{
    int bit_pos_ans = 0;
    for (j = 0; j < num_elements; j++)
    {
        /* This works by adding the 1s in list1, and subtracting the 1s in list 2 */
        bit_pos_ans += (((list1[j] >> i) & 0x1) - ((list2[j] >> i) & 0x1));
    }

    /* If there are more 1s in list1 and list2, then this bit position is a 1. */
    if (bit_pos_ans > 0)
    {
        result += 1;
    }

    /* Only shift if this is not calculating bit position 0 */
    if (i > 0)
    {
        result <<= 1;
    }
}

printf("%d", result);

- Matt Taylor