找到C中的最高位

Question

我所追求的是我可以输入一个数字的东西,它将返回最高位.我确信这有一个简单的方法.下面是一个示例输出(左边是输入)

1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 8
9 -> 8
...
63 -> 32

Answer 1

来自Hacker's Delight:

int hibit(unsigned int n) {
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

此版本用于32位整数,但逻辑可以扩展到64位或更高.

Answer 2

fls最底层的是许多架构的硬件指令.我怀疑这可能是最简单,最快速的方式.

1<<(fls(input)-1)

Answer 3

这应该可以解决问题.

int hob (int num)
{
    if (!num)
        return 0;

    int ret = 1;

    while (num >>= 1)
        ret <<= 1;

    return ret;
}

滚刀(1234)返回1024
滚刀(1024)返回1024
滚刀(1023)返回512

Answer 4

像混淆代码？试试这个:

1 <<(int)log2(x)

Answer 5

这个聚会有点晚了，但我找到的最简单的解决方案，考虑到现代 GCC 作为编译器很简单：

static inline int_t get_msb32 (register unsigned int val)
{
  return 32 - __builtin_clz(val);
}

static inline int get_msb64 (register unsigned long long val)
{
  return 64 - __builtin_clzll(val);
}

它甚至相对便携（至少它可以在任何 GCC 平台上运行）。

Answer 6

想到不断删除低位...

int highest_order_bit( int x )
{
    int y = x;
    do { 
        x = y;
        y = x & (x-1); //remove low order bit
    }
    while( y != 0 );
    return x;
}

Answer 7

linux 内核有许多这样的方便的位元，以最有效的方式为许多体系结构编码。您可以在include/asm-generic/bitops/fls.h（和朋友）中找到通用版本，但如果速度至关重要，并且可移植性很重要，请参阅include/asm-x86/bitops.h以获取使用内联汇编的定义不是。

Answer 8

现有的库调用可以很容易地解决这个问题.

int highestBit(int v){
  return fls(v) << 1;
}

Linux手册页提供了有关此函数的更多详细信息以及其他输入类型的对应函数.