Как инвертировать двоичное число

Assembler: Arithmetic

Доброго времени суток, читатель! Снова с вами команда IT Root и на повестке, как вы уже могли догадаться — Assembler. А именно работа с положительными и отрицательными числами. Ассемблер на платформе x86 содержит множество арифметических инструкций, начиная с обычного сложения и вычитания и заканчивая логическими операторами. Но сперва поговорим о числах)

Положительные числа

Это самое простое. Вы уже должны представлять, как хранится положительное число в памяти компьютера. Напомню, что биты двоичного числа принято нумеровать от младшего к старшему, то есть справа налево. Каждый бит с порядковым номером n беззнакового целого двоичного числа, соответствует значению числа 2n.

В процессорах семейства Intel основной единицей хранения всех типов является байт. Байт, как уже говорилось, состоит из восьми битов.

При работе с числами помните, что в байт можно записать число со значением не более 255, в слово — со значением не более 65 535 и т.д. Поэтому будьте внимательны, особенно при операциях сложения/умножения. Например, если при работе с байтом вы выполните операцию сложения 255 + 1, то в результате должно получиться число 256. Однако если вы запишите результат в байт, то, к вашему удивлению, результатом будет не 256, а 0.

Например, максимальное значение, которое может хранить слово данных — это 65 535 или (216–1). Почему? Потому что 216 = 65 536 — столько различных чисел может хранить слово данных. Однако сюда же входит число 0, поэтому слово данных может хранить числа от 0 до 65 535.

Отрицательные числа

Мы разобрались, как в памяти компьютера представлены положительные числа, то есть числа без знака. Но ведь числа бывают и отрицательными, то есть числа со знаком минус. Чтобы применять те же самые байты и слова для представления отрицательных чисел, существует специальная операция, которая называется дополнение до двух. Но прежде чем рассмотреть эту операцию, покажем, как отрицательное число отличить от положительного.

Для того чтобы указать знак числа, достаточно одного разряда (бита). Обычно знаковый бит занимает старший разряд числа. Если старший бит числа равен 0, то число считается положительным. Если старший разряд числа равен 1, то число считается отрицательным.

Как вы успели заметить, для представления числа со знаком требуется использовать старший бит для определения знака числа. Это означает, что этот старший бит уже нельзя использовать для записи самого числа, то есть максимальное значение, которое мы сможем записать в байт, будет уже не 255, а всего 127.

Инверсия двоичного числа

А теперь разберёмся с загадочной операцией дополнение до двух. Для изменения знака числа выполняется инверсия, то есть для числа в двоичном представлении все нули заменяются единицами, а все единицы — нулями. Затем к полученному результату прибавляют 1. Возьмём, например, десятичное число 110 (в двоичной системе это число 01101110). Как видим, после выполнения этих преобразований в старшем разряде у нас 1, то есть число отрицательное.

Преобразования положительного десятичного числа со знаком в двоичное число выполняется также как и для чисел без знака. Преобразования отрицательного десятичного числа со знаком в отрицательное двоичное число выполняется при помощи операции дополнение до двух (с использованием двоичного дополнительного кода).

Преобразования положительного двоичного числа со знаком (в старшем бите 0) в десятичное число выполняется также как и для чисел без знака. Преобразование отрицательного двоичного числа (в старшем бите 1) в десятичное число выполняется путём нахождения его дополнительного кода. То есть для двоичного числа 10010010 операция будет следующей:

В итоге получаем число 110, но поскольку в исходном числе старший бит был равен 1, то это отрицательное число, то есть –110.

AfterWords

В этом посте мы разобрались с положительными и отрицательными числами в двоичной системе счисления, а также поняли принцип инверсии двоичного числа. Для работы с языками низкого уровня эти знания очень важны! Что ж, пожалуй на этом мы закончим статью. Успехов!)

Не забывайте, что множество интересных статей можно найти на нашем Telegram канале и в Telegram боте, также все статьи мы публикуем в Twitter и Facebook

Как инвертировать двоичное число

Побитовые операторы и двоичное представление чисел

Язык программирования С++ обладает полным набором побитовых операторов. Побитовые операторы применяются при выполнении операций с битами в двоичном представлении числовых значений. Прежде чем непосредственно рассмотреть сами операторы, кратко остановимся на концепции двоичного представления числовых значений.

Как известно, целые числа представляются в виде последовательности цифр. Такое представление чисел называется позиционным. Весь набор цифр, которые могут использоваться в позиционном представлении числа, определяют систему счисления. В повседневной жизни используется десятичная система счисления, в которой числа представлены цифрами от 0 до 9.

