假设我有这两个数字:
x = 0xB7
y = 0xD9
它们的二进制表示是:
x = 1011 0111
y = 1101 1001
现在我想在给定点交叉(GA),比如从位置 4 开始。
预期的结果应该是:
x = 1011 1001
y = 1101 0111
按位,我怎样才能做到这一点?
假设我有这两个数字:
x = 0xB7
y = 0xD9
它们的二进制表示是:
x = 1011 0111
y = 1101 1001
现在我想在给定点交叉(GA),比如从位置 4 开始。
预期的结果应该是:
x = 1011 1001
y = 1101 0111
按位,我怎样才能做到这一点?
我只会使用按位运算符:
t = (x & 0x0f)
x = (x & 0xf0) | (y & 0x0f)
y = (y & 0xf0) | t
这将适用于该特定情况。为了使其更具适应性,我将它放在一个函数中,例如(伪代码,with &
,|
并!
分别表示按位“and”,“or”和“not”):
def swapBits (x, y, s, e):
lookup = [255,127,63,31,15,7,3,1]
mask = lookup[s] & !lookup[e]
t = x & mask
x = (x & !mask) | (y & mask)
y = (y & !mask) | t
return (x,y)
查找值允许您指定要交换的位。让我们取y和y 的xxxxxxxx
值以及 2的起始位和 6 的结束位(在这种情况下,位编号从左侧的零开始):x
yyyyyyyy
s
e
x y s e t mask !mask execute
-------- -------- - - -------- -------- -------- -------
xxxxxxxx yyyyyyyy 2 6 starting point
00111111 mask = lookup[2](00111111)
00111100 & !lookup[6](11111100)
00xxxx00 t = x & mask
xx0000xx x = x & !mask(11000011)
xxyyyyxx | y & mask(00111100)
yy0000yy y = y & !mask(11000011)
yyxxxxyy | t(00xxxx00)
如果两个值中的位位置相同,则两者都不需要更改。如果相反,它们都需要反转。
XOR 与 1 翻转一点;与 0 的 XOR 是无操作的。
所以我们想要的是一个1
在输入之间存在位差的任何地方都有一个值,而在其他任何地方都有一个 0。这正是这样a XOR b
做的。
简单地屏蔽这个位差异,只保留我们想要交换的位的差异,我们在 3 XORs + 1 AND 中有一个位交换。
你的面具是(1UL << position) -1
。小于 2 的幂的 1 具有低于该集合的所有位。或者更一般地说,您的位范围有高低位置:(1UL << highpos) - (1UL << lowpos)
. 查找表是否比 bit-set / sub 更快取决于编译器和硬件。(请参阅@PaxDiablo 对 LUT 建议的回答)。
// Portable C:
//static inline
void swapBits_char(unsigned char *A, unsigned char *B)
{
const unsigned highpos = 4, lowpos=0; // function args if you like
const unsigned char mask = (1UL << highpos) - (1UL << lowpos);
unsigned char tmpA = *A, tmpB = *B; // read into locals in case A==B
unsigned char bitdiff = tmpA ^ tmpB;
bitdiff &= mask; // clear all but the selected bits
*A = tmpA ^ bitdiff; // flip bits that differed
*B = tmpB ^ bitdiff;
}
//static inline
void swapBit_uint(unsigned *A, unsigned *B, unsigned mask)
{
unsigned tmpA = *A, tmpB = *B;
unsigned bitdiff = tmpA ^ tmpB;
bitdiff &= mask; // clear all but the selected bits
*A = tmpA ^ bitdiff;
*B = tmpB ^ bitdiff;
}
(带有 gcc 的 Godbolt 编译器资源管理器,适用于 x86-64 和 ARM)
这不是 xor-swap。它确实使用临时存储。正如@chux对一个几乎重复的问题的回答所表明的那样,屏蔽的异或交换需要 3 次 AND 运算以及 3 次 XOR。(并且通过需要临时寄存器或其他存储&
结果来破坏 XOR-swap 的唯一好处。)这个答案是我对另一个问题的答案的修改副本。
这个版本只需要 1 AND。此外,最后两个 XOR 彼此独立,因此从输入到两个输出的总延迟仅为 3 次操作。(通常为 3 个周期)。
有关这方面的 x86 asm 示例,请参阅 this code-golf Exchange capitalization of two strings in 14 bytes of x86-64 machine code(带有注释的 asm 源代码)
unsigned int i, j; // positions of bit sequences to swap
unsigned int n; // number of consecutive bits in each sequence
unsigned int b; // bits to swap reside in b
unsigned int r; // bit-swapped result goes here
unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));