找到C中的最高位

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

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

erickson.. 83

来自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位或更高.

1> erickson..：

---

来自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位或更高.

---

@alveko虽然XOR可以比晶体管/门级的减法更快地实现,但它们在大多数现代CPU上需要相同的时钟周期数

---

为了直观起见，此操作将MSB向右“传播”，以便0b100010变为0b111111，然后向右移0b011111并减去，得出0b100000。

2> Fabian..：

---

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

1<<(fls(input)-1)

---

显然是最好的答案。我不知道为什么所有这些网站都像是点点滴滴的骇客，而这些网站如此专注​​于减少针对此类问题的操作次数，甚至没有提及这一点。

---

@jww是正确的。`fls（0）`-> 0，未定义`<<`的rhs为负。在我的辩护中，问题空间中未提及；-)

3> Kyle Cronin..：

---

这应该可以解决问题.

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

    int ret = 1;

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

    return ret;
}

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

---

我的回答更好.没有循环!

---

对于GCC,更好的函数是__builtin_clz(v) - 它返回前导(二进制)零的数量,因此您可以通过32-clz(num)(或64-clzll(num)获得最高位位置) 64位)

4> dmityugov..：

---

像混淆代码？试试这个:

1 <<(int)log2(x)

---

如果你想在FPU上关闭作业,当然.:)

---

在数学上是正确的,但这可能比按位运算慢得多.

---

如果你把它加到第一位,那么数字的指数部分就会告诉你顺序.

---

注意数字表示形式。此配方适用于正32位整数。但是`std :: log2（）`为否定参数返回`nan`，而`int（nan）`的计算结果为'0x80000000`，这是最大的负整数。对于g ++ 7.3，可以观察到这一点，但恐怕这是不可移植的。下一个问题是舍入错误。当您输入64位数字时，一切正常，直到2 ^ {48} -1。但是对于2 ^ {49} -1，配方返回2 ^ {49}。

5> dharga..：

---

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

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

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

---

实际上,ffs返回最低位.

---

@Ragnar，如果您采用这种方式，请使用（CHAR_BIT * sizeof（long long）-__builtin_clzll（v）`，但我不认为此公式很容易携带，因此不需要。