gpt4 book ai didi

c - 用二分法得到最左边的位

转载 作者:行者123 更新时间:2023-12-04 01:07:42 25 4
gpt4 key购买 nike

我试图了解以下代码的工作原理,但我无法理解此处发生的情况:

uint32_t mask[5] = { 0xFFFF0000, 0xFF00, 0xF0, 0b1100, 0b10 };
uint32_t shift[5] = { 16, 8, 4, 2, 1 };

char first_bit_left_dichotomy(uint32_t M) {
char pos = 0;
char i;
for (i = 0; i <= 4; i++) {
if (M & mask[i]) {
M = M >> shift[i];
pos += shift[i];
}
}
return pos;
}

确实,我有两个问题,首先:如果是尺寸比较,不应该按此顺序创建 mask 吗?

uint32_t mask[5] = { 0b100, 0b1100, 0xF0, 0xFF00, 0xFFFF0000 };

请问for循环中的程序是什么?通过我的研究,我了解 &>>> 以及它们的按位行为,但是这里有什么诀窍因为我只是猜测它并且只与 mask[0] 因为它需要相同的大小。

最佳答案

该算法遵循“分而治之”原则,通过对或位模式应用二进制搜索来找出最高有效位。

基本上每个周期都会将机器字减半。这样做的好处在于,无论您输入什么 32 位模式,您始终可以在 5 步内计算出 MSB,因为二进制搜索具有 O(log2(n)) 特性。

让我们选择两个极端来说明行为,并假设单词 0x00000001 作为算法的输入。我们希望它输出 0。基本上发生的是:

0x00000001 & 0xFFFF0000 = 0x00000000
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0xFF00 = 0x0000
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0xF0 = 0x00
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0b1100 = 0x00
-> We don't shift anything, M=0x00000001, pos=0

0x00000001 & 0b10 = 0b0
-> We don't shift anything, M=0x00000001, pos=0

所以我们在 5 步内得到了结果。想象一下,现在从左到右做一个循环尝试同样的事情:需要 31 步才能得到结果。

此外,单词 0x8FFFFFFF 作为算法的输入需要 5 个步骤才能获得预期结果 31:

0x8FFFFFFF & 0xFFFF0000 = 0x8FFF0000
-> We shift by 16 right, M=0x8FFF, pos=16

0x8FFF & 0xFF00 = 0x8F00
-> We shift by 8 right, M=0x8F, pos=24

0x8F & 0xF0 = 0x80
-> We shift by 4 right, M=0x8, pos=28

0x8 & 0b1100 = 0x8
-> We shift by 2 right, M=0x2, pos=30

0x2 & 0b10 = 0x2
-> We shift by 1 right, M=0x1, pos=31

如您所见,这两个极端都使我们完成了这 5 个步骤。由于循环展开、指令的条件执行等。这应该运行得非常快,至少比在循环中从左到右查找 MSB 集要快得多。

关于c - 用二分法得到最左边的位,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65875858/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com