В программировании более популярны системы счисления с количеством цифр, равным степени двойки: восьмеричная и шестнадцатеричная. Однако двоичная система счисления — вне конкуренции. В этой системе счисления числа записываются последовательностью из двух цифр: 0 и 1.

Каждая позиция в двоичном представлении числа соответствует биту. Таким образом, с помощью бита можно записать два значения: 0 или 1. Если для представления числа используется n бит, то в этом случае существует 2 n различных комбинаций, каждая из которых соответствует отдельному числу. Например, с помощью 8 бит(1 байт) можно записать 2 8 = 256 чисел.

При представлении двоичным кодом положительных чисел можно было бы использовать стандартное математическое представление числа в двоичной системе. Однако на практике приходится иметь дело и с отрицательными числами, причем с технической точки зрения знаком «минус» здесь не обойтись — минус можно написать на бумаге, а реализовать его в памяти компьютера намного сложнее.

Для определения знака числа используют старший бит в позиционной записи. Нулевой старший бит соответствует положительному числу, а единичный старший бит соответствует отрицательному числу. При этом перевод для положительных чисел из двоичной системы счисления в десятичную осуществляется стандартными методами: если в двоичном представлении число позиционно задается как b_nb_n-1. b₂b₁b₀ (причем цифры b_i могут принимать значения 0 или 1, а старший бит для положительных чисел равен 0), то в десятичной системе число вычисляется как b₀2 0 + b₁2 1 + b₂2 2 + . + b_n-12 n-1 + b_n2 n .

С отрицательными числами дела обстоят несколько сложнее. Чтобы перевести отрицательное число с позиционным представлением в двоичной системе b_nb_n-1. b₂b₁b₀ (старший бит для отрицательного числа b_n = 1), необходимо проделать несложную процедуру из двух этапов.

Во-первых, производится побитовое инвертирование кода, т.е. каждый бит в представлении числа меняется на противоположный: 0 на 1 и 1 на 0.

Во-вторых, результат переводится в десятичную систему и к нему добавляется 1. Это модуль отрицательного числа. Чтобы получить само число, модуль числа необходимо умножить на -1.

Чтобы перевести число из десятичной системы в двоичную, проделывают обратную процедуру: от модуля отрицательного числа отнимается 1, результат переводится в бинарный код, после чего проводится побитовое инвертирование.

Проиллюстрируем это не примере.

Рассмотрим 8-битовое бинарное положительное число 01001011, что в десятичной системе счисления соответствует числу 2 0 + 2 1 + 2 3 + 2 6 = 1 + 2 + 8 + 64 = 75.

Определим бинарное машинное представление для отрицательного числа -75. Отнимем от модуля числа единицу, получаем 74. Бинарное представление для этого числа 01001010 (74 = 2 1 + 2 3 + 2 6 ). После побитового инвертирования из числа 01001010 получаем 10110101. Это и есть представление числа -75.

В том, что это так, легко убедиться: сложим числа 01001010 и 10110101. Формально получаем 100000000, однако поскольку числа 8-битовые, лишний единичный старший бит отбрасывается, и получается представление 00000000, что соответствует нулю, как и должно быть.

Теперь рассмотрим основные побитовые операции и операторы, которые используются для этого в языке программирования С++. Список побитовых операторов приведен в таблице 1.6.

a является число, которое получается побитовым инвертированием числа а.

к числу 5 требует особых пояснений. На самом деле в 8-битовом представлении число 5 имеет вид 00000101. В предыдущих случаях нулевые старшие разряды роли не играли, поэтому они явно не указывались. При инвертировании наличие старших нулевых битов важно. Инвертирование дает 11111010. Это не что иное, как представление в двоичном машинном коде числа -6. Последнее читатель может проверить самостоятельно.

Особенности операций в двоичной системе таковы, что сдвиг в побитовом представлении числа на одну позицию влево означает умножение этого числа на 2. Следует только помнить, что с определенного момента при сдвиге вправо теряются старшие биты.

Представим, что число задается 8 битами.

Если воспользоваться командной 1 << 6, получим в качестве результата значение 2 6 =64.

Действительно, десятичное число 1 в двоичной системе в 8-битовом представлении задается как 00000001. после сдвига влево на 6 позиций получаем 01000000, что в десятичной системе соответствует числу 64.

Однако если воспользоваться командой 1 << 7, получим в качестве результата -128.

Объясняется это следующим обстоятельством

После сдвига влево на 7 позиций из числа 00000001, получаем число 10000000.

Это отрицательное число, о чем свидетельствует старший единичный бит.

