苟哥的笔记本
首页
文章归档
关于
文章归档
关于
首页
编程
正文
C程序设计语言第2版习题2-9
苟哥
2019-06-17 AM
1062℃
0条
#### 问题描述 在求反码时，表达式 x &= (x - 1) 用于把x最右边的值为1的位删除掉。请解释一下这样做的道理。用这一方法重写bitcount函数 ，使之执行得更快一点。 ------ #### 问题分解 - 主函数main - 核心函数 bitcount(x)。我们先来看看书中例子 bitcount的算法实现： ```c int bitcount(unsigned x) { int b; for(b = 0; x != 0; x >>= 1) { if(x & 1) b++; } return b; } ``` 从以上代码可知， bitcount 的实现逻辑是根据任何数与1进行位与计算可判断出次数的最右侧是否为1， 根据此原理不断将x右移，妹出现一次1记录一次。 根据题意，我们现在要改造bitcount的实现方式，借用 x &= (x - 1) 。如何理解呢？ 我们知道二进制的特性， 不是0 就是1， 所以x & x - 1操作后的最右边值一定是互反的， 这样，x & （x - 1）的最右边的值一定为0，如此循环后x的最终值为0，循环次数即为x中值为1的个数。 ------ #### 代码实现 ```c #include<stdio.h> int bitcount(unsigned x); int main() { unsigned x; int r; x = 3; r = bitcount(x); printf("The result is: %u \n", r); return 0; } //使用求反码的方式 int bitcount(unsigned x) { int b; for(b = 0; x != 0; b++) { x &= (x - 1); } return b; } ``` 对比两个bitcount函数，我们发现第一个bitcount 中，for每执行一次，比第二个的bitcount 多执行了一次位与(&)操作，因此可以说第二个bitcount的执行速度是更快的。
标签:
C程序设计语言
,
算法
,
C语言
,
习题2-9
非特殊说明，本博所有文章均为博主原创。
如若转载，请注明出处：
http://www.i366211.com/archives/45/
上一篇
C程序设计语言第2版习题2-8
下一篇
C程序设计语言第2版习题3-3
取消回复
评论啦~
提交评论
栏目分类
软件安装
10
开发工具
8
算法
2
测试
1
架构
3
填坑记
2
开源
6
科普
4
私域
2
读书笔记
4
编程
48
运营
3
管理
1
标签云
算法
C程序设计语言
C语言
Java
mysql
PHP
ffmpeg
golang
VueJs
脚手架
VueJs实战项目
Intellij IDEA
Centos7
Hyperf
抖音运营
杰克韦尔奇
跌荡一百年
生成海量测试数据
企业管理
习题2-3
习题2-4
习题2-6
异常分类
File
习题2-7
习题2-8
习题2-9
习题3-3
习题3-4
习题3-5
友情链接
申请
SaaS引擎
机器人框架
京东捡漏