十进制数二进制1的计数优化及最小同1数目正整数求解的技术咨询

阿华AIGC实验室

2026-4-7

嘿，作为刚接触编程竞赛的新手，你能自己捣鼓出实现思路已经超棒了！先给你点个赞👍 不过看了你的代码，确实能发现可以优化的地方——尤其是统计二进制里1的个数的部分，写得有点绕还容易出bug，咱们一步步来捋清楚，把问题变得简单又高效～

一、先把“统计二进制1的个数”这个核心逻辑掰正

你现在的bin函数试图把二进制转成十进制数（比如把11转成11）再数1的个数，这个思路不仅容易因为数字溢出踩坑（比如数大了存不下），而且逻辑绕来绕去很容易出错——比如测试输入3的时候，你的函数会返回1，但实际二进制11明明有2个1对吧？

编程竞赛里统计二进制1的个数有两个超实用的妙招，给你分享下：

方法1：直观位运算循环（新手友好）

利用n & 1能直接取出二进制最后一位，再用n >>= 1把数字右移一位（相当于除以2），循环统计就行，逻辑直白到没朋友：

int count_ones(int n) {
    int count = 0;
    while (n > 0) {
        count += n & 1; // 最后一位是1就加1
        n >>= 1; // 右移一位，看下一位
    }
    return count;
}

这个写法完全不会有溢出问题，效率也很高，二进制有多少位就循环多少次。

方法2：Brian Kernighan算法（竞赛选手最爱）

这个方法更高效，能跳过所有0，直接盯着1找——每次用n & n - 1消除最右边的1，循环次数刚好等于1的个数：

int count_ones(int n) {
    int count = 0;
    while (n > 0) {
        n &= n - 1; // 一键消除最右边的1
        count++;
    }
    return count;
}

比如输入3（二进制11），第一次循环消除最右边的1变成10（2），count加1；第二次循环消除剩下的1变成0，count再加1，完美得到2个1。这种方法在1的个数少的时候速度快到飞起，竞赛里经常用。

二、再解决“找最小的正整数，二进制1的个数和输入数一样”的问题

你现在的思路是从0开始挨个遍历找符合条件的数，虽然小范围内能跑，但其实有个更聪明的办法——根本不用遍历！

你想啊：要找所有正整数里，二进制1的个数等于k的最小数，那不就是二进制里k个1连在一起的数吗？比如k=1就是1，k=2就是11（也就是3），k=3就是111（也就是7）... 换算成代码就是(1 << k) - 1——左移k位相当于2的k次方，减1就得到k个连续的1了！

哦对了，要是k=0的话（只有0的二进制1的个数是0），直接返回0就行。

这样一来，你的代码能简化到极致：

#include <stdio.h>

// 用Brian Kernighan算法统计二进制1的个数，高效又靠谱
int count_ones(int n) {
    int count = 0;
    while (n > 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

int main(void) {
    int A;
    printf("number: ");
    scanf("%i", &A);
    
    if (A < 0 || A > 1000000) {
        return 1;
    }
    
    int k = count_ones(A);
    // 计算最小的数：k个连续1的二进制数，特殊情况k=0时返回0
    int result = (k == 0) ? 0 : ((1 << k) - 1);
    
    printf("%i\n", result);
    return 0;
}

测试几个案例验证下：