整数をすばやく計算するバイナリ表現の1の個数

題目:1つの符号の32ビットの整数xを与えて、xのバイナリの表現法の中で1の個数を求めますか?
1つ目のアルゴリズム:

int OneCount(unsigned int x)
{
  for(int count=0; x>0; count++)
    x&=x-1;//     1 0
  return count;
}

上のアルゴリズムの時間複雑度は1の個数である.
2番目のアルゴリズム(ルックアップ):

const int idx[256]={0,1,1,,8}//0~255  1   
int OneCount(unsigned int x)
{
  int count=0;
  for(; x>0; x>>=8)
     count+=idx[x&255];
  return count;
}

上記のアルゴリズムは最大4サイクルで,空間交換時間を用いる.
2番目のアルゴリズムの別の形式:

const int idx[256]={0,1,1,..,8}
int OneCount(unsigned int x)
{
  unsigned char* p=(unsigned char*)&x;
  return idx[*p]+idx[*(p+1)]+idx[*(p+2)]+idx[*(p+3)];
}

3つ目のアルゴリズム:

int OneCount(unsigned int x)
{
  x=(x&0x55555555UL)+((x>>1)&0x55555555UL); //1
  x=(x&0x33333333UL)+((x>>2)&0x33333333UL);//2
  x=(x&0x0f0f0f0fUL)+((x>>4)&0x0f0f0f0fUL); //3
  x=(x&0x00ff00ffUL)+((x>>8)&0x00ff00ffUL); //4
  x=(x&0x0000ffffUL)+((x>>16)&0x0000ffffUL);//5
  return x;
}

例えば、8ビットの整数122について、0111 1010(abcd efgh)をバイナリで表し、1行目のコードの機能はx=0 b 0 d 0 f 0 h+0 a 0 c 0 e 0 gであり、2桁の1組で、それぞれ4組(a,b;c,d;e,f;g,h;)のうち1の個数を計算し、この例ではx=101,000+0001 0101=0101(更新されたabcd efgh)であり、これに基づいて、さらにグループ化し、2行目の機能x=00 cd 00 gh+00 ab 00 ef,4桁の1組である(abcd;efgh)は、この例ではx=0100001+0001=0001=00011 0010(abcd efghを更新する)の2つのグループが1を含む個数をそれぞれ計算し、さらに8ビットのグループが、3行目に示すようにx=0000 efgh+0000 abcd=000100+000001=0000101=5であるため、この整数122は5つの1を含む.
本アルゴリズムの考え方:集計して、1つの32ビットの整数に対して、まず16グループに分けて、各グループ(2ビット)の中の1の個数を統計して、更に統計の結果を2つ合併して、8グループを得て、その上でまた合併して4グループ、2グループ、1グループを得て、更に最終結果を得ます.