首页 / 知识

在C中找到最高位

2023-04-14 18:34:00

Find the highest order bit in C

我追求的是可以输入数字的东西，它将返回最高位。我敢肯定有一个简单的方法。下面是示例输出(左边是输入)

1
2
3
4
5
6
7
8
9
10
11

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

摘自Hacker's Delight：

1
2
3
4
5
6
7
8

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

fls简化了许多体系结构上的硬件指令。我怀疑这可能是最简单，最快的方法。

1	1<<(fls(input)-1)

这应该可以解决问题。

1
2
3
4
5
6
7
8
9
10
11
12

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

int ret = 1;

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

return ret;
}

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

像混淆代码？试试这个：

1 <<(int)log2(x)

这次聚会有点晚了，但是鉴于现代的GCC作为编译器，我发现的最简单的解决方案很简单：

1
2
3
4
5
6
7
8
9

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平台上运行)。

Linux内核具有许多这样的便捷位，它们以最有效的方式对许多体系结构进行了编码。您可以在include / asm-generic / bitops / fls.h(和朋友)中找到通用版本，但如果速度至关重要，并且可移植性非常好，请参见include / asm-x86 / bitops.h中使用内联汇编的定义。不。

不断想起低阶位...

1
2
3
4
5
6
7
8
9
10

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

这可以通过现有的库调用轻松解决。

1
2
3

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

Linux手册页提供了有关此功能及其与其他输入类型对应的功能的更多详细信息。

执行此操作的快速方法是通过查找表。对于32位输入和8位查找表，仅需要进行4次迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

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

1
2
3
4
5
6
7

// Note doesn't cover the case of 0 (0 returns 1)
inline unsigned int hibit( unsigned int x )
{
unsigned int log2Val = 0 ;
while( x>>=1 ) log2Val++; // eg x=63 (111111), log2Val=5
return 1 << log2Val ; // finds 2^5=32
}

我非常喜欢的最佳算法是：

1
2
3
4
5
6
7
8

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

它很容易扩展为uint64_t，如下所示：

1
2
3
4
5
6
7
8
9

uint64_t hibit(uint64_t n) {
n |= (n >> 1u);
n |= (n >> 2u);
n |= (n >> 4u);
n |= (n >> 8u);
n |= (n >> 16u);
n |= (n >> 32u);
return n - (n >> 1);
}

甚至是__int128

1
2
3
4
5
6
7
8
9
10

__int128 hibit(__int128 n) {
n |= (n >> 1u);
n |= (n >> 2u);
n |= (n >> 4u);
n |= (n >> 8u);
n |= (n >> 16u);
n |= (n >> 32u);
n |= (n >> 64u);
return n - (n >> 1);
}

此外，跨平台解决方案独立于使用编译器

我想到的一个不错的解决方案是对位进行二进制搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

uint64_t highestBit(uint64_t a, uint64_t bit_min, uint64_t bit_max, uint16_t bit_shift){
if(a == 0) return 0;
if(bit_min >= bit_max){
if((a & bit_min) != 0)
return bit_min;
return 0;
}
uint64_t bit_mid = bit_max >> bit_shift;
bit_shift >>= 1;
if((a >= bit_mid) && (a < (bit_mid << 1)))
return bit_mid;
else if(a > bit_mid)
return highestBit(a, bit_mid, bit_max, bit_shift);
else
return highestBit(a, bit_min, bit_mid, bit_shift);

}

最大位是2的最高幂，因此对于64位数字，它将是2 ^ 63。位移应初始化为位数的一半，因此对于64位，它将是32。

输入数字方法输出