算法训练-二进制数数-0，1码计数。

红太狼 2023-01-10 03:56 116阅读 0赞

资源限制  
时间限制：1.0s 内存限制：256.0MB  
问题描述  
　　给定L,R。统计\[L,R\]区间内的所有数在二进制下包含的“1”的个数之和。  
　　如5的二进制为101，包含2个“1”。  
输入格式  
　　第一行包含2个数L,R  
输出格式  
　　一个数S，表示\[L,R\]区间内的所有数在二进制下包含的“1”的个数之和。  
样例输入  
2 3  
样例输出  
3  
数据规模和约定  
　　L<=R<=100000;  
**思路**  
思路一：区间遍历，把数转二进制码，一股脑儿换成0或者1，存放数组里，然后遍历数组，看有多少个1。这个存放的**数组得足够大**，不然会下标越界。  
思路二：也是数组，只是这个数组可以不用思路一那么大，因为这个思路是调用函数。  
**思路一：**

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        
    	int l,r,s;
    	scanf("%d%d",&l,&r);
    	int i;
    	int len=0,b[400000],sum=0;
    	memset(b,0,sizeof(b));
    	for(i=l;i<=r;i++){
        
    		int s=i;
    		while(s>0){
        
    			b[len++]=s%2;
    			s=s/2;
    		}
    	}
    	for(i=0;i<len;i++){
        
    		if(b[i]==1){
        
    			sum++;
    		}
    	}
    	printf("%d\n",sum);
    	return 0;
    }

**思路二：**

#include <stdio.h>
    int sum=0;
    int len;
    void fun(int a[1000],int len)
    {
        
    	int i=0;
    	for(i=0;i<len;i++)
    	{
        
    		if(a[i]==1)
    			sum++;
    	}
    } 
    
    void change(int n)
    {
        
    	int a[1000];
    	int i=0;
    	while(n>0)
    	{
        
    		a[i]=n%2;
    		n/=2;
    		i++;
    	}
    	fun(a,i);
    }
    
    int main()
    {
        
    	int L,R;
    	scanf("%d %d",&L,&R);
    	int i;
    	for(i=L;i<=R;i++)
    	{
        
    		change(i);
    	}
    	printf("%d",sum);
    	return 0;
    }