Допустим, у нас есть один байт:
0110110
Применение одного сдвига влево дает нам:
1101100
Крайний левый ноль был смещен из байта, и новый ноль был добавлен к правому концу байта.
Биты не переворачиваются; они отбрасываются. Это означает, что если вы переместитесь влево на 1101100, а затем вправо, вы не получите тот же результат обратно.
Сдвиг влево на N эквивалентен умножению на 2 N .
Сдвиг вправо на N (если вы используете их дополнение ) эквивалентен делению на 2 N и округлению до нуля.
Bitshifting можно использовать для безумно быстрого умножения и деления при условии, что вы работаете со степенью 2. Почти все низкоуровневые графические процедуры используют сдвиг битов.
Например, в давние времена мы использовали режим 13h (320х200 256 цветов) для игр. В режиме 13h видеопамять распределялась последовательно на пиксель. Это означает, что для расчета местоположения для пикселя вы должны использовать следующую математику:
memoryOffset = (row * 320) + column
Так вот, в те времена скорость была критической, поэтому мы будем использовать битовые сдвиги для этой операции.
Тем не менее, 320 не является степенью двойки, поэтому, чтобы обойти это, мы должны выяснить, что такое сила двойки, которая складывается вместе, составляет 320:
(row * 320) = (row * 256) + (row * 64)
Теперь мы можем преобразовать это в левые сдвиги:
(row * 320) = (row << 8) + (row << 6)
Для окончательного результата:
memoryOffset = ((row << 8) + (row << 6)) + column
Теперь мы получаем то же смещение, что и раньше, за исключением того, что вместо дорогостоящей операции умножения мы используем два битовых сдвига ... в x86 это будет примерно так (заметьте, это было всегда, так как я делал сборку (редактор примечание: исправил пару ошибок и добавил 32-битный пример)):
mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]
; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov
Итого: 28 циклов на любом древнем процессоре имели эти тайминги.
Vrs
mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6; 2
shl di, 8; 2
add di, ax; 2 (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]
12 циклов на том же древнем процессоре.
Да, мы бы усердно работали, чтобы сбить 16 циклов ЦП.
В 32- или 64-битном режиме обе версии становятся намного короче и быстрее. Современные исполнительные процессоры вне очереди, такие как Intel Skylake (см. http://agner.org/optimize/), имеют очень быстрое аппаратное умножение (низкая задержка и высокая пропускная способность), поэтому выигрыш намного меньше. Семейство AMD Bulldozer немного медленнее, особенно для 64-разрядное умножение. В процессорах Intel и AMD Ryzen два сдвига имеют немного меньшую задержку, но больше команд, чем умножение (что может привести к снижению пропускной способности):
imul edi, [row], 320 ; 3 cycle latency from [row] being ready
add edi, [column] ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.
против
mov edi, [row]
shl edi, 6 ; row*64. 1 cycle latency
lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency
add edi, [column] ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.
Компиляторы сделают это за вас: посмотрите, как gcc, clang и MSVC все используют shift + lea при оптимизации return 320*row + col;.
Самое интересное, что следует здесь отметить, это то, что x86 имеет инструкцию shift-and-add (LEA) , которая может делать небольшие сдвиги влево и добавлять одновременно, с производительностью, равной и add инструкция. ARM еще более мощен: один операнд любой инструкции может быть перемещен влево или вправо бесплатно. Таким образом, масштабирование по постоянной времени компиляции, известной как степень 2, может быть даже более эффективным, чем умножение.
Ладно, в наши дни ... что-то более полезное сейчас - использовать битовую сдвиг для хранения двух 8-битных значений в 16-битном целом числе. Например, в C #:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
В C ++ компиляторы должны сделать это за вас, если вы использовали struct с двумя 8-битными членами, но на практике это не всегда.