如何有效地替换一组连续的位

Question

假设我有一个二进制数 1001100，我想在 [2, 6).

部分用 1011 代替它

看起来像这样：

Binary: 1001100
Sub:    --1011-
Result: 1010110

我知道可以使用此代码多次重复设置一位：
number |= 1UL << n;

但我想知道是否有一种方法可以更有效地实现这一目标。

Answer 1

让我们考虑一个更一般的问题：你有一个二进制数 a，你想用另一个数 b[=40] 的位替换它的位=]，只有当第三个数m对应的位为1时。

针对您的具体问题：

a = 1001100 b = xx1011x m = 0011110

但是没有必要让m对应一个范围

计算结果 r 的伪代码是

for all i in 0 to 6 if m[i]=1 r[i]=a[i] else r[i]=b[i]

或等同于

for all i in 0 to 6 r[i] = (a[i] and (m[i]=1)) or (b[i] and (m[i]=0))

我们可以很容易地从中推断出循环是无用的，并且表达式

r = (a & m) | (b & ~m)

给出了正确的结果。

请注意，如果你想在特定范围内进行替换 k 到 l （例如在你的情况下为 1 到 5 ), 掩码将是 (2^l - 1) - (2^k - 1) = 2^l - 2^k

所以这是对应的C代码

unsigned int replace_bit(unsigned int a, unsigned int b, int k, int l){ unsigned int mask=(1<<l) - (1<<k) return (a & mask) | (b & ~mask) ; }

Answer 2

x86 架构上最有效的方法是使用 PDEP instruction，32 位的内在等价物是

PDEP: unsigned __int32 _pdep_u32(unsigned __int32 src, unsigned __int32 mask);

它的用法思路是

mov  ebx, 1001100b    ; initial value
mov  ecx, 0011110b    ; mask value (=SRC2) - bits to be replaced
mov  edx, 0001011b    ; bits to be inserted (=SRC1) at positions ECX
mov  eax, ecx         ; duplicate mask to EAX
not  eax              ; invert mask
and  ebx, eax         ; mask out bits that will be modified
pdep eax, edx, ecx    ; put bits from ECX to position specified by EDX into EAX
or   eax, ebx         ; merge masked initial value with result of PDEP
==>                   ; result is in EAX

这是 x86 汇编解决方案。
如有必要，将其转换为固有表示。
请记住 PDEP 在 AMD 处理器上有点慢。
此解决方案无需任何条件操作（如跳转）即可工作。

如何有效地替换一组连续的位

How to efficiently replace a contiguous set of bits

bit-manipulation

bitwise-operators