Битовые операции

Упражнения

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

A: 2k

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

Ввод Вывод
8
256

B: 2k+2n

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

Ввод Вывод
0 1
3

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

Дано целое число \(A\) и целое неотрицательное число число \(k\). Обнулите у числа \(A\) его последние \(k\) бит и выведите результат.

Ввод Вывод
3 1
2

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

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

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

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

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

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

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

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

H: Вырезать бит

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

В решении можно использовать операции \(+1\) и \(-1\).

Ввод Вывод
21 2
9

I: Сменить регистр символа

Программа получает на вход символ, являющийся заглавной или строчной буквой латинского алфавита. Используя битовые операции с ASCII-кодом символа, поменяйте регистр этого символа.

Ввод Вывод
A
a
a
A

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

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

K: 2k+2n — 2

Даны два возможно равных целых неотрицательных числа: \(k\) и \(n\). Вычислите \(2^k+2^n\).

Ввод Вывод
0 1
3
1 1
4

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

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

Ввод Вывод
1 2
18
2 16
5

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

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

Разрешается использовать битовые и арифметические операции. Запрещается использовать ветвления и циклы.

Ввод Вывод
0
1
5
7

N: Точная степень двойки

Дано целое положительное число. Используя только битовые операции (не используя циклы и логарифмы) определите, является ли оно степенью двойки. Выведите YES или NO.

Ввод Вывод
4
YES
5
NO

O: Степень двойки в разложении

Дано целое положительное число. Не используя циклы и логарифмы определите, на какую максимальную степень двойки оно делится. Выведите данную степень двойки.

Ввод Вывод
12
4
1
1

P: Уникальное число

Программа получает на вход последовательность натуральных чисел неизвестной длины. В этой последовательности все числа встречаются ровно по два раза, кроме одного. Найдите это число.

Программа должна использовать \(O(1)\) памяти.

Ввод-вывод может быть как стандартным, так и файловым (input.txt/output.txt).

Ввод Вывод
83
19
19
179
83
179

Q: Лишнее число

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

Ввод-вывод может быть как стандартным, так и файловым (input.txt/output.txt).

Ввод Вывод
5
1
4
2
3
4
4

R: Обмен значений

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

Ввод Вывод
3
7
7 3

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

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

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

Ввод Вывод
78
141

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

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

Программа получает на вход строку из нескольких нулей и единиц длиной не меньше 2 и не больше 16. Разрядность кода определяется длиной строки.

Пример

Ввод Вывод
00000101
5
11111011
-5

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

Дано целое число \(А\) и целое \(n\). Выведите запись числа \(A\) в двоичном n-разрядном дополнительном коде.

Ограничения: \(2\le n \le 16\), \(-2^{n-1}\le A \le 2^{n-1}-1\). Программа должна вывести последовательность из \(n\) нулей и единиц.

Пример

Ввод Вывод
5
8
00000101
-5
8
11111011

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

В системе Linux можно проверить результат работы при помощи консольной команды sum:

$ echo -n "AND" | sum
Ввод Вывод
AND
16507

W: 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 для данной строки.

Online-калькулятор Adler-32 и других контрольных сумм

Ввод Вывод
AND
27656404

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

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

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

Ввод Вывод
AND
15595937027161525016

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

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

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

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

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

Ввод Вывод
AND
17956

Z: МегаXOR

Даны два числа \(A\) и \(B\), \(1\le A\le B\le 10^{18}\). Вычислите \(A\oplus (A + 1)\oplus (A + 2)\oplus ... \oplus B\).

Ввод Вывод
3
6
4

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\) в двоичной системе счисления.

Ввод Вывод
2
1 1 2
2 1 3
1 2 3

ZB: Криптоанализ Adler-32

По данной контрольной сумме Adler-32, восстановите файл, имеющий такую контрольную сумму.

Программа получает на вход значение контрольной суммы Adler-32, в виде 32-битного беззнакового целого числа.

Программа должна иметь текст, контрольная сумма которого совпадает с данным. Текст должен состоять из неуправляющих непробельных ASCII-символов, то есть каждый символ должен иметь код от 33 до 126. Допускается наличие символа конца строки в конце текста.

Ввод Вывод
27656404
AND

ZZZ: SHA-1

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

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

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

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

Ввод Вывод
sha
d8f4590320e1343a915b6394170650a8f35d6926

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

Для тестирования можно использовать стандартную команду sha1sum из дистрибутива Linux. Например, ответ на тест из условия получен при помощи команды echo -n "sha" | sha1sum.