Допустим, у нас есть один байт:

0110110

применение одного левого битового сдвига дает нам:

1101100

самый левый ноль был смещен из байта, и новый ноль был добавлен к правому концу байта.

биты не опрокидываются; они отбрасываются. Это означает, что если вы сдвинете влево 1101100, а затем вправо, вы не получите тот же результат обратно.

сдвиг влево на N равносильно умножению на 2^N.

сдвиг вправо на N (если вы используете одни дополняют) является эквивалентом деления на 2^N и округление до нуля.

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

например, еще в старые времена мы использовали режим 13h (320x200 256 цветов) для игр. В Режим 13h, видеопамять была выложена последовательно на пиксель. Это означало, что для вычисления местоположения пикселя вы должны использовать следующую математику:

memoryOffset = (row * 320) + column

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

однако 320 не является силой двух, поэтому, чтобы обойти это, мы должны выяснить, что такое сила двух, которая вместе составляет 320:

(row * 320) = (row * 256) + (row * 64)

теперь мы можем преобразовать его в левый сдвиги:

(row * 320) = (row << 8) + (row << 6)

для окончательного результата:

memoryOffset = ((row << 8) + (row << 6)) + column

теперь мы получаем то же смещение, что и раньше, за исключением того, что вместо дорогостоящей операции умножения мы используем два bitshifts...in 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, может быть даже более эффективным, чем умножение.

---

ОК, вернемся в наши дни... что-то более полезное сейчас было бы использовать bitshifting для хранения двух 8-битных значений в 16-битном целочисленном значении. Например, в C#:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

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

побитовые операции, включая сдвиг битов, являются фундаментальными для низкоуровневого оборудования или встроенного программирования. Если Вы читаете спецификации на устройства или даже некоторые двоичные форматы файлов, вы увидите, байты, слова, и слова, разбить на номера-байтовых полей соответствие, которые содержат различные значения интереса. Доступ к этим битовым полям для чтения / записи является наиболее распространенным использованием.

простой реальный пример в графическом программировании заключается в том, что 16-битный пиксель представлен как следует:

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

чтобы получить зеленое значение, вы должны сделать это:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

объяснение

чтобы получить значение только зеленого цвета, которое начинается со смещения 5 и заканчивается на 10 (т. е. длиной 6 бит), вам нужно использовать маску (БИТ), которая при применении ко всему 16-битному пикселю даст только те биты, которые нас интересуют.

#define GREEN_MASK  0x7E0

соответствующая маска-0x7E0, которая в двоичном формате-0000011111100000 (что в 2016 году десятичное число.)

uint16_t green = (pixel & GREEN_MASK) ...;

чтобы применить маску, вы используете оператор AND (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

после применения маски вы получите 16-битное число, которое на самом деле является всего лишь 11-битным числом, поскольку его MSB находится в 11-м бит. Зеленый цвет на самом деле имеет длину всего 6 бит, поэтому нам нужно уменьшить его с помощью правого сдвига (11-6 = 5), поэтому использование 5 в качестве смещения (#define GREEN_OFFSET 5).

также общим является использование битовых сдвигов для быстрого умножения и деления по степеням 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

Битовое Маскирование & Перекладывание

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

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

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

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

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

наши маски:

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

логическое & оператор гарантирует, что сохраняются только значения, где маска равна 1. Последнее, что нам сейчас нужно сделать, это получить правильное целочисленное значение, сдвигая все биты вправо на 16 мест (логический сдвиг вправо).

 green_value = masked_color >>> 16

и вуаля, у нас есть целое число, представляющее количество зеленого цвета в цвете пикселов:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001 
 Pixels-Green Value in Decimal: 185

это часто используется для кодирования или декодирования графических форматов, таких как jpg,png,....

один gotcha заключается в том, что следующее зависит от реализации (в соответствии со стандартом ANSI):

char x = -1;
x >> 1;

x теперь может быть 127 (01111111) или все еще -1 (11111111).

на практике, это обычно последний.

обратите внимание, что в реализации Java количество битов для сдвига изменяется на размер источника.

например:

(long) 4 >> 65

равна 2. Вы можете ожидать, что смещение битов вправо в 65 раз обнулит все, но на самом деле это эквивалент:

(long) 4 >> (65 % 64)

Это верно для >, и >>>. Я не пробовал его на других языках.

Я пишу только советы и рекомендации, может оказаться полезным в тестах/экзаменах.

1. n = n*2:n = n<<1
2. n = n/2:n = n>>1
3. проверка, если n-мощность 2 (1,2,4,8,...): проверьте !(n & (n-1))
4. начало x^е немного n:n |= (1 << x)
5. проверка четности или нечетности x:x&1 == 0 (даже)
6. включить n^е бит x: x ^ (1<<n)

имейте в виду, что только 32-разрядная версия PHP доступна на платформе Windows.

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

конечно, если вы используете 64-битную версию PHP (unix), вы должны избегать сдвига более чем на 63 бита. Однако, например, MySQL использует 64-битный BIGINT, поэтому его не должно быть проблема совместимости.

обновление: из окон PHP7 PHP-сборки наконец-то могут использовать полные 64-битные целые числа: размер integer зависит от платформы, хотя максимальное значение около двух миллиардов привычное значение (это 32-битное знаковое). 64-разрядные платформы обычно имеют максимальное значение около 9E18, за исключением Windows до PHP 7, где он всегда был 32 бит.