Java递归函数问题求助：实现ones(int x)统计二进制1的个数

嘿，我来帮你搞定这个递归统计二进制1的个数的问题！要写出能适配任意int位数（16/32/64位）的ones(int x)函数，关键要解决负数右移的死循环问题和递归的终止逻辑，我给你两种清晰的实现思路：

这是最直观的递归写法，核心是用无符号右移来避免负数高位补1导致的无限递归，完全不依赖int的具体位数。

实现代码 #

public class BitCounter {
    public static int ones(int x) {
        // 递归终止条件：x变成0时，二进制里已经没有1了
        if (x == 0) {
            return 0;
        }
        // 先判断最低位是否为1（x&1的结果是0或1），再加上右移后剩余部分的1的个数
        return (x & 1) + ones(x >>> 1);
    }

    // 测试用例
    public static void main(String[] args) {
        System.out.println(ones(5));      // 二进制101 → 输出2
        System.out.println(ones(-1));     // 全1的二进制 → 输出对应int位数（比如32位就是32）
        System.out.println(ones(0));      // 输出0
        System.out.println(ones(0b111000));// 二进制111000 → 输出3
    }
}

为啥能适配任意位数？ #

普通的带符号右移>>对负数会在高位补1，导致负数永远变不成0，直接陷入死循环。而**无符号右移>>>**不管原数是正还是负，都会把最高位补0，直到整个数变成0——不管int是16位还是64位，这个逻辑都能完美工作，完全不依赖具体位数。

比如-1的二进制是全1，无符号右移每次都会把最右边的1移走，直到所有位都变成0，递归次数正好等于int的位数，返回结果就是总位数，完全符合要求。

如果追求更高的统计效率，可以用分治的递归思路，把数字拆成小块分别统计1的个数，再合并结果。这种方法的递归层级更少，速度更快：

实现代码 #

public static int ones(int x) {
    if (x == 0) return 0;
    // 每两位一组统计1的个数
    x = x - ((x >>> 1) & 0x55555555);
    // 每四位一组合并结果
    x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
    // 每八位一组合并结果
    x = (x + (x >>> 4)) & 0x0F0F0F0F;
    // 继续合并更高位
    x = x + (x >>> 8);
    x = x + (x >>> 16);
    // 取最终结果（最多64位的话，结果不会超过64，所以用0x3F掩码足够）
    return x & 0x0000003F;
}

这个方法虽然看起来复杂，但本质还是递归的分治思想，而且同样适配任意int位数——因为不管位数多少，最终都会合并到最低位得到总数。

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