在C语言中找到最高位的比特位

Question

我需要的东西是可以输入数字并返回最高位的东西，我相信有一个简单的方法。以下是一个示例输出（左边是输入）

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

- Harley

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位或更高。

- erickson

---

最后一行使用异或（XOR）更有效率，不是吗？n ^ (n >> 1) - alveko

@alveko，尽管在晶体管/门电平上实现异或比减法更快，但它们在大多数现代CPU上需要相同数量的时钟周期。 - Drew McGowen

少一些晶体管，更高的效率，少一些热量，更多循环 :) - Steazy

为了便于理解，这个过程将最高有效位向右“扩展”，使得0b100010变成0b111111，然后对0b011111进行右移并减去它，得到0b100000。 - Warty

在这种情况下，难道它不会返回0xFFFFFFFF - 0x7FFFFFFF = 0x80000000吗？请解释一下您看到的错误在哪里。 - erickson

Answer 2

fls在许多架构上都会转化为硬件指令。我认为这可能是最简单、最快速的方法。

1<<(fls(input)-1)

- Fabian

---

显然是最佳答案。我想知道为什么所有那些像位操作技巧这样专注于减少此类问题操作数量的网站，甚至都没有提到这一点。 - Cimbali

如果一个位没有被设置会发生什么？如何通过负数进行左移位操作？我认为这是未定义的行为。 - jww

@jww 没错。fls(0) -> 0，导致 << 的右操作数为负数，这是未定义的。为了辩护，问题空间中没有说明这一点；-) - Fabian

这应该是被接受的答案。我很高兴我继续滚动！ - krs013

@krs013 - 我不知道。如果我没记错的话，它在 POSIX 之外是不可用的。 - AturSams

Answer 3

这应该能解决问题。

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

    int ret = 1;

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

    return ret;
}

hob（1234）返回1024
hob（1024）返回1024
hob（1023）返回512

- Kyle

---

要使其与零一起工作，只需添加： while (num >>= 1 && num) - Paul Hargreaves

实际上，您需要一个 if 来检查零。由于返回值 ret 从1开始增长，此算法将无法使其命中输入为0的答案。 - Kyle Cronin

我的答案更好。没有循环！ - erickson

一个好的编译器会展开循环以提高性能。如果它在没有循环的情况下确实更快，则可以实现更高的性能。 - davenpcj

对于GCC编译器而言，更好的函数是__builtin_clz(v) -- 它返回前导（二进制）零的数量，因此您可以通过32-clz(num)（或64-clzll(num)适用于64位）来获取最高有效位的位置。 - Soren

Answer 4

喜欢混淆的代码吗？试试这个：

1 << ( int) log2( x)

- dmityugov

---

我喜欢这个解决方案，但它有点过于混淆。尽管如此，它仍然是最紧凑的解决方案之一。 - Harley Holcombe

如果你想把这项工作交给FPU，那当然可以。 :) - Jeffrey Hantin

数学上是正确的，但这可能比位运算要慢得多。 - mateusza

如果您首先将其转换为双精度浮点数，该数字的指数部分将很容易地告诉您顺序。 - Calmarius

注意数字表示方式。这个方法适用于32位正整数，但是std::log2()对于负参数返回nan，而int(nan)求值为0x80000000，即最大的负整数。在g++7.3中可以观察到这一点，但我担心这不是可移植的。下一个问题是舍入误差。当输入64位数字时，一切工作都很好直到2^{48}-1。但对于2^{49}-1，该方法返回2^{49}。 - hermannk

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平台上工作）。

- Kean

---

也被clang支持。 - Nate Eldredge

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;
}

- nlucaroni

Answer 7

Linux内核有许多方便的位操作函数，它们都是以最高效的方式编写，支持多种架构。你可以在include/asm-generic/bitops/fls.h（等）中找到通用版本，但如果速度至关重要且可移植性不是问题，则还应查看include/asm-x86/bitops.h，其中使用了内联汇编定义。请注意保留HTML标记。

- theorbtwo

---

Linux内核中的位操作存在未定义行为。我不建议任何人在不了解自己在做什么或没有完整的自测功能集的情况下使用它（或复制/粘贴例程）。 - jww

Answer 8

这可以通过现有的库函数轻松解决。

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

Linux man页面提供了有关此函数及其其他输入类型对应项的更多详细信息。

- dharga

---

ffs函数返回最低位的位置。 - Joel Rein

@Soren 更好的做法是使用 (8*sizeof(long long) - __builtin_clzll(v)) - Ragnar

@Ragnar，如果你要这样做，请使用(CHAR_BIT*sizeof(long long) - __builtin_clzll(v)，但我认为这种表达方式不够通用，不需要这样做。<limits.h> - Jasen

这不是反过来了吗？应该是 1UL << fls(v)。 - Peter Cordes

在Ubuntu 20.04上没有这个命令的手册，而且在glibc中似乎也找不到。据我所知，这是FreeBSD的发明。 - Nate Eldredge

Answer 9

通过查找表的方式可以快速完成此操作。对于32位输入和8位查找表，仅需要4次迭代：

int highest_order_bit(int x)
{
    static const int msb_lut[256] =
        {
            0, 0, 1, 1, 2, 2, 2, 2, // 0000_0000 - 0000_0111
            3, 3, 3, 3, 3, 3, 3, 3, // 0000_1000 - 0000_1111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_0000 - 0001_0111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_1000 - 0001_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_0000 - 0010_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_1000 - 0010_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_0000 - 0011_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_1000 - 0011_1111

            6, 6, 6, 6, 6, 6, 6, 6, // 0100_0000 - 0100_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0100_1000 - 0100_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_0000 - 0101_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_1000 - 0101_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_0000 - 0110_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_1000 - 0110_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_0000 - 0111_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_1000 - 0111_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1000_0000 - 1000_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1000_1000 - 1000_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_0000 - 1001_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_1000 - 1001_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_0000 - 1010_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_1000 - 1010_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_0000 - 1011_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_1000 - 1011_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1100_0000 - 1100_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1100_1000 - 1100_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_0000 - 1101_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_1000 - 1101_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_0000 - 1110_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_1000 - 1110_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_0000 - 1111_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_1000 - 1111_1111
        };

    int byte;
    int byte_cnt;

    for (byte_cnt = 3; byte_cnt >= 0; byte_cnt--)
    {
        byte = (x >> (byte_cnt * 8)) & 0xff;
        if (byte != 0)
        {
            return msb_lut[byte] + (byte_cnt * 8);
        }
    }

    return -1;
}

- Ben Lever

---

速度最快的执行，但打字不一定最快 ;) - kenny

Erickson的答案更快...它使用更少的内存，因此它更具缓存效率。 - Calmarius

Answer 10

如果您不需要便携式解决方案，并且您的代码在x86兼容的CPU上执行，则可以使用Microsoft Visual C/C++编译器提供的_BitScanReverse()内置函数。它映射到BSR CPU指令，该指令返回最高位设置。

- Igor Levicki