快盘下载:好资源、好软件、快快下载吧!

快盘排行|快盘最新

当前位置:首页新闻资讯软件测评 → 算法:计算十进制数字在二进制表示1的个数

算法:计算十进制数字在二进制表示1的个数

时间:2020-01-25 16:34:27人气:作者:快盘下载我要评论

题目一

计算十进制数字在二进制表示 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 > 1;
       }
       
       printf("number:%d, count:%d ", 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(" ");
   
   return 0;
}

这个程序的过程如下:

首先先读入一个整数 n,代表要求解的范围; 然后循环 n 次,每一次通过 f[i] = f[i & (i - 1)] + 1 计算得到 f[i] 的值,也就是数字的二进制表示 1 的个数; 最后输出 1 到 n 中每个数字二进制表示中 1 的个数。

针对这个解法,程序的时间复杂度是 O(n)。

相关文章

  • 全局配置和windows节点常用配置

    全局配置和windows节点常用配置,小程序根目录下的app.json文件是小程序的全局配置文件,常用的配置项如下: pages 记录当前小程序所有页面的存放路径 windows 全局设置小......
  • 2. 请画出NAT模式、DR模式的原理图并说出有什么区别

    2. 请画出NAT模式、DR模式的原理图并说出有什么区别,集群是一组相互独立的、通过高速网络互联的计算机,它们构成了一个组,并以单一系统的模式加以管理。...

网友评论

快盘下载暂未开通留言功能。

关于我们| 广告联络| 联系我们| 网站帮助| 免责声明| 软件发布

Copyright 2019-2029 【快快下载吧】 版权所有 快快下载吧 | 豫ICP备10006759号公安备案:41010502004165

声明: 快快下载吧上的所有软件和资料来源于互联网,仅供学习和研究使用,请测试后自行销毁,如有侵犯你版权的,请来信指出,本站将立即改正。