C++二级题 计算好数：1数大于0数(二进制的位运算)

1、题目

若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为好数。

例如：

(13)10 = (1101)2，其中1的个数为3，0的个数为1，则此数是好数；

(10)10 = (1010)2，其中1的个数为2，0的个数也为2，则此数不是好数；

(24)10 = (11000)2，其中1的个数为2，0的个数为3，则此数不是好数；

对于给定的N,写程序求出1～N之中（包括1与N）中的好数个数。

时间限制：1000

内存限制：65536

输入

一个整数，题目中的N(N ≤ 1000)

输出

一个整数，表示1～N之中（包括1与N）中的好数个数

样例输入

10

样例输出

5

2、提示

提示：

(1)n>>=1 二进制右移一位

‌n>>=1‌表示将变量n的二进制表示向右移动一位，并将结果赋值给n。‌

具体来说，n>>=1的操作过程是将n的二进制表示向右移动一位，最右边的位会被丢弃，而最左边的位会填充为0。这个过程相当于将n除以2并取整。例如，如果n=8（二进制表示为1000），那么n>>=1后，n的值将变为4（二进制表示为100）。

这种操作在位运算中非常常见，可以用于各种算法和数据处理中。例如，在统计一个无符号整数的二进制表示中有多少个1时，可以通过连续地将结果左移并添加原始数最右边的位，然后将原始数右移，有效地反转了位。

(2)n&1 用来找二进制最低位数/奇数

‌在C++中，表达式n&1用于判断n是否为奇数。‌ 

如果n为奇数，n的二进制表示的最低位为1，因此n&1的结果为1；如果n为偶数，n的二进制表示的最低位为0，因此n&1的结果为0。‌

这种判断方法利用了二进制运算的性质。在二进制表示中，奇数的最低位为1，偶数的最低位为0。因此，通过将n与1进行按位与操作（&），可以快速判断n的奇偶性。具体来说，1的二进制表示为000...01，与n进行按位与操作后，只有当n的最低位为1时，结果才为1，否则为0。

(3)比特右移（>>）运算符可以是算术（左端补最高有效位）或是逻辑（左端补 0）位移。

3、代码

#include <bits/stdc++.h>
using namespace std;
bool is_good(int n){int a=0,b=0;while(n){if(n&1) a++;else b++;n>>=1;}return a>b?true:false;
} 
int main(){int n,counts=0;cin>>n;for(int i=1;i<=n;i++)if(is_good(i)) counts++;cout<<counts;return 0;
}