【编程之美】2.1求二进制中1的个数
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【编程之美】2.1求二进制中1的个数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2457字，纯文字阅读大概需要4分钟。
内容图文
题目： 对于一个字节的无符号整数变量，求其中的二进制表示中1的个数，要求算法执行效率尽可能高效。 题目解析： 这道题同样在【剑指offer】面试题10：二进制中1的个数中出现，不过在剑指offer中没有提到无符号数，因此比该题目中多考虑一个层次。下面总结这
题目：
对于一个字节的无符号整数变量，求其中的二进制表示中1的个数，要求算法执行效率尽可能高效。
题目解析：
这道题同样在【剑指offer】面试题10：二进制中1的个数 中出现，不过在剑指offer中没有提到无符号数，因此比该题目中多考虑一个层次。下面总结这道题的几种解法。
解法一（用于该题目）：
我们通常会想到除以2就是将二进制右移一位，但要判断移除的是0还是1，就要对2取余。思路很简单，通过四则运算来解答：
int Count(Byte v)
{
int num = 0;
while(v){
if(v%2)
num++;
v /= 2;
}
return num;
}解法二（用于该题目）：
对于除以2来表示二进制右移，除法的效率比直接移位的效率低得多。碰到这样的题目，尽量用移位来代替。位运算就五种形式：与、或、异或、左移和右移。在这些范围里面找到自己想要的运算。移位时要判断移除的是0还是1，那么这里就应该通过与操作判断最后一位是否为1。
int Count2(Byte v)
{
int num = 0;
while(v){
if(v & 1)
num++;
//也可以用 num += v&1; 来代替上面两行
v = v >> 1;
}
return num;
}解法三（可以用于有符号数）：
如果这个题目是有符号的话，当右移的时候，会在高位补充符号位，用上面两种方法的话，会陷入死循环。如何避免？可以先判断最高位，然后遍历n-1次判断除了最高位以外的位是否为1。这样的方法比较麻烦。我们可以变通一个思路，让与的那一位1不断的左移，直到将1移到最高位。
int Count3(Byte v)
{
int num = 0;
int flag = 1;
while(flag){
if(v & flag)
++num;
flag = flag << 1;
}
return num;
}解法四（更加高效的算法）：
这种方法，充分利用了二进制的相关操作，平时应该多收集这样的运算。
一个数不为0，那么二进制中肯定含1。当让这个数减去1时，最低位的1由1->0，更低位的0由0->1。当让n与n-1相与以后，n中最低位的1变成0。一次这样的操作，消去一个1，那么二进制中有多少个1，就循环多少次即可。
int Count4(Byte v)
{
int num = 0;
while(v){
++num;
v = v & (v-1);
}
return num;
}解法五（空间换时间方法）：
其实方法四已经够好了，但是因为只涉及到八位，我们可以利用选择直接选取相应的数据。比如0x1-0x2-0x4...这些都包含1个1；0x3-0x6...包含两个1；等等。通过switch语句选择相应的结果。但是这种方法效率可能比较低，因为，当输入v为255的时候，得比较到最后才能找到相应的数据。
int Count5(Byte v)
{
int num = 0;
switch(v){
case 0x0:
num = 0;
break;
case 0x1:
case 0x2:
....
}
return num;
}解法六（哈希表法）：
既然想到了利用空间换时间，我们干脆用个数组来表示，index为要查找的数，counttable[index]为该数据包含1的个数。
内容总结
以上是互联网集市为您收集整理的【编程之美】2.1求二进制中1的个数全部内容，希望文章能够帮你解决【编程之美】2.1求二进制中1的个数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。