Целые числа и дополнение до 10

Хранение целых чисел на компьютере в десятичном мире

Для начала представим себе, что данные в компьютерах хранятся в ячейках-"битах", каждое из которых может принимать 10 разных значений. В таком случае очень легко хранить положительные целые числа: каждое число по цифрам записывается в ячейки памяти. Реальный процессор может выполнять арифметические с такими числами, но есть проблема: чем больше цифр в числах, которые он сможет складывать за одну операцию (такт), тем сложнее его проектировать, тем больше тепла он выделяет и энергии потребляет. Поэтому необходимо выбрать некоторое фиксированную "стандартную" длину чисел так, чтобы с одной стороны для большей части основных задач числа туда помещались, с другой стороны были наиболее короткими. Например, можно выбрать длину в 10 цифр для "обычных" чисел и длину 20 для "длинных" (операций с длинными целыми числами за один такт процессора будет выполняться меньше). Кстати, нам потребуется хранить ещё и знак числа. Как лучше всего это сделать — вопрос очень хороший.

В реальности используется несколько подходов к хранению знака числа, вернее даже к хранению просто целых чисел. Самый "популярный" в данный момент называется "дополнение до двойки" (two’s complement), что для нашего воображаемого десятичного процессора превращается в "дополнение до десятки". Основная идея подхода состоит в следующем. Так как наши числа ограничены 10-ю цифрами, то если в результате арифметической операции возникнет перенос через разряд в 11-ю цифру, то он будет потерян. В таких случаях говорят, что вычисления производятся по модулю $10^{10}$. Пусть у нас есть два числа: отрицательное $x$ и положительное $y$, и нам нужно вычислить $x+y$. Заметим, что по замечанию выше $x+y\equiv (10^{10}+x) + y$ (ведь добавление лишнего $10^{10}$ ничего не меняет, у нас нет "места", чтобы хранить эту цифру). Но число $(10^{10}+x)$ уже заведомо положительное.

Итак, ровно в этом состоит идея: для хранения отрицательного числа $x$ используется положительное число $(10^{10}+x)$. Неотрицательные числа от 0000000000 до 4999999999 хранятся как есть. А числа от 5000000000 до 9999999999 отдаются отрицательным числам, причём $-1$ превращается в $10^{10}-1 = 9999999999$, $-2$ превращается в $10^{10}-2 = 9999999998$, и так далее, $-5000000000$ превращается в... в $-5000000000$. Заметим, что отрицательных чисел "поместилось" на одно больше, чем положительных.

Вот примеры: сложим $8\,512$ и $-3\,628$. $$10^{10}-3628 = 9\,999\,996\,372.$$ Далее $$8\,512 + (-3\,628) \equiv 8\,512 + 9\,999\,996\,372 = 10\,000\,004\,884 \equiv 4\,884.$$
Сложим $-6\,460$ и $-9\,290$. $$(-6\,460) + (-9\,290) \equiv (10^{10}-6\,460) + (10^{10}-9\,290) = 9\,999\,993\,540 + 9\,999\,990\,710 = $$ $$= 19\,999\,984\,250 \equiv 9\,999\,984\,250 \equiv 9\,999\,984\,250 - 10^{10} = (-15\,750).$$

В чём выгода такого подхода? Во-первых, используются все возможные значения (если знак хранить в первой цифре, то будут "потеряны" 80% чисел). Во-вторых, с таким подходом отрицательные числа ничем не отличаются от положительных и не требуется усложнения схем для организации арифметических операций с ними. По модулю $10^{10}$ отлично работают все арифметические операции, поэтому работать будут и вычитание, и умножение.

В реальных чипах используется двоичная система счисления, но в остальном всё устроенно именно так. Один бит — это двоичная цифра. И существуют числа разной длины — в 8, 16, 32 и 64 двоичных цифры. Это зависит от реальных чипов.

Битовое представление целых чисел и битовые операции

Итак, переменные типа int хранятся в двоичной системе счисления в виде последовательности двоичных цифр — бит. Биты нумеруются от 0, биты будем записывать справа налево (то есть бит с номером 0 будет записан самым правым, а самый старший бит — самым левым). 

