首页 / 算法 / 算法:计算十进制数字在二进制表示1的个数
算法:计算十进制数字在二进制表示1的个数
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法:计算十进制数字在二进制表示1的个数,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2246字,纯文字阅读大概需要4分钟。
内容图文
![算法:计算十进制数字在二进制表示1的个数](/upload/InfoBanner/zyjiaocheng/1313/6fb8d6b148d94817b8b8b36f48d0a342.jpg)
题目一
计算十进制数字在二进制表示 1 的个数
举个例子:
- 十进制数字为 1 时,它的二进制表示是 001,二进制表示 1 的个数为 1;
- 十进制数字为 2 时,它的二进制表示是 010,二进制表示 1 的个数为 1;
- 十进制数字为 3 时,它的二进制表示是 011,二进制表示 1 的个数为 2;
- 十进制数字为 4 时,它的二进制表示是 100,二进制表示 1 的个数为 1;
- 十进制数字为 5 时,它的二进制表示是 101,二进制表示 1 的个数为 2;
- 十进制数字为 6 时,它的二进制表示是 110,二进制表示 1 的个数为 2;
- 十进制数字为 7 时,它的二进制表示是 111,二进制表示 1 的个数为 3;
时间复杂度 O(logn) 的解法
对于这个题目比较容易想到的是如下代码:
int count = 0;
while(n != 0)
{
if(n % 2 == 1)
{
count++;
}
n = n >> 1;
}
上述代码主要做了两个步骤:
-
n % 2
表示对数字求模运算,也就是计算二进制的末尾是 1 还是 0,如果二进制的末尾是 1 ,则 count 自增,count 表示的是二进制表示 1 的个数; -
n = n >> 1
表示把二进制往右移走一位,比如十进制数字 7 的二进制表示是 111 ,那么通过右移一位后,则变成 011。
这个解决方式虽然能计算出二进制表示 1 的个数,但是我们可以发现这个解法的时间复杂度是 O(logn),比如当 n 为 7 时,它的二进制表示是 111,那么它将会循环 3 次,也就是非常接近 log 以 2 为底 7 的对数的值。
题目二
程序读入一个整数 n,假设 n 不会大于 1000,请输出 1 到 n 每个数字的二进制表示 1 的个数。
时间复杂度 O(nlogn) 的解法
可能有的小伙伴说,这题目二还不简单?直接把上面的解法,增加个 for 循环不就得了。
int main()
{
int i, j, n, count;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
j = i;
count = 0;
while(j != 0)
{
if(j % 2 == 1)
{
count++;
}
j = j >> 1;
}
printf("number:%d, count:%d\n", i, count);
}
return 0;
}
假设输入 7,则输出结果:
number:1, count:1
number:2, count:1
number:3, count:2
number:4, count:1
number:5, count:2
number:6, count:2
number:7, count:3
number:8, count:1
没错,用上述的解法增加个 for 循环,确实可以解决题目二的要求,这值得鼓励,但是程序的时间复杂度是时间复杂度 O(nlogn) ,运行效率不高,所以我们必须要有种精神,就是要用时间复杂度最少的方式去解决算法的问题,这样才能一次一次的进步。
时间复杂度 O(n) 的解法
请先观察下面的位运算性质:
y = x & (x - 1)
我们看到,x
和与 x -1
这两个数字做按位与运算,所以我们要以二进制的角度去思考这个问题。
比如:
- 假设
x
是 3,它的二进制是 011; - 那么
x - 1
就是 2,它的二进制是 010; -
x & (x - 1)
运算后的二进制就是 010。
那么 x & (x - 1)
实际效果等效于去掉 x
二进制表示中的最后一位 1,从而我们发现原来 y
变量与 x
变量在二进制表示中,只差一个 1。
如果我们用一个数组 f
记录相应数字二进制表示中 1 的数量,那么 f[i]
数组存放的值是 i
这个数字二进制表示中 1 的数量,从而我们可以推导得到 f[i] = f[i & (i - 1)] + 1
,也就是说 i
数字比 i & (i - 1)
数字的二进制表示中的 1 的数量要多一个,这样我们通过一步计算就得到 f[i]
的结果,也就是相应数字二进制表示中 1 的数量结果。
代码如下:
int main()
{
int n,i;
int f[1001];
f[0] = 0;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
f[i] = f[i & (i - 1)] + 1;
}
for(i = 1; i <= n; i++)
{
printf("%d ", f[i]);
}
printf("\n");
return 0;
}
这个程序的过程如下:
- 首先先读入一个整数
n
,代表要求解的范围; - 然后循环
n
次,每一次通过f[i] = f[i & (i - 1)] + 1
计算得到f[i]
的值,也就是数字的二进制表示 1 的个数; - 最后输出 1 到
n
中每个数字二进制表示中 1 的个数。
针对这个解法,程序的时间复杂度是 O(n)。
原文:https://www.cnblogs.com/xiaolincoding/p/12219909.html
内容总结
以上是互联网集市为您收集整理的算法:计算十进制数字在二进制表示1的个数全部内容,希望文章能够帮你解决算法:计算十进制数字在二进制表示1的个数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。