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

1382

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

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

Джон Руди
источник
2
Функциональные или нефункциональные случаи, в которых вы будете использовать сдвиг битов в 3GL, немногочисленны.
Трой Демонбрюн
16
После прочтения этих ответов вы можете посмотреть следующие ссылки: graphics.stanford.edu/~seander/bithacks.html & jjj.de/bitwizardry/bitwizardrypage.html
когти
1
Важно отметить, что переключение битов чрезвычайно просто и быстро для компьютеров. Находя способы использования сдвига битов в вашей программе, вы можете значительно сократить использование памяти и время выполнения.
Хойтман
@Hoytman: Но учтите, что хорошие компиляторы уже знают многие из этих трюков и, как правило, лучше понимают, где это имеет смысл.
Себастьян Мах

Ответы:

1713

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

Операторы

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

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

Обратите внимание, что <<<это не оператор, потому что он будет избыточным.

Также обратите внимание, что C и C ++ не различают операторы правого сдвига . Они предоставляют только >>оператор, и поведение смещения вправо является реализацией, определенной для подписанных типов. В остальной части ответа используются операторы C # / Java.

(Во всех основных реализациях C и C ++, включая GCC и Clang / LLVM, >>для подписанных типов это арифметика. В некотором коде это предполагается, но это не то, что гарантировано стандартом. Однако это не неопределенно ; стандарт требует, чтобы реализации определяли его одним так или иначе. Однако сдвиги влево отрицательных чисел со знаком - это неопределенное поведение (переполнение целых чисел со знаком). Поэтому, если вам не нужно арифметическое сдвиг вправо, обычно хорошей идеей является сдвиг битов беззнаковыми типами.)


Сдвиг влево (<<)

Целые числа хранятся в памяти как последовательность битов. Например, число 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.

Дерек Парк
источник
304
Ответ должен прояснить, что это специфический для Java ответ. В C / C ++ или C # нет оператора >>>, и распространяет ли он >> знак - это реализация, определенная в C / C ++ (основной потенциальный улов)
Майкл Барр
56
Ответ совершенно неверен в контексте языка Си. Нет значимого разделения на «арифметические» и «логические» сдвиги в C. В C сдвиги работают, как и ожидалось, для значений без знака и для значений с положительными знаками - они просто сдвигают биты. Для отрицательных значений смещение вправо определяется реализацией (то есть ничего нельзя сказать о том, что он делает в целом), а смещение вправо просто запрещено - оно вызывает неопределенное поведение.
2010 года
10
Одри, безусловно, есть разница между арифметическим и логическим смещением вправо. C просто оставляет реализацию выбора определенной. И сдвиг влево на отрицательные значения однозначно не запрещен. Сдвиньте 0xff000000 влево на один бит, и вы получите 0xfe000000.
Дерек Парк
16
A good optimizing compiler will substitute shifts for multiplications when possible. Какая? Сдвиг битов на несколько порядков быстрее, когда дело доходит до низкоуровневых операций ЦП, хороший оптимизирующий компилятор сделает прямо противоположное, то есть превратит обычные умножения на степени двух в сдвиги битов.
Ман
55
@ Ман, ты читаешь это назад из моего намерения. Заменить Y на X означает заменить X на Y. Y - это замена X. Таким образом, смещение - это замена умножения.
Дерек Парк
209

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

0110110

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

1101100

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

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

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

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

Сдвиг битов можно использовать для безумно быстрого умножения и деления, если вы работаете со степенью 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 и Microsoft Visual C ++ используют 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 ++ компиляторы должны делать это за вас, если вы использовали a structс двумя 8-битными членами, но на практике они не всегда.

