继任者的高效逐位反转

Question

我发现的逐位反转积分类型的最有效方法是：

template <class NT = std::size_t>
NT reverseBits(NT num)
{
NT count = sizeof(num) * 8 - 1;
NT reverse_num = num;
num >>= 1;
while(num) {
reverse_num <<= 1;
reverse_num |= num & 1;
num >>= 1;
count--;
}
reverse_num <<= count;
return reverse_num;
}

但给定一些整数I，我已经得到了结果rI = reverseBits(I):

有没有一种方法可以直接从rI获得reverseBits(I+1)，而无需再次调用reverseBits(或具有同等复杂性的东西(？

Answer 1

这样想：

• 如果必须手动实现I+1，我将如何实现它
• 我怎么能"镜像；从rI计算r(I+1)的上述实现

通过1递增一个数字可以按如下方式进行：

1. 查找最右边(最靠近LSB(的0
2. 将该0更改为1
3. 将所有内容向右设置为0

现在让我们镜像这种方法：

1. 查找最左边的(最接近MSB(0
2. 将该0更改为1
3. 将所有内容设置为左侧到0

以下是unsigned ints的基本实现。

// sets all bits except for leading zeroes
// example 0001010011 => 0001111111
unsigned int mask_leading_zeroes(unsigned int n) {
// assumes that int is at most 64 bits wide
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return n;
}
int main() {
unsigned int rI = 12345;
unsigned int mask = mask_leading_zeroes(~rI);
unsigned int rI1 = (mask ^ (mask >> 1)) | (rI & mask);
}

实现CCD_ 19的方法有很多。这里有一个替代的、不太专业的实现，它也应该与任何其他无符号类型一起使用，但可能较慢。

unsigned int mask_leading_zeroes(unsigned int n) {
unsigned int shift = 1;
unsigned int old;
do {
old = n;
n |= n >> shift;
shift <<= 1;
} while (old != n);
return -n;
}

您还可以考虑使用__builtin_ffs之类的函数来实现这一点。

Answer 2

对于完整性，这是使用注释中建议的模板化c++17版本，对4字节和8字节单词进行了部分专门化

#include <climits>
#include <type_traits>
// source: https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel
template <class NT = std::size_t, std::enable_if_t< (sizeof(NT) > 8), int > = 0>
NT uFastBitReverse(NT v) {
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
NT mask = ~0;
while ((s >>= 1) > 0)
{
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
return v;
};
// source: https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel
template <class NT, std::enable_if_t< sizeof(NT) == 4, int > = 0 >
NT uFastBitReverse(NT v) {
//std::cout << " in the 4 byte specialization " << std::endl;
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
v = ( v >> 16             ) | ( v               << 16);
return v;
};
template <class NT, std::enable_if_t< sizeof(NT) == 8, int > = 0 >
NT uFastBitReverse(NT v) {
//std::cout << " in the 8 byte specialization " << std::endl;
v = ((v >> 1) & 0x5555555555555555) | ((v & 0x5555555555555555) << 1);
v = ((v >> 2) & 0x3333333333333333) | ((v & 0x3333333333333333) << 2);
v = ((v >> 4) & 0x0F0F0F0F0F0F0F0F) | ((v & 0x0F0F0F0F0F0F0F0F) << 4);
v = ((v >> 8) & 0x00FF00FF00FF00FF) | ((v & 0x00FF00FF00FF00FF) << 8);
v = ((v >> 16)& 0x0000FFFF0000FFFF) | ((v & 0x0000FFFF0000FFFF) << 16);
v = ( v >> 32                     ) | ( v                       << 32);
return v;
};