剑指Offer面试题:8.二进制中1的个数
2024-08-25 09:31:39
一 题目:二进制中1的个数
题目:请实现一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9,该函数输出2。
二 可能引起死循环的解法
// 计算整数的二进制表示中1的个数
int CalcOneNumInBinary(int nVal)
{
int nCount = ;
while (nVal > )
{
if ( == (nVal & ))
{
nCount ++;
} nVal = nVal >> ;
}
return nCount;
}
PS:右移运算符m>>n表示把m右移n位。右移n位的时候,最右边的n位将被丢弃。如果数字原先是一个正数,则右移之后在最左边补n个0;如果数字原先是负数,则右移之后在最左边补n个1。例如下面对两个八位二进制数进行右移操作:
00001010>>2=00000010
10001010>>3=11110001
那么,问题来了:上面的方法如果输入一个负数,比如0x80000000,如果一直做右移运算,最终这个数字就会变成0xFFFFFFFF而陷入死循环。
三 避免死循环的解法
为了避免死循环,我们可以不右移输入的数字i:
(1)首先把i和1做与运算,判断i的最低位是不是为1。
(2)接着把1左移一位得到2,再和i做与运算,就能判断i的次低位是不是1。
(3)这样反复左移,每次都能判断i的其中一位是不是1。
int CalcOneNumInBinary_1(int nVal)
{
int nCount = ;
int nFlag = ;
while (nFlag > )
{
if ((nVal & nFlag) > )
{
nCount ++;
} nFlag = nFlag << ;
}
return nCount;
}
四 高效新颖解法
int NumberOf1Solution3(int n)
{
int count = ; while (n > )
{
count++;
n = (n - ) & n;
} return count;
}
最新文章
- python读取和写入csv文件
- MongoDB学习笔记——集合管理
- HDU 4738 Caocao&#39;s Bridges(Tarjan求桥+重边判断)
- nodeJs爬虫获取数据
- linux-搜索
- 17.2.2 Replication Relay and Status Logs 复制Relay 和状态日志;
- poj 2274 The Race 最小堆
- 乐在其中设计模式(C#) - 外观模式(Facade Pattern)
- 生成元(Digit Generator,ACM/ICPC Seoul 2005,UVa 1583)
- Android开发,Eclipse创建aidl接口时,出错
- PHP+Jquery+Ajax 实现动态生成GUID、加载GUID
- GridView七十二绝技-大全(收藏版)(转至别人博客)
- 分页(将数据库中的多条数据一页一页的显示在jsp页面中)
- [转]TopShelf 用法
- 学习MeteoInfo二次开发教程(十一)
- android:如何通过chrome远程调试APP中的webView的h5代码
- KVM 通过virsh console连入虚拟机
- 《Python》 面向对象初识
- route命令详情
- Spring框架总结(一)