プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

1の個数を数えよう

数値の中にある1の数の数え方について。
プログラム中でint型を32個のboolean型が入った物だと考えてプログラムを組むところがあって、trueの数を数える必要があったのでこんな記事を書くことにしました。
数える値がaの時

int sum=0;
for(int i=0;i<32;i++) sum +=  ( a>>i )&1;

はい、これが最も駄目な奴ね。こんなの書くぐらいならせめてループ外して32行手作業でかけっての。
こんなの考えるの誰だろうね。ホント馬鹿なんだろうね。何考えて21年生きてたんだろうね。死ねばいいのにね。生まれてきてごめんなさい

正解はこちら
int sum = (a & 0x55555555) + ( (a>>1) & 0x55555555);
sum = (sum & 0x33333333) + ( (sum>>2) &0x33333333);
sum = (sum & 0x0f0f0f0f) + ( (sum>>4) & 0x0f0f0f0f);
sum = (sum & 0x00ff00ff) + ( (sum>>8) & 0x00ff00ff);
sum = (sum & 0x0000ffff) +(sum >>> 16);

先に示した方が短く見えるけど、実際には32回計算とループしているのに対し、こちらは僅かに5回の計算量。すごいよね。このアルゴリズム考えた人。

ちなみに、JAVAにはIntegerクラスにbitCountという関数で同じアルゴリズムで実装されていますので、そっちを使った方が実行速度的にも早いです。

お馬鹿な私ですが簡単に解説させて頂きます。
まず、16進数55555555を2進数に直すと
01010101010101010101010101010101
16進数33333333を2進数に直すと
00110011001100110011001100110011
16進数0f0f0f0fを2進数に直すと
00001111000011110000111100001111
16進数00ff00ffを2進数に直すと
00000000111111110000000011111111

となります。なんとなく規則性は見えると思います。

まず、最初の55555555との計算は簡単に言えば、32個の0,1の数列を2つずつに分けてその中にそれぞれ何個の1があるか計算しています。

00の場合 0
01の場合 (01&01) + ((01 >>1) &01)= 01+ (?0 &01) =01  (= 1)
10の場合 (10&01) + ((10 >>1) &01)= 00+ (?1 &01) =01  (= 1)
11の場合 (11&01) + ((11 >>1) &01)= 01+ (?1 &01) =10  (= 2)
?は0か1

これで無秩序に並んでいた0,1数列が個数を表す数列に変わりました。

次の33333333との計算は先ほどの隣り合う個数を足し合わせる行為になります。

例)1110の場合
まず、最初の手順で1001に変わる
(1001&0011) + ((1001 >>2) & 0011) = 0001 + (??10 &0011) = 0001 + 0010 = 0011 (=3)

よって、この4つの中に1は3つあると、ちゃんと示せていますね。
以下も同様の考え方で最終的に隣がなくなる(ブロックが1つになる)までくり返すだけです。