Как работает возврат битов в байте?

Question

Я новичок в программировании, и я нашел этот метод для обращения битов в байте в C:

//(10000011) -> (11000001)

unsigned char reverse(unsigned char b) {
   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
   return b;
}

опубликовано пользователем в ответ на этот вопрос, но я не могу понять, как это работает. Что означают эти константы?

Answer 1

Это может помочь посмотреть на двоичное представление вышеуказанных чисел:

0xF0: 11110000
0x0F: 00001111

0xCC: 11001100
0x33: 00110011

0xAA: 10101010
0x55: 01010101

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

Вторая пара маскирует и заменяет первые 2 бита и последние 2 бита из набора из 4 битов.

Третья пара маскирует и заменяет соседние пары битов.

Answer 2

Код сначала меняет местами "полубайты", то есть старшие 4 бита с младшими 4 битами. Затем он меняет две пары высшего порядка вместе и нижние пары вместе; наконец, он выполняет парные перестановки 2n и 2n+1 бит.

---

Я собираюсь обозначить биты первоначального значения b здесь по их показателю в угловых скобках (это просто псевдо-запись, которую я здесь использую, а не C); я использую o отмечать любой бит, который всегда равен 0. Итак, в начале мы имеем

<76543210>

Нет в первой операции у нас

• <76543210> & 0xF0 -> <7654oooo>
• <76543210> & 0x0F -> <oooo3210>

Теперь первое смещено вправо на 4 бита, а второе влево на 4, таким образом, мы получаем

• <7654oooo> >> 4 -> <oooo7654>
• <oooo3210> << 4 -> <3210oooo>

Наконец они объединяются, и, следовательно, после утверждения

b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;

значение b это перестановка <32107654> оригинальных битов.

Во втором утверждении маска 0xCC является 11001100 в двоичном виде, и 0x33 является 00110011 в двоичном формате; промежуточные значения:

• (<32107654> & 0xCC) >> 2 -> <32oo76oo> >> 2 -> <oo32oo76>; а также
• (<32107654> & 0x33) << 2 -> <oo10oo54> << 2 -> <10oo54oo>,

Эти 2 or'ed вместе приведут к перестановке <10325476>, Теперь, наконец, маска 0xAA является 10101010 в двоичном виде, и 0x55 является 01010101, Таким образом, мы имеем

• (<10325476> & 0xAA) >> 1 -> <1o3o5o7o> >> 1 -> <o1o3o5o7>; а также
• (<10325476> & 0x55) << 1 -> <o0o2o4o6> << 1 -> <0o2o4o6o>

Эти or'ed вместе приведут к перестановке <01234567> что является противоположностью оригинала.

Answer 3

Так что это просто немного сдвигается. Биты расположены в следующем порядке:

76543210

Теперь, первая строка, первая часть сохраняет старшие биты, устанавливает младшие биты в 0 (маска 0b11110000), сдвигает их на 4 вправо. Вторая часть делает то же самое для младших битов (маска 0b00001111) и смещается влево:

first line, first part:  7654xxxx => xxxx7654 (bits shift to the right)
first line, second part: xxxx3210 => 3210xxxx (bits shift to the left)
add them together:                => 32107654

Затем вторая строка. То же действие, разные маски (0b11001100 и 0b00110011 соответственно), с 32107654:

second line, first part:  32xx76xx => xx32xx76 (bits shift to the right)
second line, second part: xx10xx54 => 10xx54xx (bits shift to the left)
add them together:                 => 10325476

Третья строка совпадает с другими масками (0b10101010 и 0b01010101 соответственно), с 10325476:

third line, first part:  1x3x5x7x => x1x3x5x7 (bits shift to the right)
third line, second part: x0x2x4x6 => 0x2x4x6x (bits shift to the left)
add them together:                => 01234567

Итак, мы в конечном итоге, с действием:

76543210 => 01234567

Answer 4

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

1. & (AND) Bitwise Operator.
2. | (OR) Bitwise Operator.
3. >> (Right Shift Operator).
4. << (Left Shift Operator).

К счастью, я только что написал подробный блог, который объясняет все о системе счисления и манипулировании битами

Answer 5

Давайте нумеруем биты в b следующее:

01234567

0xF0 в двоичном есть 11110000, а также 0x0F является 00001111, Первое назначение сдвигает самые левые 4 бита вправо, а самые правые 4 бита влево, а затем объединяет их с ORИтак, результат:

45670123

0xCC является 11001100, а также 0x33 является 00110011, Когда эти маскированные биты сдвинуты на 2 бита и объединены, результатом является:

67452301

В заключение, 0xAA является 10101010 а также 0x55 является 01010101, Когда эти маски и смены сделаны, результат:

76543210

Вуаля! это обратный порядок.

Обратите внимание, что для каждой пары сдвигов битовые маски являются инверсиями друг друга, и количество сдвигаемых битов совпадает с длиной последовательностей в 1 бит в маске. Таким образом, каждый из них меняет группы битов, размер которых равен длине последовательности.