a = 0   # 0b0
a = 1   # 0b1
a = 2   # 0b10
a = 10  # 0b1010
a = 255 # 0b11111111

Например, если a = 10, то в битовой записи a биты с номерами 1 и 3 равны 1, а остальные биты равны 0.

В программах на языке Питон числа в двоичной системе счисления можно записывать в виде последовательностей из 0 и 1, предваряя их префиксом 0b. Например, допустимо присваивание a = 0b101.

Для двух переменных одинакового скалярного типа определены битовые операции:
& битовое И (AND)
| битовое ИЛИ (OR)
^ битовое ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)
~ битовое ОТРИЦАНИЕ (NOT) — унарная операция.

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

a = 5     # 0b101
b = 6     # 0b110

c = a & b # 0b100 == 4
d = a | b # 0b111 == 7
e = a ^ b # 0b11 == 3
f =  ~ a  # 0b1...11111010 == -6

Битовое отрицание числа (величина f в последнем примере) — это число, полученное из исходного заменой всех нулей на единицы и наоборот.

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

Есть еще две операции, работающие с битами: это битовые сдвиги. Их два: сдвиг влево и вправо. Оператор a >> n возвращает число, которое получается из a сдвигом всех бит на n позиций вправо, при этом самые правые n бит отбрасываются. Например: 

a = 43      # 0b101011
b = a >> 1  # 0b10101 == 21
c = a >> 2  # 0b1010 == 10
d = a >> 3  # 0b101 == 5
e = a >> 5  # 0b1 == 1

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

Аналогично, битовый сдвиг влево на n бит равносилен (для положительных чисел) умножению на 2n и осуществляется при помощи оператора <<: 

a = 5       # 0b101
b = a << 1  # 0b1010 == 10
c = a << 2  # 0b10100 == 20
d = a << 3  # 0b101000 == 40
Если необходимо применить битовую операцию к переменной и результат сохранить в ней же, то можно использовать стандартные конструкции 
n &= k
n |= k
n ^= k
n <<= k
n >>= k

Тонкости битового представления целых чисел в Python

Как вам уже известно, целые числа в питоне ограничены лишь объёмом оперативной памяти, то есть могут быть весьма и весьма большими. В этом случае можно представлять себе битовую запись целых чисел так. Если число положительно, то слева от записи числа идёт бесконечное количество 0. А если число отрицательно, то слева идёт бесконечное количество 1. Число -1 записывается как последовательность из одних лишь единиц: -1 = ...111, а число 0 — из одних лишь нулей 0 = ...000. То есть 21, это не просто 10101, а ...00010101. Таким образом, ~21 — это число вида ...11101010, то есть бесконечное количество 1, а затем 01010.

Как понять, какому целому числу соответствует такая запись? Если слева нули, то число положительно, и всё просто: отбрасываем ведущие нули, получаем число в двоичной записи. А если слева единицы? Для этого найдём самую правую 1, после которой слева идут только 1. В нашем примере получится вот такая единица: 100000. Очевидно, что в двоичной записи после такой единицы сразу идёт 0 (кроме случая, когда в двоичной записи вообще только 1, то есть кроме числа -1). Таким образом, число разбивается на бесконечную «голову» единиц ...11100000 и хвост после первого нуля (возможно пустой) — 1010. Итоговое число равно их разности: ...11101010 = 0b1010 - 0b100000 = -22.

Заметим, что для любого целого числа x сумма x + ~x — это бесконечная последовательность единиц. Это то самое число -1. То есть в питоне ~x = -1 - x.

Упражнения

Во всех упражнениях (если не оговорено иное) нельзя использовать арифметические операторы сложения, умножения, вычитания, деления, взятия остатка. Вместо них используем побитовые операторы &, |, ~, ^, <<, >>.

A: 2k

Дано число k, 0⩽k⩽31. Запишите число 2k, то есть число, у которого k-й бит равен 1, а остальные — нули.

8
256

B: 2k+2n

