よくある面接のアルゴリズムの問題:1つのByteの中の“1”の個数を統計します

題目説明:1バイト(8 bit)の符号なし整形変数に対して、バイナリ表現の中の“1”の個数を求めて、アルゴリズムの実行効率ができるだけ高いことを要求します

java         
<<      :          ，num << 1,   num  2
>>      :          ，num >> 1,   num  2
>>>     :          ，     ，    0  

方法1:直接的な方法は2を除いて右にシフトし、1つずつ統計することであるが、型取りと相殺に用いられ、これは資源を消費する.

int Count(BYTE v)
{
int num=0;
while (v) 
{
   if (v%2==1)
   {
    num++;
   }
   v=v/2;
}
return num;
}

方法2:ビット操作を用いて、2を除いて直接ビット操作で右に1ビットシフトすることで実現でき、シフト操作を計算する効率は除算より高い.

int Count(BYTE v)
{
int num=0;
while (v)
{
   num+=v & 0x01; // v 00000001    v      1      1，    0。
   v>>=1;    //    。
}
return num;
}

メソッド3:ビット操作を使用しますが、1の個数を統計するだけで、ループの回数はBYTEの中の1の個数で、遍歴する必要はありません.

int Count(BYTE v)
{
int num=0;
while (v)
{
   v &=(v-1);   //v=v&(v-1)           v      1。
   num++;
}
return num;
}