Отрицательные числа в двоичной системе
До сих пор мы рассматривали только положительные целые числа и то, как они хранятся в наших машинах. Однако иногда нам необходимо работать и с отрицательными числами. Как же они представлены в компьютерах?
Мы знаем, что число 1 в двоичной системе представляется как
0001, число 6 — как 0110 и т.д. Число 0 выглядит как последовательность из одних нулей 0000. Один из логических приёмов, позволяющих хранить отрицательные числа, заключается в использовании «особого» бита, который указывает, отрицательное число или нет. Этот бит равен 1, если число отрицательное, и равен 0 в противном случае. Именно так большинство компьютеров и работают с отрицательными числами — у них есть специальный бит в самом левом разряде двоичной записи, который устанавливается в 1, если число отрицательное, и в 0, если число положительное.Но здесь есть нюанс: важно не просто поместить 1 в первый бит двоичного представления. В десятичной системе (наши обычные числа 4, 5, 10, 311 и т.д.) положительные и отрицательные числа взаимно уничтожают друг друга. Например, 6 + (-6) = 0. Это свойство не должно исчезать и в двоичной системе. То есть, если мы складываем 6 и -6 в двоичной системе, мы тоже должны получить 0.
Представьте, что у нас есть 4 бита для представления числа и 1 бит для хранения знака, итого 5 бит. Тогда 6 будет иметь вид
00110, а 0 — 00000. Двоичное представление -6 должно быть таким, чтобы при сложении с 6 результат получался 0. Забегая вперёд, -6 будет 11010. Следовательно, если сложить 00110 и 11010 в двоичной системе, получится 00000.Чтобы перейти от положительного числа к отрицательному и обратно в двоичной системе, можно воспользоваться простым приёмом: нужно инвертировать все биты (все 0 заменить на 1, а 1 — на 0), а затем прибавить 1 к результату.
x = 6 # 00110
x = ~x + 1 # Перевернуть все биты и прибавить 1 => -6
x = ~x + 1 # Перевернуть все биты и прибавить 1 => 6
z = 0 # 00000
z = ~z + 1 # Перевернуть и прибавить 1 => 0
z = ~z + 1 # Перевернуть и прибавить 1 => 0
z = ~z # -1 (все биты в 1 в двоичном представлении)
z = ~z # 0 (все биты в 0 в двоичном представлении)Обратите внимание, что сложение чисел в двоичной системе происходит аналогично сложению в десятичной системе: начинаем с наименее значимого разряда и учитываем перенос при сложении.
В зависимости от языка и реализации, компьютеры могут хранить числа по-разному. В языках вроде C++ и Java есть различные типы, рассчитанные на разные диапазоны чисел. Например, тип
int хранит целые числа в 32 битах: 31 бит отводится на само число и 1 бит на знак. Таким образом, возможный диапазон значений — от -2,147,483,648 () до 2,147,483,647 (). Обратите внимание, что верхняя граница положительных чисел на единицу меньше по модулю. Это связано с тем, что положительные числа начинаются с 0-бита, а первым числом, начинающимся с 0-бита, является само 0 (все нули).Задача
В волшебной стране семёрок всё подчинено числу 7, и поэтому местные учёные-разработчики создали систему, в которой двоичные числа (как положительные, так и отрицательные) хранятся в 77 битах.
Дана битовая строка
b, требуется вычислить отрицательное значение этого числа и вывести результат в 77-битном формате.Ввод
Во вводе содержится единственная строка — битовая запись
b (1 ≤ |b| ≤ 77). Она может представлять как положительное, так и отрицательное число.Вывод
Выведите одну строку, соответствующую
-b, длиной 77 бит.Примеры
Ввод | Вывод |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB