如何在C++中高效获取对应二进制位数的最大全1整数？

你的需求是给定一个正整数，生成与其二进制位数相同的全1整数（比如22(10110)得到31(11111)）。你当前使用的代码依赖浮点运算，存在效率低、精度风险和溢出隐患，这里提供几种更高效的位运算实现方案：

原代码的问题 #

你当前的实现：

int A = 22;  // 10110
int max = pow(2, (int) log2(A) + 1) - 1;  // returns 31 (11111)

存在以下问题：

• 浮点运算效率低：pow和log2都是浮点操作，比位运算慢得多；
• 精度风险：对于某些整数，log2的浮点计算可能出现精度误差，导致转换为int后数值偏差；
• 溢出问题：当A接近int最大值时，pow(2, ...)会超出int范围，导致未定义行为。

高效实现方案 #

方案1：无循环位运算（最优，O(1)时间） #

通过逐步将最高位的1扩散到所有低位，最终得到全1的结果，适用于32位无符号整数：

unsigned int max_all_ones(unsigned int A) {
    if (A == 0) return 0; // 处理0的特殊情况
    A |= A >> 1;
    A |= A >> 2;
    A |= A >> 4;
    A |= A >> 8;
    A |= A >> 16;
    return A;
}

原理：

• 第一次A |= A >> 1：将最高位的1扩散到相邻的低位；
• 后续移位或操作，逐步把1扩散到所有更低的位，最终得到与原数位数相同的全1整数。
• 示例：A=8(1000) → A|=A>>1得到1100 → A|=A>>2得到1111，后续操作无变化，返回15。

方案2：利用编译器内置函数（适用于GCC/Clang） #

通过计算前导零个数快速得到二进制位数，再生成全1整数：

unsigned int max_all_ones(unsigned int A) {
    if (A == 0) return 0;
    // __builtin_clz 返回32位无符号数的前导零个数
    int bit_count = 32 - __builtin_clz(A);
    return (1U << bit_count) - 1;
}

说明：

• 64位整数可使用__builtin_clzll，对应64 - __builtin_clzll(A)；
• 该方法同样是O(1)时间，依赖编译器内置指令，效率极高。

方案3：循环移位实现（兼容性好，适用于所有编译器） #

通过循环将结果逐步左移并置1，直到结果不小于原数：

unsigned int max_all_ones(unsigned int A) {
    if (A == 0) return 0;
    unsigned int result = 1;
    while (result < A) {
        result = (result << 1) | 1;
    }
    return result;
}

说明：

• 循环次数等于原数的二进制位数，对于32位整数最多循环32次，效率也远高于浮点运算；
• 兼容性最好，不依赖任何编译器特性。

测试示例 #

• 1000(8) → 1111(15)
• 1010(10) → 1111(15)
• 100001(33) → 111111(63)
• 111(7) → 111(7)

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