Переменные типа 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 равносилен целочисленному делению на 2ⁿ. Для отрицательных чисел в языке Питон операции битового сдвига неприменимы.

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

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

Упражнения

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

01: 2^k

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

8

256

02: 2^k+2ⁿ

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

0 1

3

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

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

3 1

2

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

12 1

14

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

15 2

11

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

179 0

1

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

14 1

12

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

126 3

6

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

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

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

179

10110011

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

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

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

179

8

183765996899

38

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

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

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

179

5

183765996899

19

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

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

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

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

9 17

17 9

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

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

1 2

18

2 16

5

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

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

2 3

6

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

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

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

1

0

6

4

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

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

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

0

1

5

7

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

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

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

78

141

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

Поскольку в языке Питон встроенная целочисленная арифметика является длинной, то создается иллюзия того, что целые числа имеют бесконечное число разрядов. При этом у положительных чисел лидирующие разряды в двоичной системе счисления заполнены битом 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

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

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

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

5

0~101

-5

1~011

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

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

1 2 3 2 1

3

1 17 9 20 17 179 9 1 20

179

22: Кто лишний

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

1 2 3 2

2

5 1 4 2 3 4

4

23: Контрольная сумма 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

24: 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

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

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

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

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

AND

15595937027161525016

Hello, world!

7285062107457560934

26: 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

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

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 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

28: 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).