「2進数の中の1の個数を求めます」
【一】「2進数のうち1の個数を求める」いくつかの方法
[から]http://blog.csdn.net/justpub/article/details/2292823]
バイナリの中の1の個数を求めます.1バイト(8 bit)の変数に対して,そのバイナリ表現における「1」の個数を求めるには,アルゴリズムの実行効率が可能な限り高いことが要求される.
まず、サンプル章に示されているいくつかのアルゴリズムを見てみましょう.
解法1、毎回2を除いて、奇数かどうかを見て、そうであれば累計して1を加えて、最後にこの結果はバイナリ表現の中の1の個数です.
解法2は,同様に1サイクルを用いたが,中の操作は変位操作で簡略化された.
解法の3、1つの巧みな操作を使って、v & (v -1 )バイナリ表現の最後の1を消すたびに,このテクニックを利用して一定のサイクル数を減らすことができる.
解法四、チャート法、データ8 bitしかないので、直接表を作って、各数の中の1の個数を含んで、それからチャートすればいいです.複雑度O(1).
はい、これがサンプル章で与えられた4つの案です.次に私の見方を話します.
まずアルゴリズムの測定において、複雑度は本当に唯一の基準ですか?特にこのようなデータ規模が与えられ、しかも小さい場合、複雑度は実は比較的二次的な要素です.
ルックアップ法の複雑度はO(1)で、私は解法1を用いて、8回循環して固定して、複雑度もO(1)です.データ規模が大きくなって32ビット型になると、ルックアップ法も自然に適切ではありません.
次に、このような小さな操作である以上、測定の尺度も必然的に小さくなると思います.CPUクロックサイクルは参考になります.
解法1には数回の整数加算、数回の整数除算(一般的なコンパイラでは変位に最適化できます)、いくつかのサイクル分岐判断、いくつかのパリティ判断(これは時間がかかりますが、CSAPPのデータによると、一般的にはbranch penaltyは14個くらいのcycleを消費しなければなりません)、合わせて数十個くらいのcycleでしょう.
さらに解法4を見ると,ルックアップ法は1回のアドレス計算で解決できるように見えるが,実際にはここで1つのアクセス操作が用いられ,1回目のアクセス時にその配列がcacheに含まれていない可能性が高い,というcacheが用いられる. missによる結果は、メモリにアクセスするために数十個以上のcycleを消費する可能性があります.このような「小さな操作」では、このアルゴリズムのパフォーマンスは実際には悪いです.
ここでは、32ビットの符号なし整数を例に、この問題を解決するアルゴリズムをいくつかお勧めします.
ここでは二分法を使って、二つと一つのグループを加えて、それから4つの4つのグループを加えて、それから8つの8つを加えて、最後に各位の和を得ました.
もっと巧妙なHAKMEMアルゴリズムがあります
まずバイナリ各位を3つずつグループ化し,各グループの1つの数を求め,隣接する2つのグループをまとめて6つのグループの1つの数を得,最後に63を巧みに用いて余りを取って結果を得た.
2^6なので = 64、つまり x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)、ここの等号は同余を表す.
このプログラムは10個程度の命令しか必要とせず、アクセスもせず、速度が速い.
このことから,1つのアルゴリズムの実際の効果を測定するには複雑さだけでなく,他の状況と結びつけて具体的に分析しなければならない.
後の2つの拡張問題について、1つは32ビット整数型にどのように処理するかを聞くことであり、これはすでに述べた.
問題2は2つの整数AとBを与えて、AとBが何桁あるかを聞くのは違います.
この問題は実は1を数える問題に1つのステップが多くなったので、まずAとBの異或結果を算出して、それからこの値の中の1の個数を求めればいいのです.
【二】MIT HAKMEMアルゴリズム分析
[から]http://blog.csdn.net/msquare/article/details/4536388]
今日は興味深いBitCountアルゴリズムであるMIT HAKMEMアルゴリズムを学びました.
本文中^は乗を表す
質問要件:32ビット整数の'1'の個数を計算
構想分析:
1.整数 iの数値は、実際には重みを乗じたものです.つまり、2をベースにした多項式です.
i = A0*2^0+A1*2^1+A2*2^2+...
したがって、1の桁数を要求するのは、実際には皆さんを消権する限りです.
i = A0+A1+A2+...
得られた係数の和は‘1’の個数である.
2.任意の自然数nのN次べき乗に対して、n-1で模式得数を1とし、以下のように証明する.
n^(k-1)%(n-1)=1が成立すると
n^k%(n-1) = ((n-1)*n^(k-1) + n^(k-1)) % (n-1) = 0 + n^(k-1) % (n-1) = 1も成り立つ
またn^(1-1)%(n-1)=1
従って任意の非負の整数N,n^Nに対して %(n-1)=1
3.したがって、係数が{Ai}のnをベースとした多項式P(N)、P(N)%(n-1)=(sum({Ai})))%(n-1) ;
sum({Ai})<(n−1)が保証できれば、P(N)%(n−1)=(sum({Ai})) ,すなわち,このときn−1対の多項式で型をとるだけで,消権が完了し,係数和が得られる.
そこで,問題は,2をベースとする多項式をnをベースとする多項式に変換し,nはn−1>sum({Ai})が一定に成り立つように十分大きくする.
32ビット整数数では、Ai=0または1、sum({Ai})<=32、n−1>32、nは33より大きい必要がある.
従ってn=2^6=64>33を新しい多項式の底とする.
4.32ビットの2進数の6ビットごとを1単位とし、64をベースとした多項式と見なす.
i = t0*64^0 + t1*64^1 + t2*64^2 + t3*64^3 + ...
各係数tiは6ビットあたり2進数の値である.
このように、演算により、各単位における6ビット数をこの6ビットに含まれる‘1’の個数に変更し、さらに63で型をとることにより、求められた合計の‘1’の個数を得ることができる.
5.いずれかの6ビット数tiを考慮すると、最も簡単な方法は明らかに1ビットごとにmaskを行い、加算することである.
(ti>>5)&(000001) + (ti&>>4)(000001) + (ti>>3)&(000001) + (ti>>2)&(000001) + (ti>>1)&(000001) + ti&(000001)
そのうち000001ビット2進数
Tiは最大6個の1を含むため、上式の最大値は000110であり、決してオーバーフローは発生しないため、上式の操作は完全に整数数に直接対応することができる. iはスイートであり、操作中にt 0〜t 6は並列に上式の演算を完了する.
注意:&演算を先に+後に抽出することはできません.なぜか考えてみましょう.
したがって、bit countの実装コードは以下の通りである.
しかし、MIT HAKMEMの最終的なアルゴリズムは、上記のコードよりも簡単です.
なぜ上の式では(ti>>k)を先に抽出して加算してから&演算を行うことができないのでしょうか.
&(000001)でMASKを行った後、有効ビットは1ビットしかないので、6桁のうち'1'の個数が1ビットを超えると、「先付け」の過程で得数が最下位から上へあふれ出す.
しかし,6桁のうち最大6個の‘1’,すなわち000110個であり,3桁の有効ビットしか必要としないことに気づいた.上の式は実際には1桁単位で‘1’の個数を抽出して加算して6桁の‘1’の総個数を求めるので,&(000001)を用いる..3ビット単位で‘1’の個数を算出して加算すると、完全にMASKを加算することができます.アルゴリズムは以下の通りです.
tmp = (ti>>2)&(001001) + (ti>>1)&(001001) + ti&(001001)
(tmp + tmp>>3)&(000111)
Cコード:
注:コードでは8進数でMASKを行い、11桁の8進数は33桁の2進数で1桁多いので、1桁目の8進数はint長を超えないように一番高い桁を切り捨てます(7->3).
1つ目のバージョンから2つ目までは、実は「公因式抽出」のプロセスです.3つのグループを1つのグループ+,>>,&演算で置き換えました.そして「最大公因式」が抽出されました.しかし、これは最終的なMIT HAKMEMアルゴリズムではありませんが、非常に近いので、世代コードを見てみましょう.
MIT HAKMEMアルゴリズム:
また1組の+,>,&演算が減少した.最適化されたのは3ビット2進数「グループ」内の計算である.さらに多項式に戻り、1つの3ビット2進数は4 a+2 b+cであり、我々が要求したいのはa+b+cであり、n>>1の結果は2 a+bであり、n>>2の結果はaである.
すると:(4 a+2 b+c)-(2 a+b)-(a)=a+b+c
中央のMASKは「グループ間」「クロストーク」を遮断するため、左グループの下位から移動してきた数を遮断する.
[から]http://blog.csdn.net/justpub/article/details/2292823]
バイナリの中の1の個数を求めます.1バイト(8 bit)の変数に対して,そのバイナリ表現における「1」の個数を求めるには,アルゴリズムの実行効率が可能な限り高いことが要求される.
まず、サンプル章に示されているいくつかのアルゴリズムを見てみましょう.
解法1、毎回2を除いて、奇数かどうかを見て、そうであれば累計して1を加えて、最後にこの結果はバイナリ表現の中の1の個数です.
解法2は,同様に1サイクルを用いたが,中の操作は変位操作で簡略化された.
int Count(int v)
{
int num = 0;
while (v)
{
num += v & 0x01;
v >>= 1;
}
return num;
} 解法の3、1つの巧みな操作を使って、v & (v -1 )バイナリ表現の最後の1を消すたびに,このテクニックを利用して一定のサイクル数を減らすことができる.
解法四、チャート法、データ8 bitしかないので、直接表を作って、各数の中の1の個数を含んで、それからチャートすればいいです.複雑度O(1).
int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };
int Count(int v)
{
return countTable[v];
}はい、これがサンプル章で与えられた4つの案です.次に私の見方を話します.
まずアルゴリズムの測定において、複雑度は本当に唯一の基準ですか?特にこのようなデータ規模が与えられ、しかも小さい場合、複雑度は実は比較的二次的な要素です.
ルックアップ法の複雑度はO(1)で、私は解法1を用いて、8回循環して固定して、複雑度もO(1)です.データ規模が大きくなって32ビット型になると、ルックアップ法も自然に適切ではありません.
次に、このような小さな操作である以上、測定の尺度も必然的に小さくなると思います.CPUクロックサイクルは参考になります.
解法1には数回の整数加算、数回の整数除算(一般的なコンパイラでは変位に最適化できます)、いくつかのサイクル分岐判断、いくつかのパリティ判断(これは時間がかかりますが、CSAPPのデータによると、一般的にはbranch penaltyは14個くらいのcycleを消費しなければなりません)、合わせて数十個くらいのcycleでしょう.
さらに解法4を見ると,ルックアップ法は1回のアドレス計算で解決できるように見えるが,実際にはここで1つのアクセス操作が用いられ,1回目のアクセス時にその配列がcacheに含まれていない可能性が高い,というcacheが用いられる. missによる結果は、メモリにアクセスするために数十個以上のcycleを消費する可能性があります.このような「小さな操作」では、このアルゴリズムのパフォーマンスは実際には悪いです.
ここでは、32ビットの符号なし整数を例に、この問題を解決するアルゴリズムをいくつかお勧めします.
ここでは二分法を使って、二つと一つのグループを加えて、それから4つの4つのグループを加えて、それから8つの8つを加えて、最後に各位の和を得ました.
もっと巧妙なHAKMEMアルゴリズムがあります
int Count(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
} まずバイナリ各位を3つずつグループ化し,各グループの1つの数を求め,隣接する2つのグループをまとめて6つのグループの1つの数を得,最後に63を巧みに用いて余りを取って結果を得た.
2^6なので = 64、つまり x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)、ここの等号は同余を表す.
このプログラムは10個程度の命令しか必要とせず、アクセスもせず、速度が速い.
このことから,1つのアルゴリズムの実際の効果を測定するには複雑さだけでなく,他の状況と結びつけて具体的に分析しなければならない.
後の2つの拡張問題について、1つは32ビット整数型にどのように処理するかを聞くことであり、これはすでに述べた.
問題2は2つの整数AとBを与えて、AとBが何桁あるかを聞くのは違います.
この問題は実は1を数える問題に1つのステップが多くなったので、まずAとBの異或結果を算出して、それからこの値の中の1の個数を求めればいいのです.
【二】MIT HAKMEMアルゴリズム分析
[から]http://blog.csdn.net/msquare/article/details/4536388]
今日は興味深いBitCountアルゴリズムであるMIT HAKMEMアルゴリズムを学びました.
本文中^は乗を表す
質問要件:32ビット整数の'1'の個数を計算
構想分析:
1.整数 iの数値は、実際には重みを乗じたものです.つまり、2をベースにした多項式です.
i = A0*2^0+A1*2^1+A2*2^2+...
したがって、1の桁数を要求するのは、実際には皆さんを消権する限りです.
i = A0+A1+A2+...
得られた係数の和は‘1’の個数である.
2.任意の自然数nのN次べき乗に対して、n-1で模式得数を1とし、以下のように証明する.
n^(k-1)%(n-1)=1が成立すると
n^k%(n-1) = ((n-1)*n^(k-1) + n^(k-1)) % (n-1) = 0 + n^(k-1) % (n-1) = 1も成り立つ
またn^(1-1)%(n-1)=1
従って任意の非負の整数N,n^Nに対して %(n-1)=1
3.したがって、係数が{Ai}のnをベースとした多項式P(N)、P(N)%(n-1)=(sum({Ai})))%(n-1) ;
sum({Ai})<(n−1)が保証できれば、P(N)%(n−1)=(sum({Ai})) ,すなわち,このときn−1対の多項式で型をとるだけで,消権が完了し,係数和が得られる.
そこで,問題は,2をベースとする多項式をnをベースとする多項式に変換し,nはn−1>sum({Ai})が一定に成り立つように十分大きくする.
32ビット整数数では、Ai=0または1、sum({Ai})<=32、n−1>32、nは33より大きい必要がある.
従ってn=2^6=64>33を新しい多項式の底とする.
4.32ビットの2進数の6ビットごとを1単位とし、64をベースとした多項式と見なす.
i = t0*64^0 + t1*64^1 + t2*64^2 + t3*64^3 + ...
各係数tiは6ビットあたり2進数の値である.
このように、演算により、各単位における6ビット数をこの6ビットに含まれる‘1’の個数に変更し、さらに63で型をとることにより、求められた合計の‘1’の個数を得ることができる.
5.いずれかの6ビット数tiを考慮すると、最も簡単な方法は明らかに1ビットごとにmaskを行い、加算することである.
(ti>>5)&(000001) + (ti&>>4)(000001) + (ti>>3)&(000001) + (ti>>2)&(000001) + (ti>>1)&(000001) + ti&(000001)
そのうち000001ビット2進数
Tiは最大6個の1を含むため、上式の最大値は000110であり、決してオーバーフローは発生しないため、上式の操作は完全に整数数に直接対応することができる. iはスイートであり、操作中にt 0〜t 6は並列に上式の演算を完了する.
注意:&演算を先に+後に抽出することはできません.なぜか考えてみましょう.
したがって、bit countの実装コードは以下の通りである.
int bitcount(unsigned int n)
{
unsigned int tmp;
tmp = (n &010101010101)
+((n>>1)&010101010101)
+((n>>2)&010101010101)
+((n>>3)&010101010101)
+((n>>4)&010101010101)
+((n>>5)&010101010101);
return (tmp%63);
}しかし、MIT HAKMEMの最終的なアルゴリズムは、上記のコードよりも簡単です.
なぜ上の式では(ti>>k)を先に抽出して加算してから&演算を行うことができないのでしょうか.
&(000001)でMASKを行った後、有効ビットは1ビットしかないので、6桁のうち'1'の個数が1ビットを超えると、「先付け」の過程で得数が最下位から上へあふれ出す.
しかし,6桁のうち最大6個の‘1’,すなわち000110個であり,3桁の有効ビットしか必要としないことに気づいた.上の式は実際には1桁単位で‘1’の個数を抽出して加算して6桁の‘1’の総個数を求めるので,&(000001)を用いる..3ビット単位で‘1’の個数を算出して加算すると、完全にMASKを加算することができます.アルゴリズムは以下の通りです.
tmp = (ti>>2)&(001001) + (ti>>1)&(001001) + ti&(001001)
(tmp + tmp>>3)&(000111)
Cコード:
int bitcount(unsigned int n)
{
unsigned int tmp;
tmp = (n &011111111111)
+((n>>1)&011111111111)
+((n>>2)&011111111111);
tmp = (tmp + (tmp>>3)) &030707070707;
return (tmp%63);
}注:コードでは8進数でMASKを行い、11桁の8進数は33桁の2進数で1桁多いので、1桁目の8進数はint長を超えないように一番高い桁を切り捨てます(7->3).
1つ目のバージョンから2つ目までは、実は「公因式抽出」のプロセスです.3つのグループを1つのグループ+,>>,&演算で置き換えました.そして「最大公因式」が抽出されました.しかし、これは最終的なMIT HAKMEMアルゴリズムではありませんが、非常に近いので、世代コードを見てみましょう.
MIT HAKMEMアルゴリズム:
int bitcount(unsigned int n)
{
unsigned int tmp;
tmp = n
- ((n >> 1) & 033333333333)
- ((n >> 2) & 011111111111);
tmp = (tmp + (tmp >> 3)) & 030707070707
return (tmp%63);
}また1組の+,>,&演算が減少した.最適化されたのは3ビット2進数「グループ」内の計算である.さらに多項式に戻り、1つの3ビット2進数は4 a+2 b+cであり、我々が要求したいのはa+b+cであり、n>>1の結果は2 a+bであり、n>>2の結果はaである.
すると:(4 a+2 b+c)-(2 a+b)-(a)=a+b+c
中央のMASKは「グループ間」「クロストーク」を遮断するため、左グループの下位から移動してきた数を遮断する.