垂直按位计数（同一位置上的总和）

Question

有什么有效的方法可以在多个变量的相同位置上计算 1 个吗？计数函数应该用相应位数的总和填充数组。例如，我们有以下三个变量（为了简单起见，我使用 8 位变量）：

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

我找到了很多求和整个单个变量的解决方案，但没有解决上述问题。

Answer 1

确定变量中特定位置是否为 1 比进行正常人口计数要简单得多。

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

... 只需在所有输入上调用它并在每次 returns 为真时增加一个计数器。简单

Answer 2

这段小代码完全符合您的要求。您可以通过一个小查找数组轻松扩展它以支持 N 个变量。注意双非操作的使用。就是拖拽输出为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 3

将每个 uint8_t 二进制数字扩展为 uint32_t 十六进制数字和 "add them up"。只要不超过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()。戴上你的八进制帽子

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

为了纯粹的速度，您可以通过将 8 个字节打包在一个 64 位累加器中来并行处理 8 个计数。

使用 256 个 64 位条目初始化查找 -table 将原始 8 位扩展为字节。（例如，条目 Lookup[0x17u] 映射到 0x0000000100010101ul。）

计数只是用

Acc+= Lookup[Byte];

您可以通过在 64 位上映射一个 8 字节的数组来检索各个计数器。

在发生溢出之前，您可以执行256次累加；如果您需要更多，请以 256 个块为单位累加，并在处理完一个块后，将计数传输到更大的累加器。

如果你需要累加不超过16次，32位累加器就足够了。

垂直按位计数（同一位置上的总和）

Vertical bitwise COUNT (sum of ones on the same position)

c++

c

algorithm

bit-manipulation