Ответ 1

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

Операторы

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

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

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

Также обратите внимание, что 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 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. Сдвиг этого на четыре позиции вправо с арифметическим сдвигом (-2, 147, 483, 552 >> 4) даст нам:

11111000 00000000 00000000 00000110

или число -134, 217,722.

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

Ответ 2

Скажем, у нас есть один байт:

0110110

Применяя один левый битдвиг, мы получаем:

1101100

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

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

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

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

Bitshifting может использоваться для безумно быстрого умножения и деления при условии, что вы работаете с мощностью 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-разрядном целое. Например, в С#:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

В С++ компиляторы должны сделать это для вас, если вы использовали struct с двумя 8-битными элементами, но на практике это не всегда.

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

char x = -1;
x >> 1;

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

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

Ответ 6

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

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<<n)

Ответ 7

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

Например:

(long) 4 >> 65

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

(long) 4 >> (65 % 64)

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

Ответ 8

Некоторые полезные битовые операции/манипуляции в 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)) 

Ответ 9

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

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

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

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