bit-manipulation - 如何将单个掩码给出的一位值复制到一个字(('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

这是一个简短的代码，可以在实践中生成良好的无分支代码:

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 ¹ 和 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 个周期。然而，在最新的英特尔 CPU 上，速度很快。