Даны два неравных целых неотрицательных числа: k и n. Вычислите 2k+2n.

0 1
3

C: Обнулить последние биты

Дано целое число A и целое неотрицательное число число k. Обнулите у числа A его последние k бит и выведите результат. Вычисления оформите в виде функции clear_lower_bits(A, k).

3 1
2

D: Установить бит

Дано целое число A и целое неотрицательное число k. Выведите число, которое получается из числа A установкой значения k-го бита равному 1. Вычисления оформите в виде функции set_bit(A, k).
12 1
14

E: Инвертировать бит

Дано целое число A и целое неотрицательное число k. Выведите число, которое получается из числа A инвертированием k-го бита. Вычисления оформите в виде функции toggle_bit(A, k).
15 2
11

F: Значение бита

Дано целое число A и целое неотрицательное число k. Выведите значение k-го бита числа A, то есть 0 или 1. Вычисления оформите в виде функции test_bit(A, k).
179 0
1

G: Обнулить бит

Дано целое число A и целое неотрицательное число k. Выведите число, которое получается из числа A установкой значения k-го бита равному 0. Вычисления оформите в виде функции clear_bit(A, k).
14 1
12

H: Обрезать старшие биты

Дано целое число A и натуральное число k. Выведите число, которое состоит только из k последних бит числа A (то есть обнулите все биты числа A, кроме последних k). Вычисления оформите в виде функции clear_high_bits(A, k).
126 3
6

I: Битовое представление

Дано неотрицательное целое число. Выведите его битовое представление.

В этой задаче можно использовать циклы, но нельзя использовать операции деления и умножения, а также любые операции со строками, кроме метода .join. Вычисления оформите в виде функции int2bin(n).

179
10110011

J: Битовая длина

Дано неотрицательное целое число. Выведите длину его битового представления.

В этой задаче можно использовать циклы, но нельзя использовать операции деления и умножения, а также любые операции со строками. Вычисления оформите в виде функции bit_length(n).

179
8
183765996899
38

K: Число единиц в битовой записи

Дано натуральное число. Выведите число единиц в его битовом представлении.

В этой задаче можно использовать циклы, но нельзя использовать операции деления и умножения, а также любые операции со строками. Вычисления оформите в виде функции bit_count(n).

179
5
183765996899
19

L: Число единиц в битовой записи — 2

Решите предыдущую задачу так, чтобы число повторений в цикле не превосходило число единиц в битовой записи числа.

M: Битовый обмен

В переменных x и y хранятся два целых числа. Необходимо обменять значения переменных местами, используя только битовые операции. Операции вида x, y = y, x, а также дополнительные переменные использовать запрещается. Вычисления оформите в виде функции swap_numbers(x, y).

9 17
17 9

N: Быстрое вычисление

Даны числа \(a\) и \(b\). Используя только битовые операции и операции сложения и вычитания вычислите число \(x = (18a + [\frac{b}{16}]) \bmod 32\). Выведите результат на экран.

1 2
18
2 16
5

O: Быстрое умножение

Даны числа \(a\) и \(b\). Не используя операции *, /, //, % вычислите их произведение.

2 3
6

P: Заменить 1 на 0

Дано число, замените первую справа единицу его двоичной записи на ноль.

Разрешается использовать битовые и арифметические операции. Запрещается использовать ветвления и циклы. Вычисления оформите в виде функции lowest_clear(n).

1
0
6
4

Q: Замените 0 на 1

Дано число, замените первый справа ноль его двоичной записи на единицу.

Разрешается использовать битовые и арифметические операции. Запрещается использовать ветвления и циклы. Вычисления оформите в виде функции lowest_set(n).

0
1
5
7

R: Шифрование перемешиванием

Дано число, переставьте его соседние биты (то есть поменяйте местами биты с номерами 0 и 1, 2 и 3, 4 и 5 и т.д.). Разрешается использовать битовые операции. Запрещается использовать арифметические операции, ветвления, циклы.

Общее число бит в числе не превосходит 32.

78
141

S: Из дополнительного кода

Поскольку в языке Питон встроенная целочисленная арифметика является длинной, то создается иллюзия того, что целые числа имеют бесконечное число разрядов. При этом у положительных чисел лидирующие разряды в двоичной системе счисления заполнены битом 0, а у отрицательных чисел — битом 1. Этот факт мы будем записывать следующим образом: символы «0~» будут обозначать бесконечное число нулевых бит, а символы «1~» бесконечное число единичных бит. То есть число 5 в дополнительном коде мы будем записывать, как 0~101. Для записи отрицательных чисел используется дополнение до двойки: пусть \(n\) — натуральное число, а число \(k\) минимальное из тех, для которых \(2^k \ge n\). Тогда для записи числа \(-n\) в дополнительном коде используется битовая запись числа \(2^k - n\) (с ведущими нулями), перед которой записано бесконечное число битов 1. То есть число -5 будет записываться как 1~011.

В такой записи бит, следующий после знака ~ должен отличаться от бита, идущего до него, то есть запись 0~0101 или 1~11011 считается неправильной. Исключениями являются числа 0 (записывается как 0~0) и -1 (записыватеся как 1~1).

Дана запись ненулевого числа в дополнительном коде, в соответствии с указанным выше форматом. Определите значение записанного числа.

Вычисления оформите в виде функции twos_complement2int(code).

0~101
5
1~011
-5

T: В дополнительный код

Решите задачу, обратную предыдущей.

Вычисления оформите в виде функции int2twos_complement(n).

5
0~101
-5
1~011

U: Кого потеряли

Дана последовательность из \(n\) натуральных чисел, в которой все числа, за исключением некоторого одного, повторяются два раза. Найдите это число. Время работы алгоритма должно быть \(O(n)\). Число \(n\) может быть порядка \(10^6\).

1 2 3 2 1
3
1 17 9 20 17 179 9 1 20
179

V: Кто лишний

Дана последовательность из \(n+1\) натурального числа от 1 до \(n\), ровно одно число повторяется дважды. Найдите это число. Время работы алгоритма должно быть \(O(n)\). Число \(n\) может быть порядка \(10^6\).

1 2 3 2
2
5 1 4 2 3 4
4

W: Контрольная сумма BSD

В операционной системе BSD используется следующий алгоритм вычисления контрольных сумм.

Контрольная сумма хранится в двубайтовой целочисленной переменной \(h\) (то есть хранятся только два байта числа, все вычисления выполняются в кольце вычетов по модулю \(2^{16}\). С самого начала эта переменная равна 0.

Далее с каждым считанным байтом \(c\) выполняются следующие операции.

Значение \(h\) циклически сдвигается вправо (то есть последний бит становится первым, не забываем, что число \(h\) является 16-битным. К значению \(h\) прибавляется значение считанного байта (то есть ASCII-кода его), от результата берется последние 16 бит.

Вот пример вычисления контрольной суммы для строки «AND« 

h = 0b0000000000000000 - начальная инициализация
h = 0b0000000000000000 - циклический сдвиг вправо
h = 0b0000000001000001 - добавили 65 - ASCII-код A
h = 0b1000000000100000 - циклический сдвиг вправо
h = 0b1000000001101110 - добавили 78 - ASCII-код N
h = 0b0100000000110111 - циклический сдвиг вправо
h = 0b0100000001111011 - добавили 68 - ASCII-код D

Результат равен 16507. Обратите внимание, что после сложения результат может оказаться более чем 16-битным, и требуется оставить только последние 16 бит.

Вычисления оформите в виде функции BSD(data).

AND
16507
Hello, world!
37288

X: Adler-32

В алгоритме Adler-32 вычисляются две 16-битные суммы: A — сумма всех байт входных данных и B — сумма всех промежуточных значений суммы A. При этом начальное значение A инициализируется числом 1, а начальное значение B — числом 0. Все вычисления проводятся по модулю 65521 (максимальное простое, меньшее \(2^{16}\)).

Таким образом, если файл состоит из байт \(d_1\), \(d_2\), ..., \(d_n\), то \(A = 1 + d_1 + d_2 + ... + d_n \bmod 65521\), \(B = (1 + d_1) + (1 + d_1 + d_2) + ... + (1 + d_1 + ... + d_n) \bmod 65521\).

Итоговым значением контрольной суммы является одно 32-битное число, в котором в старших 16 битах записано значение B, в младших 16 битах - значение A.

Вычислите контрольную сумму Adler-32 для данной строки.

Вычисления оформите в виде функции adler(data).

AND
27656404
Hello, world!
543032458

Y: FNV-1 хеш-функция

Алгоритм хеширования FNV-1 устроен следующим образом. Используется 64-битная арифметика. Переменная \(h\) хранит текущее значение хеш-функции. Начальное значение \(h\) равно 14695981039346656037. На каждом шаге значение \(h\) домножается на 1099511628211, затем делается побитовое исключающее ИЛИ с очередным байтом входных данных. Все вычисления проводятся с 64-битными целыми числами, поэтому после выполнения всех операций нужно брать младшие 64 бита результата.

Вычислите значение хеш-функции FNV-1 для данной строки.

Вычисления оформите в виде функции FNV(data).

AND
15595937027161525016
Hello, world!
7285062107457560934

Z: PJW-32 хеш-функция

Алгоритм хеширования PJW-32 устроен следующим образом. Используется 32-битная арифметика. Переменная \(h\) хранит текущее значение хеш-функции. Далее для каждого считанного байта \(с\) сообщения выполняются следующие операции:

1. Значение \(h\) сдвигается на 4 бита влево, к нему прибавляется (арифметическим суммированием) значение \(c\).

2. Если хотя бы один из 4 старших битов \(h\) равен 1, то старшие 4 бита сдвигаются на 24 бита вправо, и выполняется операция побитового исключающего ИЛИ со значением \(h\). После чего обнуляются старшие 4 бита значения \(h\).

Все операции проводятся с 32-битными числами, то есть берутся 32 младших бита результата.

Вычисления оформите в виде функции PJW(data).

AND
17956

ZA: Ханойские башни без рекурсии

Головоломка «Ханойские башни» состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из \(n\) дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.

Напишите программу, которая решает головоломку без использования рекурсии; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

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

Указание: попробуйте связать операцию, которую необходимо выполнить на шаге \(i\) с записью числа \(i\) в двоичной системе счисления.

Вычисления оформите в виде функции hanoi(n).

2
1 1 2 2 1 3 1 2 3

ZB: SHA-1

SHA-1 — алгоритм, вычисляющий криптографические контрольные суммы от произвольной битовой последовательности. Результатом вычисления функции SHA-1 является 160-битный хэш, который как правило записывается в виде 40 16-ричных цифр. Хэш-функция является односторонней, то есть по значению хэш-функции тяжело подобрать какую-либо исходную последовательность, имеющую такое значение хэш-функции.

Изучите описание алгоритма вычисления контрольной суммы SHA-1 по материалам википедии и реализуйте данный алгоритм.

Программа получает на вход одну строку и должна вывести значение SHA-1 суммы для этой строки. Исходная последовательность байт для вычисления SHA-1 суммы состоит только из символов этой строки, так в примере ниже входная строка имеет длину 3 байта = 24 бита. Добавлять к строке символ \n и иные спецсимволы не нужно.

Программа должна вывести 40 16-ричных цифр, цифры a-f записываются в строчном регистре.

da39a3ee5e6b4b0d3255bfef95601890afd80709
sha
d8f4590320e1343a915b6394170650a8f35d6926
Hello, world!
943a702d06f34599aee1f8da8ef9f7296031d699
.................................................................
e63aa2689b774a507aba9433e4a0c661586990a4

Обратите внимание, вам достаточно реализовать чуть более простой вариант SHA-1, который работает только в случае, когда исходное сообщение состоит из целого числа байт, в то время как спецификация SHA-1 описывает алгоритм, который получает на вход последовательность бит произвольной длины, не обязательно кратной 8.

Вычисления оформите в виде функции SHA(data).