無(wú)分支版的你這個(gè)快，原理是遞歸求二進(jìn)位相鄰兩位的和。  回復(fù)  更多評(píng)論
  

@codespy
無(wú)分支版的 比 你這個(gè)快，原理是遞歸求二進(jìn)位相鄰兩位的和。  回復(fù)  更多評(píng)論
  

@codespy

這個(gè)我還真的沒(méi)有想到.
你說(shuō)的是這種么?
int numOnesInBinary3(int num)
{
num = num - ((num >> 1) & 0x55555555);
num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
num = (num+ (num >> 4)) & 0x0F0F0F0F;
num = num + (num >> 8);
num = num + (num >> 16);
return num & 0x0000003F;
}

我是在http://bvcat007.javaeye.com/blog/203577中看到的,原理是利用二分法，兩兩一組相加，之后四個(gè)四個(gè)一組相加，接著八個(gè)八個(gè)，最后就得到各位之和了。

他還提供了一種是
int numOnesInBinary4(int num)
{
unsigned n;
n = (num >> 1) & 033333333333;
num = num - n;
n = (n >> 1) & 033333333333;
num = num - n;
num = (num + (num >> 3)) & 030707070707;
num = num% 63;

return num;
}
首先是將二進(jìn)制各位三個(gè)一組，求出每組中1的個(gè)數(shù)，然后相鄰兩組歸并，得到六個(gè)一組的1的個(gè)數(shù)，最后很巧妙的用除63取余得到了結(jié)果。因?yàn)?^6 = 64，也就是說(shuō) x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，這里的等號(hào)表示同余。

  回復(fù)  更多評(píng)論