Что такое операторы побитового сдвига (bit-shift) и как они работают?
https://stackoverflow.com/questions/141525
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытался изучать C в свободное время, и другие языки (C #, Java и т.д.) Имеют ту же концепцию (и часто те же операторы)...
Что мне интересно, так это то, что на базовом уровне означает сдвиг битов (<<, >>, >>>) знаете, какие проблемы это может помочь решить, и какие подводные камни скрываются за поворотом?Другими словами, абсолютное руководство для начинающих по смене бит во всех его достоинствах.
Решение
Операторы сдвига битов делают именно то, что подразумевает их название.Они меняют местами биты.Вот краткое (или не очень краткое) введение в различные операторы сдвига.
Операторы
>>является арифметическим (или знаковым) оператором сдвига вправо.>>>является логическим (или беззнаковым) оператором сдвига вправо.<<является оператором сдвига влево и отвечает потребностям как логического, так и арифметического сдвига.
Все эти операторы могут быть применены к целочисленным значениям (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.
Другие советы
Допустим, у нас есть один байт:
0110110
Применяя один сдвиг влево, мы получаем:
1101100
Крайний левый ноль был сдвинут из байта, и новый ноль был добавлен к правому концу байта.
Биты не переворачиваются;они отбрасываются.Это означает, что если вы сдвинете влево 1101100, а затем вправо, вы не получите тот же результат обратно.
Сдвиг влево на N эквивалентен умножению на 2N.
Сдвиг вправо на N равен (если вы используете дополнение к своим) эквивалентно делению на 2N и округление до нуля.
Сдвиг в битах можно использовать для безумно быстрого умножения и деления при условии, что вы работаете со степенью 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
Теперь мы получаем то же смещение, что и раньше, за исключением того, что вместо дорогостоящей операции умножения мы используем два 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-битного multiply.На процессорах 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 инструкция.РУКА еще более мощная:один операнд любой команды может быть сдвинут влево или вправо бесплатно.Таким образом, масштабирование с помощью константы времени компиляции, которая, как известно, равна степени 2, может быть даже более эффективным, чем умножение.
Ладно, вернемся в наши дни...чем-то более полезным сейчас было бы использовать битовый сдвиг для хранения двух 8-битных значений в 16-битном целом числе.Например, в C#:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
В C ++ компиляторы должны сделать это за вас, если вы использовали struct с двумя 8-битными элементами, но на практике это происходит не всегда.
Побитовые операции, включая битовый сдвиг, являются фундаментальными для низкоуровневого аппаратного обеспечения или встроенного программирования.Если вы прочитаете спецификацию устройства или даже некоторые форматы двоичных файлов, вы увидите байты, слова и dwords, разбитые на битовые поля, выровненные по небайтам, которые содержат различные представляющие интерес значения.Доступ к этим битовым полям для чтения / записи является наиболее распространенным способом использования.
Простым реальным примером в графическом программировании является то, что 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,....
Одна из проблем заключается в том, что следующее зависит от реализации (в соответствии со стандартом ANSI):
char x = -1;
x >> 1;
x теперь может быть 127 (01111111) или по-прежнему -1 (11111111).
На практике обычно бывает последнее.
Я пишу только советы и рекомендации, которые могут оказаться полезными при сдаче тестов / экзаменов.
n = n*2:n = n<<1n = n/2:n = n>>1- Проверка, является ли n степенью 2 (1,2,4,8, ...):проверить
!(n & (n-1)) - Получение xче немного из
n:n |= (1 << x) - Проверка, является ли x четным или нечетным:
x&1 == 0(четный) - Переключить nче бит x:
x ^ (1<<n)
Обратите внимание, что в реализации Java количество сдвигаемых битов изменяется в зависимости от размера исходного кода.
Например:
(long) 4 >> 65
равно 2.Вы могли бы ожидать, что сдвиг битов вправо 65 раз сведет все к нулю, но на самом деле это эквивалентно:
(long) 4 >> (65 % 64)
Это верно для <<, >>, и >>>.Я не пробовал это на других языках.
Некоторые полезные битовые операции / Манипуляции в Python.Реализовал ответы @Ravi Prakash на python.
# basic bit operations
# int to bin
print(bin(10))
# bin to int
print(int('1010',2))
# multiplying x with 2 .... x**2== x << 1
print(200<<1)
# dividing x with 2 .... x /2 == x >> 1
print(200>>1)
# modulo x with 2 .... x%2 == x&1
if 20&1==0:
print("20 is a even number")
# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))
# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0
# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))
Имейте в виду, что на платформе Windows доступна только 32-разрядная версия PHP.
Тогда, если вы, например, сдвинетесь << или >> больше, чем на 31 бит, результаты могут быть неожиданными.Обычно возвращается исходное число вместо нулей, и это может быть действительно сложной ошибкой.
Конечно, если вы используете 64-разрядную версию PHP (unix), вам следует избегать сдвига более чем на 63 бита.Однако, например, MySQL использует 64-разрядный BIGINT, поэтому проблем с совместимостью возникнуть не должно.
Обновить:Начиная с PHP7 Windows, сборки php наконец-то могут использовать полные 64-битные целые числа:Размер целого числа зависит от платформы, хотя максимальное значение около двух миллиардов является обычным значением (это 32 бита со знаком).64-разрядные платформы обычно имеют максимальное значение около 9E18, за исключением Windows до PHP 7, где оно всегда было 32-разрядным.
