首页 > 代码库 > nyoj 222 整数中的1个数以及这类问题
nyoj 222 整数中的1个数以及这类问题
之前也写过一篇这样的文章，但是隔了这么久，竟然忘了。还是要有清晰的思路，才能真正的掌握。
这道题是这样的：
给出两个非负32位整型范围内的数a,b，请输出闭区间[a,b]内所有数二进制中各个位的1的总个数。
分析：为的是求2进制中1的个数。从0-15的二进制如下：
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
第一位的1，每隔2就出现。第二位的1，每隔4出现2次。第三位的1，每隔8出现4次。第四位的1，每隔16出现8次。
所以，可以判断[0-a]中1的个数为：第一位 (a + 1) / 2 ，第二位 (a + 1) / 4 如果(a + 1 ) % 4 > 2 ,则还需要加这部分。
#include <iostream>using namespace std;int func (int a){ if (a <= 0) return 0; int i = 2, j = 1; int sum = 0; int b = a + 1, tmp; while (a >= i / 2) { sum += b / i * j; if ((tmp = b % i - i / 2) > 0) sum += tmp; i *= 2; j *= 2; } return sum;}int main (void){ long a, b; cin >> a >> b; cout << func (b) - func (a - 1) << endl; return 0;}
nyoj 222 整数中的1个数以及这类问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。