FlySwat
источник
8
Более того, на процессорах Intel (и многих других) это сделать быстрее: int c, d; с = д << 2; Чем это: с = 4 * д; Иногда даже «c = d << 2 + d << 1» быстрее, чем «c = 6 * d» !! Я широко использовал эти приемы для графических функций в эпоху DOS, я не думаю, что они больше так полезны ...
Джо Пинеда
5
@James: не совсем, в настоящее время это скорее прошивка видеокарты, которая включает в себя подобный код, который должен выполняться не GPU, а GPU. Так что теоретически вам не нужно реализовывать подобный код (или как черную магическую функцию обратного корня Кармака) для графических функций :-)
Джо Пинеда
3
@JoePineda @james Авторы компиляторов определенно используют их. Если вы напишите, c=4*dвы получите сдвиг. Если вы пишете, k = (n<0)это может быть сделано также с помощью смен: k = (n>>31)&1избегать веток. В итоге, это улучшение в умении компиляторов означает, что теперь нет необходимости использовать эти приемы в коде C, и они ставят под угрозу читабельность и переносимость. Все еще очень хорошо знать их, если вы пишете, например, векторный код SSE; или в любой ситуации, когда вам это нужно быстро и есть хитрость, которой не пользуется компилятор (например, код графического процессора).
Грегго
2
Другой хороший пример: очень распространенная вещь, if(x >= 1 && x <= 9)которую можно сделать, так как if( (unsigned)(x-1) <=(unsigned)(9-1)) замена двух условных тестов на один может быть большим преимуществом в скорости; особенно когда это позволяет предикатное выполнение вместо ветвей. Я использовал это годами (когда это было оправдано), пока не заметил около 10 лет назад, что компиляторы начали выполнять это преобразование в оптимизаторе, а затем остановился. Тем не менее, это полезно знать, поскольку в подобных ситуациях компилятор не может выполнить преобразование за вас. Или если вы работаете над компилятором.
Грегго
3
Есть ли причина, по которой ваш «байт» составляет всего 7 бит?
Мейсон Уотмоф
104

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

Простой реальный пример в графическом программировании - 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;
robottobor
источник
1
0x7e0 - это то же самое, что 11111100000, то есть 2016 в десятичном виде.
Сахид
50

Битовая маскировка и сдвиг

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

Басти Функ
источник
Не проще ли разыграть свой оригинальный, скажем, 32-битный cl_uint, как что-то вроде cl_uchar4 и получить доступ к нужному байту непосредственно как * .s2?
Дэвид Х. Парри
27

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

char x = -1;
x >> 1;

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

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

AShelly
источник
4
Если я правильно помню, стандарт ANSI C прямо говорит, что это зависит от реализации, поэтому вам нужно проверить документацию вашего компилятора, чтобы увидеть, как он реализован, если вы хотите сместить целые числа со знаком в вашем коде.
Джо Пинеда
Да, я просто хотел подчеркнуть, что сам стандарт ANSI говорит так, это не тот случай, когда производители просто не следуют стандарту или что стандарт ничего не говорит об этом конкретном случае.
Джо Пинеда
22

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

  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&1 == 0(четный)
  6. Переключите n- й бит x:x ^ (1<<n)
Рави Пракаш
источник
Там должно быть еще несколько, что вы знаете сейчас?
ryyker
@ryyker Я добавил еще несколько. Я постараюсь постоянно обновлять его :)
Рави Пракаш
Индексируются ли x и n 0?
Reggaeguitar
Объявление 5 .: Что если это отрицательное число?
Питер Мортенсен
Итак, можем ли мы заключить, что 2 в двоичном коде, как 10 в десятичном? а сдвиг битов подобен добавлению или вычитанию еще одного числа за другим числом в десятичном виде?
Вилли Сатрио Нугрохо
8

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

Например:

(long) 4 >> 65

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

(long) 4 >> (65 % 64)

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

Патрик Монкельбан
источник
Да, интересно! В Си это технически неопределенное поведение . gcc 5.4.0выдает предупреждение, но выдает 2за 5 >> 65; также.
pizzapants184
2

Некоторые полезные битовые операции / манипуляции в Python.

Я реализовал ответ Рави Пракаша в Python.

# Basic bit operations
# Integer to binary
print(bin(10))

# Binary to integer
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 second bit is 0

# Toggle nth bit of x : x^(1 << n)
# take bin(10) == 1010 and toggling second bit in bin(10) we get 1110 === bin(14)
print(10^(1 << 2))
Питер Мортенсен
источник
-3

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

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

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

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

lukyer
источник