Переводя это число в десятичную систему, сначала инвертируем бинарный код и получаем 01111111. Это код числа 127. Чтобы получить конечное значение, необходимо прибавить к этому результату 1 и добавить минус — в результате приходим к значению -128.

О битовых операциях

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

Введение

Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.

Я расскажу о следующих побитовых операторах:

• | (Побитовое ИЛИ (OR)),
• & (Побитовое И (AND)),
• ^ (Исключающее ИЛИ (XOR)),

Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.

О битовых операторах вам также необходимо знать:

1. Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
2. Большинство битовых операций являются операциями составного присваивания.

Побитовое ИЛИ (OR)

Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:

38 | 53 будет таким:

A	0	0	1	0	0	1	1	0
B	0	0	1	1	0	1	0	1
A | B	0	0	1	1	0	1	1	1

В итоге мы получаем 110111₂ , или 55₁₀ .

Побитовое И (AND)

Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

Пример работы побитового И на выражении 38 & 53:

A	0	0	1	0	0	1	1	0
B	0	0	1	1	0	1	0	1
A & B	0	0	1	0	0	1	0	0

Как результат, получаем 100100₂ , или 36₁₀ .

С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2 ? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.

Исключающее ИЛИ (XOR)

Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

Например, выражение 138^43 будет равно…

A	1	0	0	0	1	0	1	0
B	0	0	1	0	1	0	1	1
A ^ B	1	0	1	0	0	0	0	1

С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.

Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:

Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.

Побитовое отрицание (NOT)

Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.

Вот, например, операция

Результатом будет 203₁₀

При использовании побитового отрицания знак результата всегда будет противоположен знаку исходного числа (при работе со знаковыми числами). Почему так происходит, узнаете прямо сейчас.

Дополнительный код

Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.

Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.

Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.

Например, если мы имеем 109:

Представленным выше методом мы получаем -109 в дополнительном коде.
Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.

Побитовый сдвиг влево

Побитовые сдвиги немного отличаются от рассмотренных ранее битовых операций. Побитовый сдвиг влево сдвигает биты своего операнда на N количество битов влево, начиная с младшего бита. Пустые места после сдвига заполняются нулями. Происходит это так:

A	1	0	1	1	0	1	0	0
A<<2	1	1	0	1	0	0	0	0

Интересной особенностью сдвига влево на N позиций является то, что это эквивалентно умножению числа на 2 N . Таким образом, 43<<4 == 43*Math.pow(2,4) . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

Побитовый сдвиг вправо

Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.

Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.

Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2 N . Опять же, это выполняется намного быстрее обычного деления.

Вывод

Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.

Двоичное число: прямой, обратный и дополнительный коды

Прямой, обратный и дополнительный коды двоичного числа — способы представления двоичных чисел с фиксированной запятой в компьютерной (микроконтроллерной) арифметике, предназначенные для записи отрицательных и неотрицательных чисел

Мы знаем, что десятичное число можно представить в двоичном виде. К примеру, десятичное число 100 в двоичном виде будет равно 1100100, или в восьмибитном представлении 0110 0100. А как представить отрицательное десятичное число в двоичном виде и произвести с ним арифметические операции? Для этого и предназначены разные способы представления чисел в двоичном коде.
Сразу отмечу, что положительные числа в двоичном коде вне зависимости от способа представления (прямой, обратный или дополнительный коды) имеют одинаковый вид.

Прямой код

Прямой код — способ представления двоичных чисел с фиксированной запятой. Главным образом используется для записи неотрицательных чисел

Прямой код используется в двух вариантах.
В первом (основной) — для записи только неотрицательных чисел:

В этом варианте (для восьмибитного двоичного числа) мы можем записать максимальное число 255 (всего чисел 256 — от 0 до 255)

Второй вариант — для записи как положительных, так и отрицательных чисел.
В этом случае старший бит (в нашем случае — восьмой) объявляется знаковым разрядом (знаковым битом).
При этом, если:
— знаковый разряд равен 0, то число положительное
— знаковый разряд равен 1, то число отрицательное

В этом случае диапазон десятичных чисел, которые можно записать в прямом коде составляет от — 127 до +127:

Подводя итоги вопроса, не влезая в его дебри, скажу одно:
Прямой код используется главным образом для представления неотрицательных чисел.
Использование прямого кода для представления отрицательных чисел является неэффективным — очень сложно реализовать арифметические операции и, кроме того, в прямом коде два представления нуля — положительный ноль и отрицательный ноль (чего не бывает):

Обратный код

Обратный код — метод вычислительной математики, позволяющий вычесть одно число из другого, используя только операцию сложения.
Обратный двоичный код положительного числа состоит из одноразрядного кода знака (битового знака) — двоичной цифры 0, за которым следует значение числа.
Обратный двоичный код отрицательного числа состоит из одноразрядного кода знака (битового знака) — двоичной цифры 1, за которым следует инвертированное значение положительного числа.

