时间戳

首页 > 解决方案 > 用二分法获取最左边的位

c - 用二分法获取最左边的位

问题描述

我试图了解以下代码是如何工作的，但我无法理解这里发生了什么：

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

确实，我有两个问题，首先：如果是大小比较，是否不应该按此顺序创建蒙版？

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

那么，for循环中的程序是什么？通过我的研究，我理解&了>>它们的按位行为，但是这里的诀窍是什么，因为我猜它只是并且只是比较，mask[0]因为它需要相同的大小。

标签： cbit-manipulationbitbit-shift

解决方案

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

它基本上在每个循环中将机器字减半。这样做的好处是，您总是在 5 步内计算 MSB，无论您输入什么 32 位模式，因为二进制搜索具有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 集快得多。

推荐阅读