Как этот код работает для обратного бита в числе?

Ответ 1

Предположим, что у меня есть рука из 8 карт:

7 8 9 10 J Q K A

Как мы можем отменить их? Один из способов - обмен соседними парами:

8 7 10 9 Q J A K

Затем замените смежные группы из 2: обмен 8 7 и 10 9 и т.д.:

10 9 8 7 A K Q J

Наконец, обмениваются группы из четырех, что вдвое меньше 8:

A K Q J 10 9 8 7

Готово.

Вы можете сделать это в разных заказах. Зачем? Потому что обмены стабильны относительно друг друга. Например, если мы обменяем верхнюю половину карточек с нижней половиной, пары остаются в том же порядке. Или, когда мы обмениваемся парами, половинки остаются в том же порядке.

Это то, что код выполняет с битовыми операциями. Например, для замены пар мы можем использовать маску 01010101 для выделения четных битов и 10101010 для выбора нечетных битов с использованием побитовой операции AND:

  ABCDEFGH     ABCDEFGH
& 01010101   & 10101010
----------   ----------
= 0B0D0F0H     A0C0E0G0

Помните, что правило для и задано для некоторого битового значения X, X и 1 = X и X и 0 = 0. 1 бит в маске сохраняет значение, а 0 бит в маске - 0. Это называется маскировкой, потому что он выглядит точно так же, как маска, используемая при распылении краски и т.д. 1 бит "накрывает" места, которые вы не хотите "красить" нулем.

Затем левый результат сдвигается влево на один бит, а правый результат сдвигается вправо. Это приводит к обмену:

  B0D0F0H0     0A0C0E0G

Окончательно, эти два сочетаются с логическим ИЛИ. Правило для OR состоит в том, что X или 0 является X. Каждая из двух частей имеет 0, где другая имеет ненулевое значение, поэтому бит просто объединяется:

  B0D0F0H0
| 0A0C0E0G
----------
= BADCFEHG

И теперь пары меняются местами.

Ответ 2

Это можно понять по индукции.

Начните с базового случая, двухбитового номера

input = (input & 0x1) <<  1 | (input & 0x2) >>  1;

Теперь переходим к четырехбитовому номеру

input = (input & 0x5) <<  1 | (input & 0xA) >>  1; // swap bits
input = (input & 0x3) <<  2 | (input & 0xc) >>  2; // swap bit pairs

Достижение 8-битного числа

input = (input & 0x55) <<  1 | (input & 0xAA) >>  1; // swap bits
input = (input & 0x33) <<  2 | (input & 0xCC) >>  2; // swap bit pairs
input = (input & 0x0F) <<  4 | (input & 0xF0) >>  4; // swap bit nibbles

и т.д.

Ответ 3

Сначала код свопирует отдельные соседние биты, затем смежные пары бит и т.д., каждый раз удваивая размер свопинга, пока в конце не обмениваются куски размером с половину целого числа. Перестановка выполняется путем маскировки битов, которые нужно перемещать с помощью AND, сдвигая их, а затем OR, чтобы результаты были вместе.

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

Ответ 4

Пусть b[0], b[1], b[2], ..., b[31] являются битами input, начиная с младшего значащего бита. Тогда b[1], b[0], b[3], b[2], ..., b[31], b[30] будут битами

input = (input & 0x55555555) <<  1 | (input & 0xAAAAAAAA) >>  1;

В основном, он меняет соседние биты input. Аналогично, другие 4 строки свопируют соседние пары, группы из 4, группы из 8 и, наконец, группы из 16 бит.

Ответ 5

unsigned reverse_bits(unsigned input)
{  
     //works on 32-bit machine  
     input = (input & 0x55555555) <<  1 | (input & 0xAAAAAAAA) >>  1;
     input = (input & 0x33333333) <<  2 | (input & 0xCCCCCCCC) >>  2;
     input = (input & 0x0F0F0F0F) <<  4 | (input & 0xF0F0F0F0) >>  4;
     input = (input & 0x00FF00FF) <<  8 | (input & 0xFF00FF00) >>  8;
     input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16;
     printf("\nvalue = %x",input);
     return input;
}

int _tmain()
{
    // TODO: Please replace the sample code below with your own.

    int value;
    signed int res,bit;
    signed int stPos, len;
    value = 0x12345678;

    reverse_bits(value);
    printf("\nvalue = %x",value);
    char buffer [33];
    itoa (value,buffer,2);
    printf ("\nbinary: %s\n",buffer);

    return 0;
}