这个功能的行为是什么？(2的力量)

Question

我有下一个功能:

static inline int nextPowerOfTwo(int n) {
    n--;

    n = n >>  1 | n;
    n = n >>  2 | n;
    n = n >>  4 | n;
    n = n >>  8 | n;
    n = n >> 16 | n;
    //  n = n >> 32 | n;    //  For 64-bit ints

    return ++n;
}

但我不知道他的行为是什么(功能输出 - 功能 - )

我不知道每一行的行为是什么(每行后的n值).

有人可以解释一下吗？

Answer 1

该代码来自Bit Twiddling Hacks

最高可达2的最高功率

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

[...]

它的工作原理是将最高设置位复制到所有低位,然后再加1,这会导致将所有低位设置为0并将超出最高设置位的1位设置为1.如果原始数字为1 2的幂,然后减少将它减少到一个,以便我们四舍五入到相同的原始值.

16,32和64位的明显版本:

#include <stdint.h>

uint16_t round_u16_to_pow2(uint16_t v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v++;
    return v;
}

uint32_t round_u32_to_pow2(uint32_t v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;
}

uint64_t round_u64_to_pow2(uint64_t v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v |= v >> 32;
    v++;
    return v;
}