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

0110110

Применяя один левый битдвиг, мы получаем:

1101100

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

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

Сдвиг слева на N эквивалентен умножению на 2 ^N ,

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

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

Например, еще в прежние времена мы использовали режим 13h (320x200 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-битными членами, но на практике это не всегда.

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

Простым реальным примером в графическом программировании является то, что 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

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

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

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

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

char x = -1;
x >> 1;

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

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

Note that in the Java implementation, the number of bits to shift is mod'd by the size of the source.

For example:

(long) 4 >> 65

equals 2. You might expect shifting the bits to the right 65 times would zero everything out, but it's actually the equivalent of:

(long) 4 >> (65 % 64)

This is true for <<, >>, and >>>. I have not tried it out in other languages.

I am writing tips and tricks only, may find useful in tests/exams.

1. n = n*2: n = n<<1
2. n = n/2: n = n>>1
3. Checking if n is power of 2 (1,2,4,8,...): check !(n & (n-1))
4. Getting x^th bit of n: n |= (1 << x)
5. Checking if x is even or odd: x&1 == 0 (even)
6. Toggle the n^th bit of x: x ^ (1<<n)

Be aware of that only 32 bit version of PHP is available on the Windows platform.

Then if you for instance shift << or >> more than by 31 bits, results are unexpectable. Usually the original number instead of zeros will be returned, and it can be a really tricky bug.

Of course if you use 64 bit version of PHP (unix), you should avoid shifting by more than 63 bits. However, for instance, MySQL uses the 64-bit BIGINT, so there should not be any compatibility problems.

UPDATE: From PHP7 Windows, php builds are finally able to use full 64bit integers: The size of an integer is platform-dependent, although a maximum value of about two billion is the usual value (that's 32 bits signed). 64-bit platforms usually have a maximum value of about 9E18, except on Windows prior to PHP 7, where it was always 32 bit.