ビットカウントの速さ
ビットカウントで、分割統治法と呼ばれるものと、テーブルを使ったものとではどちらが早いのかテストしてみました。以下JavaScriptでのコード
function hammingWeight1(number) { number = (number & 0x55555555) + ((number >>> 1) & 0x55555555); number = (number & 0x33333333) + ((number >>> 2) & 0x33333333); number = (number & 0x0F0F0F0F) + ((number >>> 4) & 0x0F0F0F0F); number = (number & 0x00FF00FF) + ((number >>> 8) & 0x00FF00FF); return (number & 0x0000FFFF) + ((number >>>16) & 0x0000FFFF); } var weightTable = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8]; function hammingWeight2(n) { return weightTable[n>>>24] + weightTable[(n>>>16) & 15] + weightTable[(n>>>8) & 15] + weightTable[n & 15]; } var d, i, t1, t2; d = new Date; for (i = 0; i < 100000; ++i)hammingWeight1(4294967295-i); t1 = (new Date).getTime() - d.getTime(); d = new Date; for (i = 0; i < 100000; ++i)hammingWeight2(4294967295-i); t2 = (new Date).getTime() - d.getTime(); alert([t1,t2]);
Firefox3.6ではテーブルのほうが早かったですが、それ以外は計算のほうが早かったです。
C言語で書いてWindowsで実行したらテーブルのほうが早かったです。