Challenge: Bitmap Centroid

I'd like to calculate the centro开发者_如何学JAVAid of a bitmap (black and white) stored as a bit-packed array of integers. I know there are fast algorithms for counting the number of set bits in an integer, but this doesn't help me calculate a centroid. Any ideas?

As an example, if my bitmap looks like this:

111000
111000
111000
000000
000000
000000

The centroid is at 1, 1. Packed into 32 bit integers (you choose the Endian), it might look like this: {width: 6, height: 6} { 3817734144, 0 }.

Bonus points if you can also get the mass (9 in the example) without iterating over each bit.

Let's assume you're going to process this a row at a time. (Once you've got the total mass, and center of mass of each row, it's a weighted average to get the x and y coordinates of the centroid).

So in other words you've got a row of bits b_i and you want to calculate the sum of b_if(i) for some functions f. If f(i)=1, that's the bit count (let's call that C), and if f(i)=i, it'll give the total moment of the mass M (which you'll divide by C to get the center of mass).

For inputs less than 8 bits, you can easily store tables for C and M, each 256 bytes wide. Let's write numbers bigger than 8 bits as h:l, where l is the lower 8 bits of the number, and h is the rest of the bits.

Then

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)

the only tricky bit being the 8C(h), corresponding to those C(h) bits being shifted down 8 places when we calculated M(h) instead of M(h:0).

Non-recursively, if your input as bytes is 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) + ...

and then you can pass M and C to average over all lines.