求整数的下一个 2 次方的以 2 为底的对数

Question

我已经运行研究了很多，看来应该有更好的方法来做到这一点。我想使用 bit twiddling 来完成等同于以下内容的操作：

uint8_t nextlog(uint32_t n) {
  return (uint8_t) ceil(log2(n)) + 1;
}

用法示例：

nextlog(0) -> undefined
nextlog(1) == 1
nextlog(3) == 3  // 0b11 -{next power 2}-> 0b100 -{log2+1}-> 3
nextlog(32) == 6 // 0b00100000 -{log2+1}-> 6
nextlog(71) == 8 // 0b01000111 --> 0b10000000 -> 8

我想出的最好办法是结合著名的 bit twiddling hacks 参考中的 "Round up to the next highest power of 2" 和 "Finding integer log base 2 of an integer"。我想还值得注意的是 __builtin_clz 可以帮助完成问题的后半部分。

Answer 1

你想要 32 - clz(x)，尽管你的说法与此相反。

你声称 log₂ 0b100 是 3，这是你的数学错误。正确答案是 2.

它不在 "bit twiddling hacks" 页面中，但我找到了这个：

int clz(uint32_t x) {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return 32 - popcount(x);
}

int popcount(uint32_t x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    return (((x + (x >> 4)) & 0x0f0f0f0f) * 0x01010101) >> 24;
}

请注意，与 x86 上的 ffs 相比，我确信性能有些糟糕。

参见：http://aggregate.org/MAGIC/#Leading%20Zero%20Count

Answer 2

根据@Mark Dickinson 的评论，单分支的明显解决方案如下：

uint8_t nextlog(uint32_t n) {
  if (n == 1) return 1;
  return 33 - __builtin_clz(n - 1);
}

求整数的下一个 2 次方的以 2 为底的对数

Find the base 2 logarithm of the next power of 2 of an integer

c

bit-manipulation