Вопрос: Что такое операторы бит-сдвига (бит-сдвиг) и как они работают?
Я пытаюсь изучить C в свое свободное время, а другие языки (C #, Java и т. Д.) Имеют одну и ту же концепцию (и часто одни и те же операторы) ...
Мне интересно, на каком-то основном уровне, что делает бит-сдвиг (<<, >>, >>>), какие проблемы он может решить, а что замаскирует вокруг изгиба? Другими словами, руководство абсолютного новичка по смещению бит во всей его доброте.
1175
2017-09-26 19:47
источник
Ответы:
Операторы сдвига битов делают именно то, что подразумевает их название. Они сдвигают биты. Вот краткое (или не столь краткое) введение в различные операторы сдвига.
Операторы
>>
является арифметическим (или подписанным) оператором сдвига вправо. >>>
является логическим (или беззнаковым) оператором сдвига вправо. <<
является оператором сдвига влево и отвечает потребностям как логических, так и арифметических сдвигов.
Все эти операторы могут применяться к целочисленным значениям ( 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
2017-09-26 20:46
Допустим, у нас есть один байт:
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
2017-09-26 19:55
Побитовые операции, включая сдвиг бит, являются фундаментальными для низкоуровневого оборудования или встроенного программирования. Если вы прочитали спецификацию для устройства или даже некоторые форматы двоичных файлов, вы увидите байты, слова и слова, разбитые на не-байт-выровненные битовые поля, которые содержат различные значения, представляющие интерес. Доступ к этим битовым полям для чтения / записи является наиболее распространенным использованием.
Простым реальным примером в графическом программировании является то, что 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
2017-09-26 22:22
Бит-маскирование и смена
Бит-сдвиг часто используется при низкоуровневом графическом программировании. Например, заданное значение цвета пикселя, закодированное в 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
2018-03-31 10:49
Одна из них заключается в следующем: зависимость зависит от реализации (согласно стандарту ANSI):
char x = -1;
x >> 1;
x теперь может быть 127 (01111111) или еще -1 (11111111).
На практике это обычно последнее.
26
2017-09-26 20:07
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
2017-08-28 13:16
I am writing tips and tricks only, may find useful in tests/exams.
n = n*2
: n = n<<1
n = n/2
: n = n>>1
- Checking if n is power of 2 (1,2,4,8,...): check
!(n & (n-1))
- Getting xth bit of
n
: n |= (1 << x)
- Checking if x is even or odd:
x&1 == 0
(even)
- Toggle the nth bit of x:
x ^ (1<<n)
6
2017-10-11 22:43
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
2017-10-23 14:28