Вопрос: Что такое операторы бит-сдвига (бит-сдвиг) и как они работают?


Я пытаюсь изучить C в свое свободное время, а другие языки (C #, Java и т. Д.) Имеют одну и ту же концепцию (и часто одни и те же операторы) ...

Мне интересно, на каком-то основном уровне, что делает бит-сдвиг (<<, >>, >>>), какие проблемы он может решить, а что замаскирует вокруг изгиба? Другими словами, руководство абсолютного новичка по смещению бит во всей его доброте.


1175


источник


Ответы:


Операторы сдвига битов делают именно то, что подразумевает их название. Они сдвигают биты. Вот краткое (или не столь краткое) введение в различные операторы сдвига.

Операторы

  • >>является арифметическим (или подписанным) оператором сдвига вправо.
  • >>>является логическим (или беззнаковым) оператором сдвига вправо.
  • <<является оператором сдвига влево и отвечает потребностям как логических, так и арифметических сдвигов.

Все эти операторы могут применяться к целочисленным значениям ( int, long, возможно shortа также byteили char). На некоторых языках применение операторов сдвига к любому типу данных меньше, чем intавтоматически изменяет размер операнда int,

Обратите внимание, что <<<не является оператором, поскольку он будет избыточным. Также обратите внимание, что C и C ++ не различают операторы правого сдвига. Они обеспечивают только >>оператор, а поведение с правосторонним сдвигом - это реализация, определенная для подписанных типов.


Левый сдвиг (<<)

Целые числа хранятся в памяти как серия бит. Например, номер 6, хранящийся как 32-разрядный intбыло бы:

00000000 00000000 00000000 00000110

Сдвиг этого битового рисунка влево на одну позицию ( 6 << 1) приведет к числу 12:

00000000 00000000 00000000 00001100

Как вы можете видеть, цифры сдвинулись влево на одну позицию, а последняя цифра справа заполнена нулем. Вы также можете заметить, что смещение влево эквивалентно умножению на степени 2. Таким образом 6 << 1эквивалентно 6 * 2, а также 6 << 3эквивалентно 6 * 8, Хороший оптимизирующий компилятор, если возможно, заменит умножения на сдвиги.

Не круговое смещение

Обратите внимание, что это не круговые сдвиги. Перемещение этого значения влево на одну позицию ( 3,758,096,384 << 1):

11100000 00000000 00000000 00000000

приводит к 3,221,225,472:

11000000 00000000 00000000 00000000

Утерянная цифра «с конца» теряется. Он не обертывается.


Логический сдвиг вправо (>>>)

Логический сдвиг вправо - это обратный сдвиг влево. Вместо того, чтобы перемещать биты влево, они просто перемещаются вправо. Например, смещение числа 12:

00000000 00000000 00000000 00001100

справа на одну позицию ( 12 >>> 1) вернет наш оригинал 6:

00000000 00000000 00000000 00000110

Итак, мы видим, что смещение вправо эквивалентно делению степенями 2.

Потерянные бит пропали

Однако сдвиг не может вернуть «потерянные» биты. Например, если мы изменим этот шаблон:

00111000 00000000 00000000 00000110

налево 4 позиции ( 939,524,102 << 4), получаем 2,147,483,744:

10000000 00000000 00000000 01100000

и затем смещение назад ( (939,524,102 << 4) >>> 4) получаем 134 217 734:

00001000 00000000 00000000 00000110

Мы не можем вернуть свое первоначальное значение после того, как мы потеряли бит.


Арифметический сдвиг вправо (>>)

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

Например, если мы интерпретируем этот битовый шаблон как отрицательное число:

10000000 00000000 00000000 01100000

мы имеем число -2,147,483,552. Смещение этого вправо на 4 позиции с арифметическим сдвигом (-2,147,483,552 >> 4) даст нам:

11111000 00000000 00000000 00000110

или номер -134,217,722.

Итак, мы видим, что мы сохранили знак отрицательных чисел, используя арифметический сдвиг вправо, а не логический сдвиг вправо. И снова мы видим, что мы выполняем разделение по степеням 2.


1487



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

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-битными членами, но на практике это не всегда.


168



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

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

82



Бит-маскирование и смена

Бит-сдвиг часто используется при низкоуровневом графическом программировании. Например, заданное значение цвета пикселя, закодированное в 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, ...,


37



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

char x = -1;
x >> 1;

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

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


26



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.


8



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 xth bit of n: n |= (1 << x)
  5. Checking if x is even or odd: x&1 == 0 (even)
  6. Toggle the nth bit of x: x ^ (1<<n)

6



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.


-1