有人知道上/下转换位数组的算法吗?

即:当分辨率为1/16时:

每1位= 16位。 (从低分辨率到高分辨率)

1010 -> 1111111111111111000000000000000011111111111111110000000000000000

反向,16位= 1位(高分辨率到低分辨率)
1111111111111111000000000000000011111111111111110000000000000000 -> 1010

现在我正在一点一点地循环,这效率不高。使用整个64位字会更好,但是当无法通过分辨率将其一分为二时会遇到问题(某些位可能会溢出到下一个字)。

C++:
std::vector<uint64_t> bitset;

C:
uint64_t *bitset = calloc(total_bits >> 6, sizeof(uint64_t)); // free() when done

使用以下命令访问
const uint64_t idx = bit >> 6;
const uint64_t pos = bit % 64;

const bool value = (bitset[idx] >> pos) & 1U;

并设置/清除:
bitset[idx] |= (1UL << pos);
bitset[idx] &= ~(1UL << pos);

并使用完整的64位字完成具有相同分辨率的两个位集的OR(或AND / XOR / AND / NOT):
bitset[idx] |= source.bitset[idx];

我正在处理足够大的位集(2+十亿位),因此我正在寻找循环中的任何效率。我发现优化循环的一种方法是使用__builtin_popcountll检查每个单词,然后在循环中跳过:
for (uint64_t bit = 0; bit < total_bits; bit++)
{
   const uint64_t idx = bit >> 6;
   const uint64_t pos = bit % 64;

   const uint64_t bits = __builtin_popcountll(bitset[idx]);

   if (!bits)
   {
      i += 63;
      continue;
   }
   // process
}

我在寻找算法/技术而不是代码示例。但是,如果您有共享的代码,我不会拒绝。任何学术研究论文也将不胜感激。

提前致谢!

最佳答案

分辨率是否始终在1/2到1/64之间?甚至是1/32?因为如果需要很长的序列,则可能需要更多的循环嵌套,这可能会导致速度变慢。

您的序列总是很长(几百万个位)还是最大,但是通常您的序列更短?从高分辨率到低分辨率时,您可以假定数据有效还是无效。

这里有一些技巧:

uint64_t one = 1;
uint64_t n_one_bits = (one << n) - 1u; // valid for 0 to 63; not sure for 64

如果您的序列太长,则可能要检查n是否为2的幂,并针对这些情况使用更优化的代码。

您可能会在这里找到其他有用的技巧:

https://graphics.stanford.edu/~seander/bithacks.html

因此,如果您的分辨率为1/16,则不需要循环单个16位,但是可以一次检查所有16位。然后,您可以一次又一次地对下一组重复。

如果该数字不是64的除数,则每次越过64位边界时,都可以适当地移位位。假设您的分辨率为1/5,那么您可以处理60位,然后将剩余的4位移位并与后面的60位合并。

如果可以假设数据是有效的,那么您甚至不需要移动原始数字,因为您可以每次选择适当的位的值。

关于c++ - C/C++位阵列分辨率转换算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/52636890/

10-12 00:39
查看更多