Практическое применение битового сдвига

Я полностью понимаю, как сдвигать биты. Я проработал множество примеров на бумаге и в коде, и мне здесь не нужна помощь.

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

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

  • Кажется, что компиляторы и процессоры могут произвести определенную оптимизацию при работе с любыми умножениями, равными n ^ 2, n ^ 4 и т. Д. Биты просто сдвигаются влево. (И наоборот, я полагаю, то же самое применимо к делению, n / 2, n / 4 и т. Д.)

  • В алгоритмах шифрования. Т.е. использовать серию битовых сдвигов, реверсов и комбинаций, чтобы что-то запутать.

Все ли эти примеры точны? Вы бы что-нибудь добавили? Я потратил довольно много времени на изучение того, как реализовать битовый сдвиг / переупорядочение / байтовую замену, и я хочу знать, как это можно применить на практике =)


c bit-shift bits
person Calvin Froedge    schedule 26.02.2012    source источник
comment
возможный дубликат Есть ли веские причины использовать сдвиг битов, кроме быстрых вычислений?   -  person James    schedule 26.02.2012
comment
Это тоже был полезный пост ... stackoverflow.com/questions/520625/   -  person Calvin Froedge    schedule 26.02.2012

Ответы (4)


arrow_upward
3
arrow_downward

Я бы не согласился, что самый важный пример - это порядок байтов, но он полезен. Ваши примеры верны.

Хеш-функции часто используют битовые сдвиги как способ добиться хаотического поведения; не отличается от ваших криптографических алгоритмов.

person Captain Giraffe    schedule 26.02.2012
comment
Так, например, случайная сортировка массива? - person Calvin Froedge; 26.02.2012
comment
@CalvinFroedge Если под случайным массивом вы имеете в виду массив, заполненный случайными числами, ванильная быстрая сортировка по-прежнему непобедима. - person Captain Giraffe; 26.02.2012

arrow_upward
2
arrow_downward

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

uint8_t bla = INIT_VALUE;

bla |= (1U << N);   // Set N-th bit
bla &= ~(1U << N);  // Clear N-th bit
person ouah    schedule 26.02.2012
comment
Зачем вам это нужно? - person Calvin Froedge; 26.02.2012
comment
Например, @CalvinFroedge во встроенном мире широко используется для чтения или записи определенных битов регистров ввода-вывода. - person ouah; 26.02.2012

arrow_upward
2
arrow_downward

  1. Быстрое умножение и деление на степень двойки - особенно важно во встроенных приложениях
  2. вычисление CRC - удобно для сетей, например Ethernet
  3. Математические вычисления, требующие очень больших чисел

Просто пара с моей головы

person Ed Heal    schedule 26.02.2012

arrow_upward
2
arrow_downward

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

Не очень широко используется, но в (некоторых) шахматных играх доска и ходы представлены 64-битными целочисленными значениями (называемыми битовыми досками), поэтому оценка допустимых ходов, выполнение ходов и т. Д. Выполняется с помощью побитовых операторов. В сети этому много объяснений, но это кажется довольно хорошим объяснением: http://www.frayn.net/beowulf/theory.html#bitboards.

И, наконец, в некоторых технических интервью вы можете обнаружить, что вам нужно подсчитать количество битов, установленных в int / long!

person Kevin    schedule 26.02.2012