7. Чем отличается логический сдвиг двоичного кода от арифметического сдвига?
При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение. Арифметический сдвиг аналогичен логическому, но число считается знаковым, представленным в дополнительном коде. Так, при правом сдвиге старший бит сохраняет своё значение. Левый арифметический сдвиг идентичен логическому. Арифметический сдвиг: Вывод: арифметический сдвиг отличается от логического тем, что он не изменяет значение старшего бита, и предназначен для чисел со знаком.
8. Как изменяется значение числа при арифметическом сдвиге на 1 двоичный разряд влево?
При арифметическом сдвиге сдвиг влево соответствует умножению на 2 (в общем случае — на основание системы счисления).
9. Как изменяется значение числа при арифметическом сдвиге на 1 двоичный разряд вправо?
При арифметическом сдвиге сдвиг вправо соответствует делению на 2 (в общем случае — на основание системы счисления). 10. В каком порядке следует выполнять действия для получения прямого кода двоичного целого числа из дополнительного кода? (НЕ УВЕРЕН) Прямой обратный и дополнительный код - это модели представления целых чисел , как положительных, так и отрицательных. Во всех трех кодах старший разряд указывает на знак числа и он равен единице, если число отрицательное и нулю в противном случае. Остальные разряды содержат представление модуля числа. Различие между кодами наблюдается именно в способах представления модуля. Для положительного числа модуль во всех трех кодах представляется одинаково - это просто естественная запись двоичного числа. Для отрицательных чисел, в обратном коде это просто поразрядная инверсия прямого кода, а в дополнительном - к обратному коду, как к числу, просто прибавляется единица. Вычесть единицу и инвертировать, кроме бита знака.
04.11.2020 980.83 Кб 13 OEVM_laby.pdf
Побитовые операторы
Побитовые операторы интерпретируют операнды как последовательность из 32 битов (нулей и единиц). Они производят операции, используя двоичное представление числа, и возвращают новую последовательность из 32 бит (число) в качестве результата.
Эта глава требует дополнительных знаний в программировании и не очень важная, при первом чтении вы можете пропустить её и вернуться потом, когда захотите понять, как побитовые операторы работают.
Формат 32-битного целого числа со знаком
Побитовые операторы в JavaScript работают с 32-битными целыми числами в их двоичном представлении.
Это представление называется «32-битное целое со знаком, старшим битом слева и дополнением до двойки».
Разберём, как устроены числа внутри подробнее, это необходимо знать для битовых операций с ними.
- Что такое двоичная система счисления, вам, надеюсь, уже известно. При разборе побитовых операций мы будем обсуждать именно двоичное представление чисел, из 32 бит.
- Старший бит слева – это научное название для самого обычного порядка записи цифр (от большего разряда к меньшему). При этом, если больший разряд отсутствует, то соответствующий бит равен нулю. Примеры представления чисел в двоичной системе:
a = 0; // 00000000000000000000000000000000 a = 1; // 00000000000000000000000000000001 a = 2; // 00000000000000000000000000000010 a = 3; // 00000000000000000000000000000011 a = 255;// 0000000000000000000000001111111100000000000000000000000100111010Чтобы получить -314 , первый шаг – обратить биты числа: заменить 0 на 1 , а 1 на 0 :
11111111111111111111111011000101Второй шаг – к полученному двоичному числу прибавить единицу, обычным двоичным сложением: 11111111111111111111111011000101 + 1 = 11111111111111111111111011000110 . Итак, мы получили:
-314 = 11111111111111111111111011000110Список операторов
В следующей таблице перечислены все побитовые операторы. Далее операторы разобраны более подробно.
| Оператор | Использование | Описание |
|---|---|---|
| Побитовое И (AND) | a & b | Ставит 1 на бит результата, для которого соответствующие биты операндов равны 1. |
| Побитовое ИЛИ (OR) | a | b | Ставит 1 на бит результата, для которого хотя бы один из соответствующих битов операндов равен 1. |
| Побитовое исключающее ИЛИ (XOR) | a ^ b | Ставит 1 на бит результата, для которого только один из соответствующих битов операндов равен 1 (но не оба). |
| Побитовое НЕ (NOT) | ~a | Заменяет каждый бит операнда на противоположный. |
| Левый сдвиг | a | Сдвигает двоичное представление a на b битов влево, добавляя справа нули. |
| Правый сдвиг, переносящий знак | a >> b | Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты. |
| Правый сдвиг с заполнением нулями | a >>> b | Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты и добавляя нули слева. |
Побитовые операторы работают следующим образом:
- Операнды преобразуются в 32-битные целые числа, представленные последовательностью битов. Дробная часть, если она есть, отбрасывается.
- Для бинарных операторов – каждый бит в первом операнде рассматривается вместе с соответствующим битом второго операнда: первый бит с первым, второй со вторым и т.п. Оператор применяется к каждой паре бит, давая соответствующий бит результата.
- Получившаяся в результате последовательность бит интерпретируется как обычное число.
Посмотрим, как работают операторы, на примерах.
Вспомогательные функции parseInt, toString
Для удобной работы с примерами в этой статье, если вы захотите протестировать что-то в консоли, пригодятся две функции.
- parseInt(«11000», 2) – переводит строку с двоичной записью числа в число.
- n.toString(2) – получает для числа n запись в 2-ной системе в виде строки.
let access = parseInt("11000", 2); // получаем число из строки alert( access ); // 24, число с таким 2-ным представлением let access2 = access.toString(2); // обратно двоичную строку из числа alert( access2 ); // 11000Без них перевод в двоичную систему и обратно был бы куда менее удобен. Более подробно они разбираются в главе Числа.
& (Побитовое И)
Выполняет операцию И над каждой парой бит.
Результат a & b равен единице только когда оба бита a и b равны единице.
Таблица истинности для & :
| a | b | a & b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 & 9 (по осн. 10) = 00000000000000000000000000001000 (по осн. 2) = 8 (по осн. 10)| (Побитовое ИЛИ)
Выполняет операцию ИЛИ над каждой парой бит. Результат a | b равен 1, если хотя бы один бит из a,b равен 1.
Таблица истинности для | :
| a | b | a | b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 | 9 (по осн. 10) = 00000000000000000000000000001111 (по осн. 2) = 15 (по осн. 10)^ (Исключающее ИЛИ)
Выполняет операцию «Исключающее ИЛИ» над каждой парой бит.
a Исключающее ИЛИ b равно 1, если только a=1 или только b=1 , но не оба одновременно a=b=1 .
Таблица истинности для исключающего ИЛИ:
| a | b | a ^ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Как видно, оно даёт 1, если ЛИБО слева 1 , ЛИБО справа 1 , но не одновременно. Поэтому его и называют «исключающее ИЛИ».
9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 ^ 9 (по осн. 10) = 00000000000000000000000000000111 (по осн. 2) = 7 (по осн. 10)Исключающее ИЛИ в шифровании
Исключающее или можно использовать для шифрования, так как эта операция полностью обратима. Двойное применение исключающего ИЛИ с тем же аргументом даёт исходное число.
Иначе говоря, верна формула: a ^ b ^ b == a .
Пусть Вася хочет передать Пете секретную информацию data . Эта информация заранее превращена в число, например строка интерпретируется как последовательность кодов символов.
Вася и Петя заранее договариваются о числовом ключе шифрования key .
- Вася берёт двоичное представление data и делает операцию data ^ key . При необходимости data бьётся на части, равные по длине key , чтобы можно было провести побитовое ИЛИ ^ для каждой части. В JavaScript оператор ^ работает с 32-битными целыми числами, так что data нужно разбить на последовательность таких чисел.
- Результат data ^ key отправляется Пете, это шифровка.
Например, пусть в data очередное число равно 9 , а ключ key равен 1220461917 .
Данные: 9 в двоичном виде 00000000000000000000000000001001 Ключ: 1220461917 в двоичном виде 01001000101111101100010101011101 Результат операции 9 ^ key: 01001000101111101100010101010100 Результат в 10-ной системе (шифровка): 1220461908- Петя, получив очередное число шифровки 1220461908 , применяет к нему такую же операцию ^ key .
- Результатом будет исходное число data .
Полученная шифровка в двоичной системе: 9 ^ key = 1220461908 01001000101111101100010101010100 Ключ: 1220461917 в двоичном виде: 01001000101111101100010101011101 Результат операции 1220461917 ^ key: 00000000000000000000000000001001 Результат в 10-ной системе (исходное сообщение): 9Конечно, такое шифрование поддаётся частотному анализу и другим методам дешифровки, поэтому современные алгоритмы используют операцию XOR ^ как одну из важных частей более сложной многоступенчатой схемы.
~ (Побитовое НЕ)
Производит операцию НЕ над каждым битом, заменяя его на обратный ему.
Таблица истинности для НЕ:
| a | ~a |
|---|---|
| 0 | 1 |
| 1 | 0 |
9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) -------------------------------- ~9 (по осн. 10) = 11111111111111111111111111110110 (по осн. 2) = -10 (по осн. 10)
Из-за внутреннего представления отрицательных чисел получается так, что ~n == -(n+1) .
Урок 31 — 35
Арифметические и логические (битовые) операции. Маски. Арифметические и логические (битовые) операции. Маски
§26. Особенности представления чисел в компьютере. §27. Хранение в памяти целых чисел. § 28. Операции с целыми числами. §29. Хранение в памяти вещественных чисел
Об операции сдвига вспоминают гораздо реже, чем она того заслуживает. Перечитайте ещё раз алгоритм умножения, описанный выше, и вы убедитесь, что он весь построен на сдвигах. Сдвиги незаменимы тогда, когда требуется проделать ту или иную обработку каждого бита, входящего в число. Наконец, сдвиги двоичного числа позволяют быстро умножить или разделить число на степени двойки: 2, 4, 8 и т. д. Поэтому программисты очень ценят и широко применяют всевозможные разновидности сдвигов.
Идея операции сдвига довольно проста: все биты кода одновременно сдвигаются в соседние разряды 1 влево или вправо (рис. 4.16).
1 Аппаратно сдвиг реализуется необычайно просто и изящно: регистр, содержащий число, сбрасывается в ноль, при этом из тех разрядов, где исчезла единица, электрический импульс проходит в соседние и устанавливает их в единицу. При этом важно, что все разряды обрабатываются одновременно.
Рис. 4.16
Отдельно надо поговорить о двух крайних битах, у которых «нет соседей». Для определённости обсудим сдвиг влево. Для самого младшего бита (на рис. 4.16 он крайний справа) данные взять неоткуда, поэтому в него просто заносится ноль. Самый старший (крайний слева) бит должен потеряться, так как его некуда сохранить. Чтобы данные не пропали, содержимое этого разряда копируется в специальную ячейку процессора — бит переноса 2 С (от англ, carry — перенос), с которым может работать процессор.
2 При программировании на языках высокого уровня бит переноса недоступен.
Рассмотренный тип сдвига обычно называется логическим сдвигом. Его можно использовать для быстрого умножения и деления. Рассмотрим, например, 8-разрядный двоичный код 0000 1100, который представляет число 1210. Выполнив логический сдвиг влево, получим 0001 1000, т. е. число 2410, которое вдвое больше! Это не случайность: вспомните, что происходит, если к десятичному числу справа приписать дополнительный ноль, например 34 -> 340.
При сдвиге вправо любое чётное число уменьшается ровно в 2 раза. В случае нечётного значения происходит деление нацело, при котором остаток отбрасывается. Например, из 0001 0001 = 1710 при сдвиге вправо получается 0000 1000 = 810.
Логический сдвиг влево на 1 разряд увеличивает целое положительное число вдвое, а сдвиг вправо делит на 2 нацело.
Пример. Для умножения числа, находящегося в ячейке Z, на 10 можно использовать такой алгоритм:
1. Сдвиг влево Z (в ячейке Z получаем 2Z0, где Z0 — исходное число).
2. X = Z (сохраним 2Z0).
3. Сдвиг на 2 бита влево X (вычислили 8Z0).
Для некоторых компьютеров такая последовательность выполняется быстрее, чем стандартная операция умножения.
Посмотрим, что получится для отрицательных чисел. Сдвинем влево код 1111 1000 (8-разрядное представление числа —8):
получится 1111 0000. Легко проверить, что это дополнительный код числа -16, т. е. значение удвоилось! Но со сдвигом вправо ничего не получается: из 1111 1000 получаем 0111 1100 — это код положительного числа! Дело в том, что при сдвиге вправо отрицательных чисел, в отличие от положительных, старший разряд надо заполнять не нулём, а единицей! Чтобы исправить положение, вводится ещё одна разновидность сдвига — арифметический сдвиг. Его единственное отличие от логического состоит в том, что старший (знаковый) бит не меняется, т. е. знак числа остаётся прежним (рис. 4.17).
Рис. 4.17
Если применить арифметический сдвиг к коду 1111 1000, получается 1111 1100 — дополнительный код числа -4, т. е. произошло деление на 2. В качестве упражнения проверьте, как ведёт себя отрицательное нечётное число при арифметическом сдвиге вправо.
Арифметический сдвиг влево не требуется, поскольку он ничем не отличается от обычного логического сдвига.
То, что в результате логических сдвигов содержимое крайних разрядов теряется, не всегда удобно. Поэтому в компьютере предусмотрен циклический сдвиг, при котором бит из одного крайнего разряда переносится в другой («по циклу», рис. 4.18).
Рис. 4.18
Циклический сдвиг позволяет «просмотреть» все биты и вернуться к исходному значению. Если сделать последовательно 8 циклических сдвигов 8-битного числа, каждый его бит на каком-то шаге окажется на месте младшего разряда, где его можно выделить с помощью логической операции «И» с маской 1. Так можно «просматривать» не только младший, но и любой другой разряд (например, для выделения старшего разряда нужно использовать маску 8016).
Следующая страница Вопросы и задания
Cкачать материалы урока
Битовые операции
Во многих языках программирования допустимы логические операции над битами целых чисел. В отличие от обычных логических операций, результатом выполнения которых является логический тип данных, битовые логические операции просто изменяют целое число согласно определенным правилам. Точнее битовые операции изменяют отдельные биты двоичного представления числа, в результате чего изменяется его десятичное значение.
Например, в языке программирования Паскаль обычные логические операции и логические операции над битами обозначают с помощью одних и тех же ключевых слов: not, and, or, xor . Компилятор определяет, что имелось в виду в зависимости от контекста использования этих слов. Обычные логические операции объединяют два и более простых логических выражения. Например, (a > 0) and (c != b) , (c < a) or(not b) и т.п. В свою очередь побитовые логические операции выполняются исключительно над целыми числами (или переменными, которые их содержат). Например, a and b, a or 8, not 247 .
Как понять побитовые операции
1. Переведем пару произвольных целых чисел до 256 (один байт) в двоичное представление.
6710 = 0100 00112 11410 = 0111 00102
2. Теперь расположим биты второго числа под соответствующими битами первого и выполним обычные логические операции к цифрам, стоящим в одинаковых разрядах первого и второго числа. Например, если в последнем (младшем) разряде одного числа стоит 1, а другого числа — 0, то логическая операция and вернет 0, а or вернет 1. Операцию not применим только к первому числу.
3. Переведем результат в десятичную систему счисления.
01000010 = 26 + 21 = 64 + 2 = 66 01110011 = 26 + 25 + 24 + 21 + 20 = 64 + 32 + 16 + 2 + 1 = 115 00110001 = 25 + 24 + 20 = 32 + 16 + 1 = 49 10111100 = 27 + 25 + 24 + 23 + 22 = 128 + 32 + 16 + 8 + 4 = 188
4. Итак, в результате побитовых логических операций получилось следующее:
67 and 114 = 66 67 or 114 = 115 67 xor 114 = 49 not 67 = 188
Вот еще один пример выполнения логических операций над битами. Проверьте его правильность самостоятельно.
5 and 6 = 4 5 or 6 = 7 5 xor 6 = 3 not 5 = 250
Зачем нужны побитовые логические операции
Глядя на результат побитовых операций, не сразу можно уловить закономерности в их результате. Поэтому непонятно, зачем нужны такие операции. Однако, они находят свое применение. В байтах не всегда хранятся числа. Байт или ячейка памяти может хранить набор флагов (установлен — сброшен), представляющих собой информацию о состоянии чего-либо. С помощью битовых логических операций можно проверить, какие биты в байте установлены в единицу, можно обнулить биты или, наоборот, установить в единицу. Также существует возможность сменить значения битов на противоположные.
Проверка битов
Проверка битов осуществляется с помощью битовой логической операции and .
Представим, что имеется байт памяти с неизвестным нам содержимым. Известно, что логическая операция and возвращает 1, если только оба операнда содержат 1. Если к неизвестному числу применить побитовое логическое умножение (операцию and ) на число 255 (что в двоичном представлении 1111 1111), то в результате мы получим неизвестное число. Обнулятся те единицы двоичного представления числа 255, которые будут умножены на разряды неизвестного числа, содержащие 0. Например, пусть неизвестное число 38 (0010 0110), тогда проверка битов будет выглядеть так:
Другими словами, x and 255 = x .
Обнуление битов
Чтобы обнулить какой-либо бит числа, нужно его логически умножить на 0.
Обратим внимание на следующее:
1111 1110 = 254 = 255 - 1 = 255 - 20 1111 1101 = 253 = 255 - 2 = 255 - 21 1111 1011 = 251 = 255 - 4 = 255 - 22 1111 0111 = 247 = 255 - 8 = 255 - 23 1110 1111 = 239 = 255 - 16 = 255 - 24 1101 1111 = 223 = 255 - 32 = 255 - 25 1011 1111 = 191 = 255 - 64 = 255 - 26 0111 1111 = 127 = 255 - 128 = 255 - 27
Т.е. чтобы обнулить четвертый с конца бит числа x , надо его логически умножить на 247 или на (255 — 23).
Установка битов в единицу
Для установки битов в единицу используется побитовая логическая операция or . Если мы логически сложим двоичное представление числа x с 0000 0000, то получим само число х . Но вот если мы в каком-нибудь бите второго слагаемого напишем единицу, то в результате в этом бите будет стоять единица.
Отметим также, что:
0000 0001 = 20 = 1 0000 0010 = 21 = 2 0000 0100 = 22 = 4 0000 1000 = 23 = 8 0001 0000 = 24 = 16 0010 0000 = 25 = 32 0100 0000 = 26 = 64 1000 0000 = 27 = 128
Поэтому, например, чтобы установить второй по старшинству бит числа x в единицу, надо его логически сложить с 64 ( x or 64 ).
Смена значений битов
Для смены значений битов на противоположные используется битовая операция xor . Чтобы инвертировать определенный бит числа x , в такой же по разряду бит второго числа записывают единицу. Если же требуется инвертировать все биты числа x , то используют побитовую операцию исключающего ИЛИ ( xor ) с числом 255 (1111 1111).
Операции побитового циклического сдвига
Помимо побитовых логических операций во многих языках программирования предусмотрены битовые операции циклического сдвига влево или вправо. Например, в языке программирования Паскаль эти операции обозначаются shl (сдвиг влево) и shr (сдвиг вправо).
Первым операндом операций сдвига служит целое число, над которым выполняется операция. Во втором операнде указывается, на сколько позиций сдвигаются биты первого числа влево или вправо. Например, 105 shl 3 или 105 shr 4 . Число 105 в двоичном представлении имеет вид 0110 1001.
При сдвиге влево теряются старшие биты исходного числа, на их место становятся младшие. Освободившиеся младшие разряды заполняются нулями.
При сдвиге вправо теряются младшие биты исходного числа, на их место становятся старшие. Освободившиеся старшие разряды заполняются нулями, если исходное число было положительным.