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 回答