补码系统中x&=(x-1)删最右1位原理及高效bitcount实现问询

一、严谨解释x & (x-1)删除最右侧1位的原因 #

在补码数系统（无符号数的运算同样遵循补码规则）中，可通过二进制位的变化逻辑推导：

• 设x的二进制表示中，最右侧的1位位于第k位（从0开始计数，最低位为第0位），那么x的二进制形式可表示为：...a 1 0 0 ... 0，其中a代表任意二进制位，第k位为1，右侧跟着k个0。
• 执行x-1操作时，第k位的1会被借位变为0，右侧所有的0都会因借位变为1，更高位的位保持不变，因此x-1的二进制形式为：...a 0 1 1 ... 1。
• 对x和x-1执行按位与（&）操作：
  • 第k位：1 & 0 = 0
  • 第k位右侧的所有位：0 & 1 = 0
  • 第k位左侧的所有位：a & a = a（保持原有值不变）
    最终结果等价于将x最右侧的1位及其右侧所有位置为0，也就是彻底删除了x最右侧的1位。

二、原习题的bitcount函数 #

原函数通过逐位右移并检查最低位是否为1来统计1的个数：

/* bitcount:  count 1 bits in x */
int bitcount(unsigned x) {
    int b;
    for (b = 0; x != 0; x >>= 1)
        if (x & 01)
            b++;
    return b;
}

三、你的实现验证与分析 #

你基于x &= (x-1)实现的bitcount函数是完全正确的，且效率更高：

#include <stdio.h>

int bitcount(unsigned x);

int main() {
    int x, onebits;
    printf("Enter an integer: ");
    scanf("%d", &x);
    onebits = bitcount(x);
    printf("This integer contains %d one bits.", onebits);
    return 0;
}

int bitcount(unsigned x) {
    int b;
    for (b = 0; x != 0; x &= (x - 1))
        ++b;
    return b;
}

正确性与优势说明： #

• 正确性：每次循环x &= x-1都会删除一个1位，循环次数恰好等于x中1位的总数，最终统计结果准确。
• 效率提升：原函数需要循环x的二进制位数次（例如32位整数最多循环32次），而你的实现仅需循环x中1位的个数次（例如x只有1个1时仅循环1次），在1位较少的场景下效率提升明显。
• 无符号参数的安全性：函数参数为unsigned，避免了有符号数右移时的符号扩展问题（原函数虽也用unsigned，但你的实现无需右移，逻辑更简洁）。
• 输入处理说明：scanf("%d", &x)读取的整数会自动转换为unsigned类型传入函数，若输入负数，会被转换为对应无符号数的补码形式（例如输入-1，32位系统中会转为0xFFFFFFFF，函数会返回32），这符合无符号数的运算逻辑，属于正常行为。

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