时间戳

首页 > 解决方案 > 如何使用按位运算根据另外两个字节分配一个字节的特定位？（根据掩码进行位混合）

c - 如何使用按位运算根据另外两个字节分配一个字节的特定位？（根据掩码进行位混合）

问题描述

我有 3 个字节。

有没有办法使用按位运算符来实现这一点？如果是这样，怎么做？一个简单的公式或程序来实现这一点会很好（最好在 c 中）。

例子：

BitsToAssign:   0b01101011
ValuesToAssign: 0b01000010
ByteToAlter:    0b11110001

ExpectedResult: 0b11010010

标签： cbit-manipulation

解决方案

对此的标准 bithack 是“根据掩码合并来自两个值的位”-我将输入的变量名称添加到 Sean Anderson 的 bithacks 集合中的现有注释中。

unsigned int a;    // (ByteToAlter)    value to merge in non-masked bits
unsigned int b;    // (ValuesToAssign) value to merge in masked bits
unsigned int mask; // (BitsToAssign)   1 where bits from b should be selected; 0 where from a.

unsigned int r;    // result of (a & ~mask) | (b & mask) goes here

r = a ^ ((a ^ b) & mask);

正如 bithack 评论指出的那样，直接的方法是(a & ~mask) | (b & mask)- 清除您没有保留在每个输入中的位，然后将它们组合在一起。

工作原理a ^ ((a ^ b) & mask)：

bitdiff = a^b是这些输入之间的位差。
它有1它们不同的地方，也有0它们相同的地方。（根据 XOR 的定义）。

a ^ bitdiff会翻转a与b. 事实上，b == a ^ bitdiff.
证明这是真的的一种方法是 XOR 是关联的，所以 a ^ (a^b)= (a ^ a) ^ b。
和x^x= 0，就像x-x = 0.
0 ^ x = x，所以(a^a) ^ b= 0 ^ b= b。

但是，如果我们将 bitdiff 屏蔽为仅从某些位置设置位a到位b，我们就实现了我们的目标：根据掩码进行按位混合。 blend = a ^ (bitdiff & mask);

(a & ~mask) | (b & mask)简单版的特殊情况

如果您的输入被安排成ValuesToAssign只有1在掩码选择的位置有任何位，您可以优化掉b & mask部分，只留下(a & ~mask) | b. （Eraklon 的回答）。清除未选择的位，然后在新值中进行 OR 以设置应设置的任何位。

另一个特殊情况是 when ValuesToAssign == BitsToAssign，即修改只设置位，从不清除它们。这就是 OR 所做的，因此这种情况当然会优化为a | b，而无需a在 ORing 之前清除位。

效率：

r = a ^ ((a ^ b) & mask);只有 3 个布尔运算，而如果所有三个输入都是运行时变量，
则为 4个。(a & ~mask) | (b & mask)（一个按位非，两个与，加上一个或）。

如果mask是一个常量，那么常量传播到~mask使其成为一个常量，并且大多数机器可以使用至少一个 8 位与掩码进行与立即数。所以你仍然只需要 3 条指令：两个 AND（带反常数）和一个 OR。

一些机器（比如带有 BMI1 的 x86）甚至有一条andn指令x & ~y，允许(a & ~mask) | (b & mask)使用 3 条指令来完成。

对于延迟，(a & ~mask) | (b & mask)具有更多的指令级并行性。如果mask和在和~mask之前准备好，则只有两个并行的 AND 操作和一个 OR，从和输入准备好到输出准备好。在普通的超标量机器上（可以在同一个周期中执行两个独立的 AND 操作），从输入到输出只有 2 个周期的延迟。（再次，假设已提前准备好，或者存在类似的指令可以在单个操作中执行）。ababmaskandna & ~mask

如果关键路径通过（即它没有提前准备好），并且mask您没有像andn做一个操作的指令，那么从to的延迟是 3 个操作，，和。（假设可以并行运行而不会减慢这三个中的任何一个）。~&maskresult~&|b & mask

(a & ~mask) | (b & mask)现代 OoO 执行机器上的延迟。
（与吞吐量成本不同）

  • a -> 结果：2 个周期
  • b -> 结果：2 个周期
  • 掩码 -> 结果：3 个周期（或在某些机器上为 2 个）

但是位差方式没有任何 ILP；这是一个由 3 个操作组成的链。 a^b要求这两个输入都为第一步做好准备，然后mask需要为这& mask一步做好准备。最后a ^ ...一步是使用之前已经需要的输入。所以它只有3个操作，但它们是串行的。

a ^ ((a ^ b) & mask)现代 OoO 执行机器上的延迟。

  • a -> 结果：3 个周期
  • b -> 结果：3 个周期
  • 掩码 -> 结果：2 个周期

相关问答：

  • 根据掩码合并位序列 a 和 b - 这在 SIMD 编程中称为混合。IDK 如果其他人使用我喜欢用于此操作的“位混合”术语，但 IMO 清楚地描述了它。x86 的 AVX-512 扩展具有 3 输入布尔运算vpternlog，带有来自 8 位立即数的真值表，因此可以在单个指令中完成。

  • 在两个字节之间的给定点交换位- 相同的 bithack 想法，但将掩码位差应用于两个输入以在掩码位置交换位。

  • https://catonmat.net/low-level-bit-hacks - 从对运算符的介绍开始（如^按位异或）。包括使用 + 和 - 的 bithacks（以及命中 1 或 0 的进位传播效果，例如x & (x-1)清除最右边的设置位。）

  • https://agner.org/optimize/了解更多关于现代 CPU 调优的信息。

推荐阅读