寻求二进制整数最左侧置位的位运算计算公式

当然存在纯位运算的公式可以定位二进制整数的最左侧置位，下面是最实用的实现思路及公式：

高位扩散法（纯位运算公式） #

原理 #

通过右移和按位或操作，将原数最左侧的1逐步扩散到所有低位，得到一个从最高位到最低位全为1的数；随后用这个全1数减去右移一位后的结果，即可得到仅保留最左侧1的数值。

针对16位整数的公式 #

y = (x | x >> 1 | x >> 2 | x >> 4 | x >> 8) - ((x | x >> 1 | x >> 2 | x >> 4 | x >> 8) >> 1)

示例验证 #

输入 x = 0000101101011000：

1. 执行扩散操作：x | x>>1 | x>>2 | x>>4 | x>>8 得到 0000111111111111；
2. 将扩散结果右移一位：0000011111111111；
3. 相减后得到：0000111111111111 - 0000011111111111 = 0000100000000000，即目标结果y。

适配不同位数 #

• 32位整数：只需增加右移16位的操作，公式为：

y = (x | x>>1 | x>>2 | x>>4 | x>>8 | x>>16) - ((x | x>>1 | x>>2 | x>>4 | x>>8 | x>>16) >> 1)

• 64位整数则继续增加右移32位的操作，以此类推。

二分定位法（分支型位运算实现） #

如果需要通过分支判断逐步定位，也可以用二分思想：

1. 从最高位区间开始判断是否存在置位；
2. 逐步缩小范围，最终定位到最左侧1的位置并构造结果。

16位整数的代码实现 #

uint16_t get_leftmost_set_bit(uint16_t x) {
    if (x == 0) return 0;
    uint16_t res = 0;
    if (x >= (1U << 12)) res = 1U << 12;
    else if (x >= (1U << 11)) res = 1U << 11;
    else if (x >= (1U << 10)) res = 1U << 10;
    else if (x >= (1U << 9)) res = 1U << 9;
    else if (x >= (1U << 8)) res = 1U << 8;
    else if (x >= (1U << 7)) res = 1U << 7;
    else if (x >= (1U << 6)) res = 1U << 6;
    else if (x >= (1U << 5)) res = 1U << 5;
    else if (x >= (1U << 4)) res = 1U << 4;
    else if (x >= (1U << 3)) res = 1U << 3;
    else if (x >= (1U << 2)) res = 1U << 2;
    else if (x >= (1U << 1)) res = 1U << 1;
    else res = 1U << 0;
    return res;
}

这个方法通过判断x与各次幂的大小关系，直接返回对应位的数值，同样基于位运算实现。

内容的提问来源于stack exchange，提问作者Mojtaba Valizadeh