我也来出个好玩的题

[SpitFire]

计算出正整数N二进制1的个数

--
SpitFire

[Atry]

int numberOfOne;
for(;;) {
  numberOfOne += N & 1;
  N >>= 1;
}
return numberOfOne;

2007/11/15, SpitFire <spit...@gmail.com >:

计算出正整数N二进制1的个数

--
SpitFire

[SpitFire]

比较正统的回答，时间复杂度可以继续下降

在07-11-15，Atry <pop....@gmail.com> 写道：

--
SpitFire

[Fisher]

如果N的位数确定，时间复杂度可以O(1)

[SpitFire]

就一般的64位好了

在07-11-15，Fisher <yuf...@gmail.com> 写道：

--
SpitFire

[Fisher]

ms是这样的？

int _n = 0;
_n = ((N & 0xAAAAAAAA) >> 1) + (N & 0x55555555);
_n = ((_n & 0xCCCCCCCC) >> 2)) + (_n & 0x33333333);
_n = ((_n & 0xF0F0F0F0) >> 4) + (_n & 0x0F0F0F0F);
_n = ((_n & 0xFF00FF00) >> 8) + (_n & 0x00FF00FF);
_n = ((_n & 0xFFFF0000) >> 16) + (_n & 0000FFFF);
return _n;

[li jiecong]

a=~x

number=0

x--;

while( a & x){

number++;

x--;

}

 

On 11/15/07, SpitFire <spit...@gmail.com> wrote:

计算出正整数N二进制1的个数

--
SpitFire

[li jiecong]

错了 应该是这样吧

 

number = 0;

if ( 1==x){

    number = 1;

}

 

while( ~x & (x-1)){

     number ++

     x &=(x-1)

[SpitFire]

基本上是这样了
int i = 0;
while( n &= n-1) ++i;

在07-11-15，li jiecong <liji...@gmail.com> 写道：

--
SpitFire

[SpitFire]

哦，i = 1，do while是i = 0

2007/11/15, SpitFire <spit...@gmail.com>:

--
SpitFire

[hayate]

n = 0呢？
这时 i 应该等于 0

[oldrev]

有点意思

[SpitFire]

这个移植性相对不那么好，不过性能倒是不是，在linux源码里有专门的宏

在07-11-16，oldrev <old...@gmail.com> 写道：

--
SpitFire