在内存数组中选择一对位（0b11）
pick pair of bit (0b11) in memory array
我的嵌入式系统有 128KB 内存阵列结构用于特定用途
每2bit代表4个state(state 0,state 1,state 2,state 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 : 我用的是LEON3 Sparc V8 32bit处理器，用的是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Ж
最后，当且仅当状态为 0b11.
时，使用 & 获得 1 位
(l >>> 1) & r = 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0?
这里 ? 如果相应的状态是 0b11 则 1 否则 0 否则。
通过简化公式 (s >>> 1) & s & 0x55555555.
可以得到相同的结果
位计数
要计算 s 中的 0b11 个状态，我们只需计算 1 中的位
(s >>> 1) & s & 0x55555555.
如书中所述，无需循环即可进行位计数 Hacker's Delight, chapter 5 or in this Whosebug answer。
此处显示的方法仅适用于单个数组元素。要计算整个数组中的状态，请循环遍历其元素。
优化
正如 Lundin 在评论中指出的那样，如果您的处理器无法将 uint32_t 放入其寄存器，则操作 (s >>> 1) 可能会很昂贵。在这种情况下，将数组 states[] 声明为不是 uint32_t 是明智的，但无论哪种方式在您的处理器上最有效——过程保持不变，您只需使用或多或少的 555… .如果由于某种原因您无法更改数组的类型，您仍然可以像访问其他类型一样访问它，请参阅 how to cast an int array to a byte array in C.
我的嵌入式系统有 128KB 内存阵列结构用于特定用途
每2bit代表4个state(state 0,state 1,state 2,state 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 : 我用的是LEON3 Sparc V8 32bit处理器，用的是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Ж
最后，当且仅当状态为 0b11.
& 获得 1 位
(l >>> 1) & r = 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0? 0?
这里 ? 如果相应的状态是 0b11 则 1 否则 0 否则。
通过简化公式 (s >>> 1) & s & 0x55555555.
位计数
要计算 s 中的 0b11 个状态，我们只需计算 1 中的位
(s >>> 1) & s & 0x55555555.
如书中所述，无需循环即可进行位计数 Hacker's Delight, chapter 5 or in this Whosebug answer。
此处显示的方法仅适用于单个数组元素。要计算整个数组中的状态，请循环遍历其元素。
优化
正如 Lundin 在评论中指出的那样，如果您的处理器无法将 uint32_t 放入其寄存器，则操作 (s >>> 1) 可能会很昂贵。在这种情况下，将数组 states[] 声明为不是 uint32_t 是明智的，但无论哪种方式在您的处理器上最有效——过程保持不变，您只需使用或多或少的 555… .如果由于某种原因您无法更改数组的类型，您仍然可以像访问其他类型一样访问它，请参阅 how to cast an int array to a byte array in C.