我想计算存储为位打包整数数组的位图(黑白)的质心。我知道有一些快速算法可以计算整数中设置的位数，但这并不能帮助我计算质心。有任何想法吗？
例如，如果我的位图如下所示:
111000
111000
111000
000000
000000
000000
质心位于 1, 1。打包成 32 位整数(您选择 Endian)，它可能看起来像这样:{width: 6, height: 6} { 3817734144, 0 }。
如果您还可以在不迭代每一位的情况下获得质量(示例中为 9)，则加分。
最佳答案
假设您要一次处理一行。 (一旦你得到了每行的总质量和质心，它就是一个加权平均值来获得质心的 x 和 y 坐标)。
所以换句话说，你有一行位 bi 并且你想计算一些函数 f 的 bif(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) 而不是 M(h:0) 时，那些 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 对所有行进行平均。
关于algorithm - 挑战 : Bitmap Centroid，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5329080/