20240318每日一题题解
20240318每日一题题解
Problem
若将一个正整数化为二进制数，在此二进制数中，我们将数字 \(1\) 的个数多于数字 \(0\) 的个数的这类二进制数称为 \(A\) 类数，否则就称其为 \(B\) 类数。
例如：
\((13)_{10}=(1101)_2\)，其中 \(1\) 的个数为 \(3\)，\(0\) 的个数为 \(1\)，则称此数为 \(A\) 类数；
\((10)_{10}=(1010)_2\)，其中 \(1\) 的个数为 \(2\)，\(0\) 的个数也为 \(2\)，称此数为 \(B\) 类数；
\((24)_{10}=(11000)_2\)，其中 \(1\) 的个数为 \(2\)，\(0\) 的个数为 \(3\)，则称此数为 \(B\) 类数；
程序要求：求出 1~n 之中（\(1 \le n \le 1000\)），全部 \(A,B\) 两类数的个数。
输入输出格式
输入 \(n\)。
输出一行，包含两个整数，分别是 \(A\) 类数和 \(B\) 类数的个数，中间用单个空格隔开。
输入输出样例
输入1
7
输出1
5 2
Solution
除法和取余
对于数字x，我们从低位开始考虑。
如果x除以2的余数是1，则说明x在二进制下的最低位是1
如果x除以2的余数是0，则说明x在二进制下的最低位是0
而将x除以2，就可以将x的最低位直接抹去
例如：\((10)_{10}=(1010)_2\)，10/2=5，\((5)_{10}=(101)_2\)
只要x还有值，那么就判断x的最低位是0还是1，并且将x的最低位抹去
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int count_A=0,count_B=0; // 两个变量用来存放A类数和B类数的数量
for(int i=1;i<=n;i++)
{
int x=i; // x为当前要判断的数
int number0=0,number1=0; // 用两个变量统计 x 中的0和1的数量
// 重点！使用除法和取余数来统计
while(x) // 只要x还有值
{
if(x%2 == 1) number1++; // 使用取余数来得到x在二进制下最低位是0还是1
else number0++;
x/=2; // 使用除法来让x在二进制下的最低位抹去
}
if(number1>number0) count_A++; // 如果1比0多，则归为A类数
else count_B++;
}
cout<<count_A<<" "<<count_B<<endl;
return 0;
}
二进制位运算
c++对于整数二进制运算支持的非常好，下面介绍两种二进制运算符
-
&（按位与）：将两个操作数的二进制按位比较，仅当对应位都是1时，结果的这一位才为1。10011010011 & 00000011001 = 00000010001 -
>>（右移位）：将操作数的所有位向右移动指定的位数，低位直接抹去。10011010010 >> 2 = 100110100
可以用x&1来判断x的最低位是不是1。 1 的二进制表示是 000...0001，x&1就相当于只保留 x 的最低位。
有了以上的铺垫，我们就能很轻松的提取了。我们这需要每次把数和1进行按位且操作，这样就能提取出这个数的最后一位，然后在把这个数右移一位就行了。
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int count_A=0,count_B=0;//两个变量用来存放A类数和B类数的数量
for(int i=1;i<=n;i++)
{
int x=i;//x为当前要判断的数
int number0=0,number1=0;//用两个变量统计 x 中的0和1的数量
//重点！
while(x)//只要x还有值
{
if(x&1) number1++;//用二进制运算符&(二进制与)得到x在二进制下最低位是0还是1
else number0++;
x>>=1;//二进制右移运算符，让x在二进制下的最低位抹去
}
if(number1>number0) count_A++;//如果1比0多，则归为A类数
else count_B++;
}
cout<<count_A<<" "<<count_B<<endl;
return 0;
}
STL
c++中提供一种容器bitset，其有一个功能可以将十进制数字转成二进制数字，count()函数还可以统计其中的1的数量。
那么0的位数可以由二进制下的位数总数减去1的个数得到
二进制下的位数总数可用公式\(\lfloor\log_2x+1\rfloor\)得到
#include<iostream>
#include<bitset>//bitset的头文件
#include<cmath>//使用取以2为底的对数函数log2()需要包含cmath
using namespace std;
int main()
{
int n;
cin>>n;
int count_A=0,count_B=0;//两个变量用来存放A类数和B类数的数量
for(int i=1;i<=n;i++)
{
bitset<20>x(i);//定义一个最大长度为20的bitset，其十进制值是i
int number1=x.count();//1的数量直接用count()函数统计
int number0=floor(log2(i)+1)-number1;//0的数量是用二进制数的总位数减去1的数量
//使用log2(i)下取整在加一，得到i在二进制下的总位数
if(number1>number0) count_A++;//如果1比0多，则归为A类数
else count_B++;
}
cout<<count_A<<" "<<count_B<<endl;
return 0;
}
内置函数（不推荐）
在C++中，一些编译器（如GCC和Clang）提供了一些内置函数来执行一些常见的位操作，例如：
__builtin_popcount：计算整数在二进制下1的数量
__builtin_clz：计算整数在二进制下前导0的数量
而我们又知道，int整型是32位的，即共有32个0/1
所以，1的个数=__builtin_popcount
0的个数=32-前导零__builtin_clz-1的个数
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int count_A=0,count_B=0;//两个变量用来存放A类数和B类数的数量
for(int i=1;i<=n;i++)
{
int number1=__builtin_popcount(i);
int number0=32-__builtin_clz(i)-number1;
if(number1>number0) count_A++;//如果1比0多，则归为A类数
else count_B++;
}
cout<<count_A<<" "<<count_B<<endl;
return 0;
}