c - 在内存阵列中选择一对位(0b11)

我的嵌入式系统具有128KB的内存阵列结构，用于特定目的

每个2位代表4状态（状态0，状态1，状态2，状态3）

我想计算内存阵列中的总状态3（0b11）

例如0xFF001234 = 1111 1111 0000 0000 0001 0010 0011 0100

数5（0b11）

我搜索了算法，但只算一位
-https://www.geeksforgeeks.org/count-set-bits-in-an-integer/

我希望避免贪婪算法，例如每2位比较0b11

有人有好主意吗？

ps：我正在使用C语言使用LEON3 Sparc V8 32位处理器

最佳答案

您有一个数组uint32_t states[]，其中每个state[i]代表16个状态？

要计算变量0b11中的uint32_t s状态数，可以使用以下方法：

首先，对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可以达到相同的结果。

位计数

要计算0b11中的s状态，我们只需要计算1位中的
(s >>> 1) & s & 0x55555555。

如本书Hacker's Delight, chapter 5或本Stackoverflow answer所述，可以无循环地进行位计数。

此处显示的方法仅适用于单个数组元素。要计算整个数组中各个元素的状态。

优化

正如Lundin在评论中指出的那样，如果处理器不能将(s >>> 1)装入其寄存器，则uint32_t操作可能会很昂贵。在这种情况下，明智的是将数组states[]声明为不是uint32_t，但是将其声明为最适合您的处理器的方法–该过程保持不变，只需使用或多或少的555…。如果由于某种原因您无法更改数组的类型，仍然可以像访问其他类型一样访问它，请参见how to cast an int array to a byte array in C。