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

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

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

8 Solutions collect form web for “Что такое операторы бит-сдвига (бит-сдвиг) и как они работают?”

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

Операторы

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

Все эти операторы могут применяться к целочисленным значениям ( 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 эквивалентен умножению на 2 N.

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

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

Например, еще в прежние времена мы использовали режим 13h (320×200 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 ), которая может выполнять небольшие сдвиги влево и добавлять одновременно, с инструкцией as и 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).

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

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

Например:

 (long) 4 >> 65 

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

 (long) 4 >> (65 % 64) 

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

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

  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 четным или нечетным: x&1 == 0 (четное)
  6. Переключить n- й бит x: x ^ (1<

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

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

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

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

Interesting Posts

Как избавиться от автогенерируемого порядкового номера в имени устройства сети в Windows?

Как определить, какой тип Wi-Fi поддерживается вашим драйвером в Linux

Существует ли полная лицензия Windows 8 на продажу? (Не OEM, не обновление)

Шаблон регулярного выражения для соответствия, Исключая, когда … / За исключением между

Каковы плюсы и минусы использования альтернативного DNS вместо DNS-сервера ISP?

Удобный способ планирования заданий в Mac OS X

Bluetooth гарнитуры и появляется в звуковых устройствах, но отображается как отключено?

Что случилось с этим флеш-накопителем емкостью 64 ГБ, появляющимся в виде двух дисков?

Перенаправление портов после NAT класса несущей?

Повышенная подсказка командной строки не может получить доступ к общим дискам

Как сделать радарную диаграмму пирога

Агрегация перекрывающихся группировок в сводной таблице

Как удалить запись в Auto Complete в Microsoft Edge

Как применять условное форматирование адиаторной ячейки в момент поворота, когда ячейка пуста

Используется IP-адрес 0.0.0.0 или нет?

Давайте будем гением компьютера.