Обмен пары битов в байте

Question

У меня есть произвольное 8-битное двоичное число, например, 11101101

Я должен поменять все пары битов, как:

Перед заменой: 11-10-11-01 После замены: 11-01-11-10

Меня спросили об этом в интервью!

Answer 1

В псевдокоде:

x = ((x & 0b10101010) >> 1) | ((x & 0b01010101) << 1)

Он работает, обрабатывая младшие и старшие биты каждой битовой пары отдельно, а затем объединяя результат:

• Выражение x & 0b10101010 извлекает старший бит из каждой пары, а затем >> 1 переводит его в позицию младшего бита.
• Аналогично, выражение (x & 0b01010101) << 1 извлекает младший бит из каждой пары и переводит его в верхнюю битовую позицию.
• Затем две части объединяются с использованием побитового ИЛИ.

Поскольку не все языки позволяют писать двоичные литералы напрямую, вы можете написать их, например, в шестнадцатеричном формате:

Binary        Hexadecimal  Decimal 
0b10101010    0xaa         170
0b01010101    0x55         85

Answer 2

1. Создайте две битовые маски, одну из которых содержит все четные биты, а другую - неравные биты (10101010 и 01010101).
2. Используйте поразрядно-и, чтобы отфильтровать входные данные в два числа, одно из которых обнуляет все четные биты, а другое обнуляет все неравные биты.
3. Сдвиг числа, содержащего только четные биты, на один бит влево, а другого - на один бит вправо
4. Используйте побитовые или объединить их вместе.

Пример для 16 бит (не фактический код):

short swap_bit_pair(short i) {
    return ((i & 0101010110101010b) >> 1) | ((i & 0x0101010101010101b) << 1));
}

Answer 3

Предположим, ваш номер num.

Сначала найдите бит четной позиции:
num & oxAAAAAAAA

Второй шаг - найти бит нечетной позиции:
num & ox55555555

3-й шаг изменения положения нечетной позиции на бит четной позиции и четного положения на бит нечетной позиции:
Even = (num & oxAAAAAAAA)>>1
Odd = (num & 0x55555555)<<1

Последний шаг ... result = Even | Odd

Результат печати

Answer 4

Наиболее элегантное и гибкое решение состоит в том, чтобы, как уже говорили другие, применять маску «расчески» по отдельности к четным и нечетным битам, а затем смещать их влево и вправо соответственно на одно место, чтобы объединять их, используя поразрядно или.

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

const unsigned char lookup[] = { 0x02, 0x01, 0x03, 0x08, 0x0A, 0x09, 0x0B ...

Каждое значение помещается в массив для представления преобразования индекса.Поэтому, если вы затем сделаете это:

unsigned char out = lookup[ 0xAA ];

out будет содержать 0x55

Это более громоздко и менее гибко, чем первый подход (что если вы хотите перейти от 8биты до 16?), но есть подход, который будет заметно быстрее, если выполнять большое количество этих операций.

Answer 5

Сначала я закодировал бы его как «от руки», то есть в несколько очевидных, явных этапов, и использовал бы его для проверки правильности работы модульных тестов, которые у меня были на месте, а затем переходил только к более эзотерическим решениям по обработке битов.если у меня была потребность в производительности (и эта дополнительная производительность была достигнута за счет указанных улучшений)

Код для людей, во-первых, компьютеры, затем.

Answer 6

b = (a & 170 >> 1) | (a & 85 << 1)