Обмен битами в заданной точке между двумя байтами

Question

Допустим, у меня есть эти два числа:

x = 0xB7
y = 0xD9

Их двоичные представления:

x = 1011 0111
y = 1101 1001

Теперь я хочу пересечь (GA) в данной точке, скажем, с позиции4. и далее.

Ожидаемый результат должен быть:

x = 1011 1001
y = 1101 0111

Поразрядно, как мне этого добиться?

Answer 1

Я бы просто использовал побитовые операторы:

t = (x & 0x0f)
x = (x & 0xf0) | (y & 0x0f)
y = (y & 0xf0) | t

Это подойдет для этого конкретного случая. Чтобы сделать его более адаптируемым, я бы добавил его в функцию, например:

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)

Значения поиска позволяют указать, какие биты следует поменять местами. Давайте возьмем значения xxxxxxxx для x и yyyyyyyy для y вместе с начальным битом s в 2 и конечным битом e в 6 (в этом сценарии номера битов начинаются с нуля слева).

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)

Answer 2

Если битовая позиция одинакова в обоих значениях, никаких изменений не требуется.Если все наоборот, они оба должны инвертировать.

XOR с 1 сальто;XOR с 0 - это неоперация.

Итак, нам нужно значение, которое имеет 1 везде, где есть разница между входами, и 0 везде.Это именно то, что делает a XOR b.

Просто замаскируйте эту битовую разницу, чтобы сохранить только различия в битах, которые мы хотим поменять , и у нас есть бит-своп в 3 XOR +1 AND.

Ваша маска (1UL << position) -1.Один меньше степени 2 имеет все биты ниже этого набора.Или, в более общем случае, с верхней и нижней позицией для вашего битового диапазона: (1UL << highpos) - (1UL << lowpos).Быстрее ли таблица поиска быстрее, чем бит-набор / подпрограмма, зависит от компилятора и аппаратного обеспечения.(См. Ответ @ 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;
}

( Проводник компилятора Godbolt с gcc для x86-64 и ARM )

Это не обмен xor .Он использует временное хранилище.Как показывает ответ @ chux на вопрос, почти повторяющийся, подкачка xor в маске требует 3 операций AND, а также 3 XOR.(И исключает единственное преимущество XOR-swap, требуя временный регистр или другое хранилище для результатов &.) Этот ответ является модифицированной копией моего ответа на этот другой вопрос.

Эта версия требует только1 И.Кроме того, два последних XOR не зависят друг от друга, поэтому общая задержка от входов до обоих выходов составляет всего 3 операции.(Обычно 3 цикла).

---

Пример этого в x86 asm см. В этом code-golf Обмен капитализации двух строк в 14 байтах машинного кода x86-64 (спрокомментированный источник asm)

Answer 3

Замена отдельных битов с помощью 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));