Хранение целых чисел на компьютере в десятичном мире
Для начала представим себе, что данные в компьютерах хранятся в ячейках-"битах", каждое из которых может принимать 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$.
Заметим, что отрицательных чисел "поместилось" на одно больше, чем положительных.
В чём выгода такого подхода? Во-первых, используются все возможные значения (если знак хранить в первой цифре, то будут "потеряны" 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
IDE
B: 2k+2n
Даны два неравных целых неотрицательных числа: k и n.
Вычислите 2k+2n.
0 1
3
IDE
C: Обнулить последние биты
Дано целое число A и целое неотрицательное число число k. Обнулите у числа A его последние k бит и выведите результат.
Вычисления оформите в виде функции clear_lower_bits(A, k).
3 1
2
IDE
D: Установить бит
Дано целое число A и целое неотрицательное число k.
Выведите число, которое получается из числа A установкой значения
k-го бита равному 1.
Вычисления оформите в виде функции set_bit(A, k).
12 1
14
IDE
E: Инвертировать бит
Дано целое число A и целое неотрицательное число k.
Выведите число, которое получается из числа A инвертированием
k-го бита.
Вычисления оформите в виде функции toggle_bit(A, k).
15 2
11
IDE
F: Значение бита
Дано целое число A и целое неотрицательное число k.
Выведите значение k-го бита числа A, то есть 0 или 1.
Вычисления оформите в виде функции test_bit(A, k).
179 0
1
IDE
G: Обнулить бит
Дано целое число A и целое неотрицательное число k.
Выведите число, которое получается из числа A установкой значения
k-го бита равному 0.
Вычисления оформите в виде функции clear_bit(A, k).
14 1
12
IDE
H: Обрезать старшие биты
Дано целое число A и натуральное число k.
Выведите число, которое состоит только из k последних бит числа A
(то есть обнулите все биты числа A, кроме последних k).
Вычисления оформите в виде функции clear_high_bits(A, k).
126 3
6
IDE
I: Битовое представление
Дано неотрицательное целое число. Выведите его битовое представление.
В этой задаче можно использовать циклы, но нельзя использовать операции
деления и умножения, а также любые операции со строками, кроме метода .join.
Вычисления оформите в виде функции int2bin(n).
179
10110011
IDE
J: Битовая длина
Дано неотрицательное целое число. Выведите длину его битового представления.
В этой задаче можно использовать циклы, но нельзя использовать операции
деления и умножения, а также любые операции со строками.
Вычисления оформите в виде функции bit_length(n).
179
8
183765996899
38
IDE
K: Число единиц в битовой записи
Дано натуральное число. Выведите число единиц в его битовом представлении.
В этой задаче можно использовать циклы, но нельзя использовать операции
деления и умножения, а также любые операции со строками.
Вычисления оформите в виде функции bit_count(n).
179
5
183765996899
19
IDE
L: Число единиц в битовой записи — 2
Решите предыдущую задачу так, чтобы число повторений в цикле не превосходило число единиц в битовой записи числа.
IDE
M: Битовый обмен
В переменных x и y хранятся два целых числа.
Необходимо обменять значения переменных местами, используя только битовые операции.
Операции вида x, y = y, x, а также дополнительные переменные использовать запрещается.
Вычисления оформите в виде функции swap_numbers(x, y).
9 17
17 9
IDE
N: Быстрое вычисление
Даны числа \(a\) и \(b\). Используя только битовые операции
и операции сложения и вычитания вычислите число
\(x = (18a + [\frac{b}{16}]) \bmod 32\). Выведите результат на экран.
1 2
18
2 16
5
IDE
O: Быстрое умножение
Даны числа \(a\) и \(b\). Не используя операции *, /, //, %
вычислите их произведение.
2 3
6
IDE
P: Заменить 1 на 0
Дано число, замените первую справа единицу его двоичной записи на ноль.
Разрешается использовать битовые и арифметические операции.
Запрещается использовать ветвления и циклы.
Вычисления оформите в виде функции lowest_clear(n).
1
0
6
4
IDE
Q: Замените 0 на 1
Дано число, замените первый справа ноль его двоичной записи на единицу.
Разрешается использовать битовые и арифметические операции.
Запрещается использовать ветвления и циклы.
Вычисления оформите в виде функции lowest_set(n).
0
1
5
7
IDE
R: Шифрование перемешиванием
Дано число, переставьте его соседние биты
(то есть поменяйте местами биты с номерами 0 и 1, 2 и 3, 4 и 5 и т.д.).
Разрешается использовать битовые операции. Запрещается использовать
арифметические операции, ветвления, циклы.
Общее число бит в числе не превосходит 32.
78
141
IDE
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
IDE
T: В дополнительный код
Решите задачу, обратную предыдущей.
Вычисления оформите в виде функции int2twos_complement(n).
5
0~101
-5
1~011
IDE
U: Кого потеряли
Дана последовательность из \(n\) натуральных чисел, в которой все числа, за исключением некоторого одного, повторяются два раза.
Найдите это число. Время работы алгоритма должно быть \(O(n)\).
Число \(n\) может быть порядка \(10^6\).
1 2 3 2 1
3
1 17 9 20 17 179 9 1 20
179
IDE
V: Кто лишний
Дана последовательность из \(n+1\) натурального числа от 1 до \(n\), ровно одно число повторяется дважды.
Найдите это число. Время работы алгоритма должно быть \(O(n)\).
Число \(n\) может быть порядка \(10^6\).
1 2 3 2
2
5 1 4 2 3 4
4
IDE
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
IDE
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
IDE
Y: FNV-1 хеш-функция
Алгоритм хеширования FNV-1 устроен следующим образом.
Используется 64-битная арифметика. Переменная \(h\)
хранит текущее значение хеш-функции. Начальное значение \(h\) равно
14695981039346656037. На каждом шаге значение \(h\) домножается на
1099511628211, затем делается побитовое исключающее ИЛИ с очередным
байтом входных данных. Все вычисления проводятся с 64-битными целыми
числами, поэтому после выполнения всех операций нужно брать младшие
64 бита результата.
Вычислите значение хеш-функции FNV-1 для данной строки.
Вычисления оформите в виде функции FNV(data).
AND
15595937027161525016
Hello, world!
7285062107457560934
IDE
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
IDE
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
IDE
ZB: SHA-1
SHA-1 — алгоритм, вычисляющий криптографические контрольные суммы
от произвольной битовой последовательности. Результатом вычисления функции
SHA-1 является 160-битный хэш, который как правило записывается в виде
40 16-ричных цифр. Хэш-функция является односторонней, то есть по значению
хэш-функции тяжело подобрать какую-либо исходную последовательность, имеющую
такое значение хэш-функции.
Изучите описание алгоритма вычисления контрольной суммы SHA-1 по
материалам википедии
и реализуйте данный алгоритм.
Программа получает на вход одну строку и должна вывести значение SHA-1 суммы
для этой строки. Исходная последовательность байт для вычисления SHA-1 суммы
состоит только из символов этой строки, так в примере ниже входная строка
имеет длину 3 байта = 24 бита. Добавлять к строке символ \n и иные спецсимволы не нужно.
Программа должна вывести 40 16-ричных цифр, цифры a-f
записываются в строчном регистре.
Обратите внимание, вам достаточно реализовать чуть более простой вариант
SHA-1, который работает только в случае, когда исходное сообщение состоит из целого
числа байт, в то время как спецификация SHA-1 описывает алгоритм, который получает
на вход последовательность бит произвольной длины, не обязательно кратной 8.