计算二进制数中1的个数

巴蜀人在紫荆 posted @ 2012年12月19日 03:38 in 编程之美 with tags 算法 编程 , 575 阅读

编程之美中提出有三种方法:

1、每次除以2,看余数是否为1,是的话结果+1,最后可得到结果;

int count1(byte n) {
int num = 0;
while (n != 0) {
if (n % 2 == 1) {
num ++;
}
n /= 2;
}
return num;
}

2、通过移位来确定1的个数

int count2(byte n) {
int num = 0;
while (n != 0) {
if (n % 2 == 1) {
num += n && 0x01;
n >>= 1;
}
}
return num;
}

3、用到一个巧妙的与操作,v & (v -1 )每次能消去二进制表示中最后一位1,利用这个技巧可以减少一定的循环次数。

int count3(byte n) {
int num = 0;
while (n != 0) {
n &= (n-1);
num ++;
}
return num;
}

4、更多算法见http://blog.csdn.net/justpub/article/details/2292823http://en.wikipedia.org/wiki/Hamming_weight

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter