后继者的高效按位反转

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

为了完整性，这是使用 suggestion in the comments 的模板化 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;
};

Answer 2

这样想：

如果必须手动实施，我将如何实施 I+1？
如何“镜像”上述实现以从 rI 计算 r(I+1)？

将数字增加 1 可以按如下方式完成：

寻找最右边（最靠近 LSB）0。
将 0 更改为 1。
将所有内容设置到 0 的右侧。

现在让我们模仿这种方法：

寻找最左边（最接近MSB）0。
将 0 更改为 1。
将左侧的所有内容设置为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);
}

实现方法有很多种mask_leading_zeroes。这是一个替代的、不太专业的实现，它也应该适用于任何其他无符号类型，但可能更慢。

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 等函数来实现。

后继者的高效按位反转

Efficient bitwise reverse of the successor

c++

performance

bit-manipulation