如何复制（'transplant'）单个掩码给定的一位的值到一个字？

Question

复制一个位的值很简单，就是清零然后设置：

int copy(int from, int offset, int to) {
    int mask = 1 << 31-offset;
    return to & ~mask | from & mask;
}

然而，是否可以使用以下签名相当有效地执行此操作？

/* to - a word to set the bit on
 * mask - mask specifying the bit to set/clear and the value of that bit:
 *        - if mask contains exactly one set bit, set that bit on 'to';
 *        - if mask contains exactly one zero, clear that bit on 'to';   
 */
int copy_bit(int mask, int to);

这不是纯粹的学术（尤其不是家庭作业；）。我出于句法原因并将其实现为二元运算符。我想到了这个：

int copy_bit(int mask, int to) {
    int lowestZero = ~mask & (mask+1);
    //overflow 'clear' masks to zero highest bit; 0 for clear, ~0 for set.
    int switch = (mask | 0x80000000 | lowestZero) +1 >> 31;
    return to & (switch | mask) | (switch & mask);
}

然后我可以通过减少表达式来减少一些操作：

int switch = -(~mask & 0x7fffffff & ~mask-1) >> 31;

有没有更好的方法？

Answer 1

这是一个简短的代码，可以在实践中产生很好的 branch-free 代码：

int copy_bit(int mask, int to) {
  return (mask - 1 < 0) ? to & mask : to | mask;
}

这是assembly generated on gcc：

copy_bit(int, int):
 lea    edx,[rdi-0x1]
 mov    eax,edi
 or     edi,esi
 and    eax,esi
 test   edx,edx
 cmovg  eax,edi
 ret

所以只有6条指令（不包括ret），包括一条cmov^1条，15个字节的代码

将它与问题中显示的方法的程序集进行比较，后者需要 15 条指令（没有 cmov）和 36 字节的代码：

copy_bit_orig(int, int):
 lea    eax,[rdi+0x1]
 mov    edx,edi
 not    edx
 and    edx,eax
 mov    eax,edi
 or     eax,0x80000000
 or     edx,eax
 mov    eax,edi
 add    edx,0x1
 shr    edx,0x1f
 or     eax,edx
 and    edi,edx
 and    esi,eax
 mov    eax,esi
 or     eax,edi
 ret

请记住，您的解决方案涉及未定义的行为，因为操作 (mask + 1) 可能会溢出，这在 C 和 C++ 中未定义。我需要将强制转换添加到我的答案中，否则 gcc 会利用此行为将其编译为不符合您预期的代码。

¹ 我叫 cmov 因为在某些架构上它比简单的 ALU 指令慢，例如 2 个周期。然而，在最近的 Intel CPU 上它很快。

如何复制（'transplant'）单个掩码给定的一位的值到一个字？

How to copy ('transplant') the value of one bit given by a single mask to a word?

bit-manipulation

bitwise-operators