整数のビットパック配列として格納されているビットマップ (白黒) の重心を計算したいと思います。整数に設定されたビット数をカウントするための高速なアルゴリズムがあることは知っていますが、これは重心の計算には役立ちません。何か案は？
例として、私のビットマップが次のようになっているとします。
111000
111000
111000
000000
000000
000000
重心は 1, 1 です。32 ビット整数 (エンディアンを選択) にパックすると、{幅: 6, 高さ: 6} { 3817734144, 0 } のようになります。
各ビットを反復せずに質量 (例では 9) も取得できる場合のボーナス ポイント。
これを一度に 1 行ずつ処理するとします。(総質量と各行の重心を取得したら、重心の x 座標と y 座標を取得する加重平均です)。
つまり、ビット b iの行があり、いくつかの関数 f について b i f(i)の合計を計算したいとします。f(i)=1 の場合、それがビット カウント (C と呼びましょう) であり、f(i)=i の場合、質量 M の総モーメントが得られます (これを C で割ると、重心）。
8 ビット未満の入力の場合、C と M のテーブルをそれぞれ 256 バイト幅で簡単に格納できます。8 ビットより大きい数値を h:l と書きましょう。ここで、l は数値の下位 8 ビットで、h は残りのビットです。
それで
C(h:l) = C(h:0) + C(0:l) = C(h) + C(l)
M(h:l) = M(h:0) + M(0:l) = M(h) + 8C(h) + M(l)
唯一のトリッキーなビットは 8C(h) です。これは、M(h:0) ではなく M(h) を計算したときに、これらの C(h) ビットが 8 桁下にシフトされたことに対応します。
バイトとしての入力が x0、x1、x2、x3...の場合、非再帰的に。
C(x) = C(x0) + C(x1) + C(x2) + C(x3) + ...
M(x) = M(x0) + M(x1) + M(x2) + M(x3) + ...
+8C(x1) + 16C(x2) + 24C(x3) + ...
次に、M と C を渡して、すべての行の平均を得ることができます。