Для неотрицательных чисел обратный код двоичного числа имеет тот же вид, что и запись неотрицательного числа в прямом коде.
Для отрицательных чисел обратный код получается из неотрицательного числа в прямом коде, путем инвертирования всех битов (1 меняем на 0, а 0 меняем на 1).
Для преобразования отрицательного числа записанное в обратном коде в положительное достаточного его проинвертировать.

При 8-битном двоичном числе — знаковый бит (как и в прямом коде) старший (8-й)

Диапазон десятичных чисел, который можно записать в обратном коде от -127 до + 127

Арифметические операции с отрицательными числами в обратном коде:

1-й пример (для положительного результата)
Дано два числа:
100 = 0110 0100
-25 = — 0001 1001
Необходимо их сложить:
100 + (-25) = 100 — 25 = 75

1-й этап
Переводим число -25 в двоичное число в обратном коде:
25 = 0 001 1001
-25= 1 110 0110
и складываем два числа:
0 110 0100 (100) + 1 110 0110 (-25) = 1 0 100 1010, отбрасываем старшую 1 (у нас получился лишний 9-й разряд — переполнение), = 0 100 1010
2-й этап
Отброшенную в результате старшую единицу прибавляем к результату:
0 100 1010 + 1 = 0 100 1011 (знаковый бит = 0 , значит число положительное), что равно 75 в десятичной системе

2-й пример (для отрицательного результата)
Дано два числа:
5 = 0000 0101
-10 = — 0000 1010
Необходимо их сложить:
5 + (-10) = 5 — 10 = -5

1-й этап
Переводим число -10 в двоичное число в обратном коде:
10 = 0 000 1010
-10= 1 111 0101
и складываем два числа:
0 000 0101 (5) + 1 111 0101 (-10) = 1 111 1010 (знаковый бит = 1 , значит число отрицательное)

2-й этап
Раз результат получился отрицательный, значит число представлено в обратном коде.
Переводим результат в прямой код (путем инвертирования значения, знаковый бит не трогаем):
1 111 1010 —-> 1 000 0101
Проверяем:
1 000 0101 = — 0000 0101 = -5

Обратный код решает проблему сложения и вычитания чисел с различными знаками, но и имеет свои недостатки:
— арифметические операции проводятся в два этапа
— как и в прямом коде два представления нуля — положительный и отрицательный

Дополнительный код

Дополнительный код — наиболее распространенный способ представления отрицательных чисел. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел.

В дополнительном коде (как и в прямом и обратном) старший разряд отводится для представления знака числа (знаковый бит).

Диапазон десятичных чисел которые можно записать в дополнительном коде от -128 до +127. Запись положительных двоичных чисел в дополнительном коде та-же, что и в прямом и обратном кодах.

Дополнительный код отрицательного числа можно получить двумя способами
1-й способ:
— инвертируем значение отрицательного числа, записанного в прямом коде (знаковый бит не трогаем)
— к полученной инверсии прибавляем 1
Пример:
Дано десятичное число -10
Переводим в прямой код:
10 = 0 000 1010 —-> -10 = 1 000 1010
Инвертируем значение (получаем обратный код):
1 000 1010 —-> 1 111 0101
К полученной инверсии прибавляем 1:
1 111 0101 + 1 = 1 111 0110 — десятичное число -10 в дополнительном коде

2-й способ:
Вычитание числа из нуля
Дано десятичное число 10, необходимо получить отрицательное число (-10) в дополнительном двоичном коде
Переводим 10 в двоичное число:
10 = 0 000 1010
Вычитаем из нуля:
0 — 0000 1010 = 1 111 0110 — десятичное число -10 в дополнительном коде

Арифметические операции с отрицательными числами в дополнительном коде

Дано: необходимо сложить два числа -10 и 5
-10 + 5 = -5
Решение:
5 = 0000 0101
-10 = 1111 0110 (в дополнительном коде)
Складываем:
1111 0110 + 0000 0101 = 1111 1011, что соответствует числу -5 в дополнительном коде

Как мы видим на этом примере — дополнительный код отрицательного двоичного числа наиболее подходит для выполнения арифметических операций сложения и вычитания отрицательных чисел.

Вывод:
1. Для арифметических операций сложения и вычитания положительных двоичных чисел наиболее подходит применение прямого кода
2. Для арифметических операций сложения и вычитания отрицательных двоичных чисел наиболее подходит применение дополнительного кода