A: 2^k

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

B: 2^k+2ⁿ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

V: Кто лишний

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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