プログラミングの美しさ2.1バイナリの中の1の個数を求めます
1199 ワード
最近しばらく、ずっとプログラミングの美しさなどのアルゴリズムの本を読んでいて、プログラミングの美しさを見始めたばかりで、難しさを感じて、时にはこの本をめくりたくないこともありますが、しばらくの間の修練を経て、私も徹底的にこの本が好きになりました.本の中のアルゴリズムは多くの方面に及んで、木、チェーン時計、ビット演算、配列、hashテーブルアプリケーションなど.
最近仕事も忙しくて、プログラミングの美しさのアルゴリズムを書き直して、ここで記録して、後で読むのが便利になりました.
最初の問題は2.1から書きます.この問題は難しくありません.まず、この問題の関数宣言を与えます.
ここでは、2つの非常に一般的で非常に良いアルゴリズムの実装を示しています.コードにはコメントが追加されているので、私は直接コードを貼り付けます.
最近仕事も忙しくて、プログラミングの美しさのアルゴリズムを書き直して、ここで記録して、後で読むのが便利になりました.
最初の問題は2.1から書きます.この問題は難しくありません.まず、この問題の関数宣言を与えます.
/*2.1 1 */
int DutCountOf1InBin_1(unsigned int);
int DutCountOf1InBin_2(unsigned int);
ここでは、2つの非常に一般的で非常に良いアルゴリズムの実装を示しています.コードにはコメントが追加されているので、私は直接コードを貼り付けます.
/* */
int DutCountOf1InBin_1(unsigned int v)
{
/* 1 */
int count = 0;
while (v)
{
++count;
/* 1( )*/
v &= (v - 1);
/* 2 :v > 0 && (v & (v - 1) == 0)*/
}
return count;
}
/* */
int DutCountOf1InBin_2(unsigned int v)
{
/* 1 , 1 */
v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
return v;
}