2

假设我有这两个数字：

x = 0xB7
y = 0xD9

它们的二进制表示是：

x = 1011 0111
y = 1101 1001

现在我想在给定点交叉（GA），比如从位置 4 开始。

预期的结果应该是：

x = 1011 1001
y = 1101 0111

按位，我怎样才能做到这一点？

4

3 回答 3

2

我只会使用按位运算符：

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 的结束位（在这种情况下，位编号从左侧的零开始）：xyyyyyyyyse

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)
于 2010-08-25T02:05:13.430 回答
1

如果两个值中的位位置相同，则两者都不需要更改。如果相反，它们都需要反转。

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 源代码）

于 2018-06-13T14:09:00.407 回答
0

用 XOR 交换单个位 

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));
于 2010-08-25T02:06:18.077 回答