如何使用按位运算来根据其他两个字节分配一个字节的特定比特？(根据蒙版进行比特混合) [英] How to use bitwise operations to assign specific bits of a byte according to two other bytes? (bit blend according to a mask)

问题描述

我有%3个字节。

• 一个字节决定第三个字节的哪些位需要更改(1表示位需要更改，0表示不应该更改)。
• 第二个字节确定更改的位是被分配1还是0。
• 第3个字节是发生更改的位置。

有没有办法可以使用按位运算符来实现这一点？如果是这样的话，是如何做到的呢？一个简单的公式或程序来实现这一点是很好的(最好是用c语言)。

示例：

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

ExpectedResult: 0b11010010

推荐答案

这方面的标准Bithack是"；Merge bits from two values according to a mask"；-我将输入的变量名称添加到肖恩·安德森的Bithack集合中的现有注释中。

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's answer)。清除未选择的位，然后在新值中执行OR操作以设置应设置的任何位。

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

---

效率：

r = a ^ ((a ^ b) & mask);只有3个布尔运算，
对于(a & ~mask) | (b & mask)，如果所有三个输入都是运行时变量，则为4。(一个按位NOT，两个AND，加上一个OR)。

如果mask是一个常量，则向~mask的常量传播使其成为常量，并且大多数机器可以使用至少8位AND掩码立即执行AND运算。因此，您仍然只需要3条指令：两个AND(具有反常数)和一个OR。

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

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

如果关键路径经过mask(即没有提前准备好)，并且没有andn和&这样的指令作为一次操作，则从mask到result的延迟是3个操作，~、&和|。(假设b & mask可以并行运行，而不会减慢这三个进程中的任何一个)。

现代Ooo执行计算机上(a & ~mask) | (b & mask)的延迟。
(Not the same thing as throughput cost)

• a->；结果：2个周期
• b->；结果：2个周期
• 掩码->；结果：3个周期(在某些计算机上为2个周期)

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

现代Ooo执行计算机上a ^ ((a ^ b) & mask)的延迟。

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

相关问答：

• Merge bit sequences a and b according to a mask-这称为SIMD编程的混合体。IDK如果其他人使用比特混合这一术语，我喜欢将其用于此操作，但国际海事组织清楚地描述了这一点。X86的AVX-512扩展具有3输入布尔运算vpternlog和来自8位立即数的真值表，因此可以在一条指令中完成。

• Swapping bits at a given point between two bytes-相同的Bithack思想，但将屏蔽的位差应用于两个输入以在屏蔽位置交换位。

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

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

这篇关于如何使用按位运算来根据其他两个字节分配一个字节的特定比特？(根据蒙版进行比特混合)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！