Битовые операции II: изменение порядка бит

Часть I

Циклический сдвиг

Циклический сдвиг бит представляет собой операцию, напоминающую прокручивание содержимого бит-строки на месте: при сдвиге влево биты, «выпадающие» с левого конца, вставляются с правого конца (сохраняя исходный относительный порядок следования), при сдвиге вправо, наоборот, биты, «выпадающие» с правого конца, вставляются с левого.

Реализовать циклический сдвиг на заданное число бит достаточно просто. Например, сдвиг влево:

inline uint32_t rotate_left(uint32_t word, unsigned bits)
{
  return (word << bits) | (word >> (32 - bits));
}

Замечание. Если bits больше 31, то результат может быть различным (зависит от компилятора и процессора). При необходимости корректно обрабатывать случай bits > 31 на любом процессоре следует в качестве bits использовать остаток от деления bits на 32 (применить маску: bits &= 31).

Ассемблерные аналоги x86: ROL, ROR.

Поменять местами половинки слова

Частный случай циклического сдвига: сдвинуть циклически (хоть влево, хоть вправо) на половину разрядности.

inline uint32_t swap_halves(uint32_t word)
{
  return (word << 16) | (word >> 16);
}

Обратить порядок байт

Необходимость обращения порядка байт иногда возникает из-за требования передачи двоичных данных между компьютерами с разными архитектурами. Современные процессоры имеют встроенные команды для быстрого обращения порядка байт (x86) и/или способны работать в разных режимах и быстро переключаться между ними (PowerPC, ARM). Но если требуется реализовать процессорно-независимую функцию, то это можно сделать, например так (метод «в лоб», эффективен на конвейерных процессорах с большим набором регистров):

inline uint32_t swap_bytes(uint32_t word)
{
  return ((word & 0x0000'00FF) << 24)
       | ((word & 0x0000'FF00) << 8)
       | ((word & 0x00FF'0000) >> 8)
       | ((word & 0xFF00'0000) >> 24);
}

Более сложный для понимания способ (см. также следующие примеры с обращением порядка бит) использует меньше операций:

inline uint32_t swap_bytes(uint32_t word)
{
  word = ((word & 0x00FF'00FF) << 8)
       | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

Ассемблерные аналоги x86: BSWAP.

Обратить порядок тетрад

Способ, применённый для обращения порядка байт, можно расширить для обращения порядка тетрад (половинок байт). Нужно поменять местами соседние тетрады и обратить порядок байт.

inline uint32_t swap_nibbles(uint32_t word)
{
  return swap_bytes(
    ((word & 0x0F0F'0F0F) << 4)
  | ((word >> 4) & 0x0F0F'0F0F);
}

Обратить порядок бит

Итак, если мы уже умеем обращать порядок тетрад, то обратить порядок бит можно, обратив его в каждой тетраде, а затем обратив порядок тетрад. Для этого поменяем местами соседние биты, затем пары соседних бит аналогично тому, как поменяли местами соседние тетрады в предыдущем примере.

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word << 1)  & 0xAAAA'AAAA)
       | ((word >> 1)  & 0x5555'5555);
  word = ((word << 2)  & 0xCCCC'CCCC)
       | ((word >> 2)  & 0x3333'3333);
  return swap_nibbles(word);
}

Впрочем, если базовый swap_bytes реализован стандартными операциями, а не с помощью специальной команды процессора, то лучше не использовать его, а просто распространить применённый метод «наверх» вплоть до половинок 32-битного слова.

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word << 1) & 0xAAAA'AAAA)
       | ((word >> 1) & 0x5555'5555);
  word = ((word << 2) & 0xCCCC'CCCC)
       | ((word >> 2) & 0x3333'3333);
  word = ((word << 4) & 0xF0F0'F0F0)
       | ((word >> 4) & 0x0F0F'0F0F);
  word = ((word << 8) & 0xFF00'FF00)
       | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

Или так (занести маски):

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word & 0x5555'5555) << 1)
       | ((word >> 1) & 0x5555'5555);
  word = ((word & 0x3333'3333) << 2)
       | ((word >> 2) & 0x3333'3333);
  word = ((word & 0x0F0F'0F0F) << 4)
       | ((word >> 4) & 0x0F0F'0F0F);
  word = ((word & 0x00FF'00FF) << 8)
       | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

Для расширения указанного метода на 64-битные слова надо будет добавить ещё одну строчку (уже для обмена 32-битных половин) и так далее при каждом удвоении разрядности.

Некоторые процессоры (например, семейства ARMv8) предоставляют встроенную команду для обращения порядка бит.

См. также: 0, 1, 2 и 3.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: