Упражнения

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

Входное число A имеет тип unsigned int (если не оговорено иное). Номера битов всегда задаются корректно, то есть принимают значения от 0 до 31.

A: 2^k

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

8

256

B: 2^k+2ⁿ

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

0 1

3

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

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

3 1

2

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

12 1

14

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

15 2

11

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

179 0

1

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

14 1

12

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

126 3

6

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

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

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

83
19
19
179
83

179

J: Вывод байта

179

10110011

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

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

1 2

4

2 16

9

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

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

2 3

6

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

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

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

1

0

6

4

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

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

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

0

1

5

7

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

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

78

141

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

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

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

Пример

5
8

00000101

-5
8

11111011

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

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

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

Пример

00000101

5

11111011

-5

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

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

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

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

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

Вот пример вычисления контрольной суммы для строки “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.

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

$ echo -n "AND" | sum

AND

16507

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

AND

27656404

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

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

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

AND

15595937027161525016

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

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

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

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

AND

17956

Z: 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.