2218: 蓝桥杯算法训练-二进制数数（位运算）

解题思路:

对于二进制转十进制来说，有一个简单的方法是8 4 2 1

以101为例，它转成十进制就是1*2^(3-1)+0*2^(2-1)+1*2^(1-1) 即为4+0+1=5

我们可以发现它可以拆成多少个2的整数次方，就有多少个1。

5（101）可以拆成4和1，有两个，所以就是两个1，7（111）可以拆成4+2+1，所以就是三个1。

考虑到2的三十次方以上就超过int型的最大数了，所以我们把2的30以内的次方以打表的形式放进数组中，减少运算。

参考代码:

#include <stdio.h>

long long int p[31]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,};

int main ()
{
	int i,j,k=0;
	int n=0,m=0,z=0;
	scanf("%d %d",&n,&m);
	for(i=n;i<=m;i++){
		k=i;
		while(k>0){
			for(j=0;j<31;j++){
				if(p[j]<=k&&p[j+1]>k){//找到刚好比k小的2的整数次方
					break;
				}
			}
			k-=p[j];//减去
			z++;//1的数量加1
		}
	}
	printf("%d",z);

	
	return 0;
}

 第二个方法是&运算。

&运算中1&1=1,1&0=0,0&0=0

通过n=n&(n-1)，n通过几步达到0，n的二进制就有几个0

以7（111）为例

111&110=110 一次

110&101=100 两次

100&011=000 三次，最后正好到0。

代码实现如下，具体位运算的巧妙还需要大家多了解位运算的知识：

#include <stdio.h>

int main ()
{
	int i,j,k=0;
	int n=0,m=0,z=0;
	scanf("%d %d",&n,&m);
	for(i=n;i<=m;i++){
		k=i;
		while(k>0){
			k=k&(k-1);
			z++;
		}
	}
	printf("%d",z);

	
	return 0;
}