我的嵌入式系统具有128KB内存阵列结构，用于特定用途
每个 2 位代表 4 状态(状态 0、状态 1、状态 2、状态 3)
我想计算内存数组中的总状态 3 (0b11)
例如0xFF001234 = 1111 1111 0000 0000 0001 00100011 0100
它计数 5 (0b11)
我搜索了算法，但它只计算一位 - https://www.geeksforgeeks.org/count-set-bits-in-an-integer/
我希望避免贪婪的算法，例如每 2 位比较 0b11
有人有好主意吗？
ps ： 我使用的是 LEON3 Sparc V8 32 位处理器，使用 C 语言
您有一个数组uint32_t states[]其中每个state[i]代表 16 个状态？
要计算变量uint32_t s中0b11状态的数量，可以使用以下方法：
首先，预处理s使得每个状态0b11只导致一个1位，所有其他状态导致0位。然后数1位数。
预处理
将s拆分为l每个状态的左位和r的右位。
s AB CD EF GH IJ LM NO PQ RS TU VW XY ZΓ ΔΠ ΦΨ ДЖ
l = s & 0xAAAAAAAA = A0 C0 E0 G0 I0 L0 N0 P0 R0 T0 V0 X0 Z0 Δ0 Φ0 Д0
r = s & 0x55555555 = 0B 0D 0F 0H 0J 0M 0O 0Q 0S 0U 0W 0Y 0Γ 0Π 0Ψ 0Ж
然后将l位对齐并r。
(l >>> 1) = 0A 0C 0E 0G 0I 0L 0N 0P 0R 0T 0V 0X 0Z 0Δ 0Φ 0Д
r = 0B 0D 0F 0H 0J 0M 0O 0Q 0S 0U 0W 0Y 0Γ 0Π 0Ψ 0Ж
最后，使用&获取1位当且仅当状态为0b11时
(l >>> 1) & r = 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0?
这里?1相应的状态是否0b11，否则0。
简化公式(s >>> 1) & s & 0x55555555可以获得相同的结果。
位计数
要计算s中的0b11状态，我们只需要计算1位(s >>> 1) & s & 0x55555555.
位计数可以在没有循环的情况下完成，如《黑客的喜悦》一书第5章或Stackoverflow答案中所述。
此处显示的方法仅适用于单个数组元素。要计算整个数组中的状态，请遍历其元素。
优化
正如 Lundin 在评论中指出的那样，如果您的处理器无法uint32_t放入其寄存器中，则操作(s >>> 1)可能会很昂贵。在这种情况下，明智的做法是声明您的数组states[]不是uint32_t而是在您的处理器上最有效的任何数组 - 过程保持不变，您只需要使用或多或少的555…。如果由于某种原因您无法更改数组的类型，您仍然可以像访问其他类型一样访问它，请参阅如何在 C 中将 int 数组转换为字节数组。