如何用递归方法统计整数二进制表示中1的个数

核心逻辑说明 #

递归实现只需要抓住两个核心规则：

• 终止条件：当入参X == 0时，二进制中没有1，直接返回0即可，你原来的终止条件仅覆盖了X=0的判断，逻辑冗余且不全
• 递推公式：当前位的1的计数为X % 2（结果为0或1，对应当前最低位是否为1），剩余高位的1的计数可以递归调用binaryOnes(X / 2)获得，最终返回两者的和即可

完整实现代码 #

public static int binaryOnes(int X) {
    // 递归终止条件
    if (X == 0) {
        return 0;
    }
    // 当前位计数 + 高位部分递归计数
    return X % 2 + binaryOnes(X / 2);
}

扩展优化（支持负数统计） #

如果需要兼容负数的1的统计，可以将算术运算替换为位运算，避免符号位影响计算结果：

public static int binaryOnes(int X) {
    if (X == 0) {
        return 0;
    }
    // X&1等价于X%2取最低位，X>>>1是无符号右移等价于非负数的X/2
    return (X & 1) + binaryOnes(X >>> 1);
}

测试代码问题修正 #

你之前写的错误测试代码存在两个问题：

• 方法返回值声明错误，binaryOnes返回int类型，不能声明为void
• 语法错误，调用语句末尾应该是分号不是句号

你提供的驱动测试代码可以直接和上述实现配合运行，测试0-9的所有用例都会返回Correct。

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