c++ - C/C++ 位数组分辨率变换算法
问题描述
有人知道上/下转换位数组的任何算法吗?
即:当分辨率为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);
以及两个相同分辨率的位集的 OR(或 AND/XOR/AND/NOT)是使用完整的 64 位字完成的:
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 位组合。
如果您可以假设数据是有效的,那么您甚至不需要移动原始数字,因为您每次都可以选择适当位的值。
推荐阅读
- javascript - 试图将数组作为键值对放入对象中。没有得到想要的输出?
- php - 从存储在变量 PHP 中的字符串调用“两个”函数
- sql - 删除 SQL 中的特定列数据而不删除整行
- php - 通过直接链接将文件下载到服务器
- mysql - 我应该如何在 asp.net 中的 1 个中继器控件中显示 2 个表中的数据?
- reactjs - 无法发送 request.data 并获得 api 响应?
- angular - Uncaught (in promise) TypeError: Document not active
- sql - Delete certain values inside a column
- go - Multiple replicas accessing a cache in kubernetes
- javascript - 如何在茉莉业力中模拟翻译 I18n?