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

Упражнения

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

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

A: \(2^k\)

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

8

256

B: \(2^k+2^n\)

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

0 1

3

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

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

3 1

2

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

12 1

14

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

179 0

1

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

15 2

11

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

14 1

12

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

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

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

21 2

9

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

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

126 3

6

J: \(2^k+2^n\) — 2

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

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

0 1

3

1 1

4

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

Расскажем трюк, как заметить в битовом представлении числа \(a\) самую последнюю единицу на 0. Это делается при помощи операции a & (a - 1).

Теперь аналогичным способом замените в данном числе \(a\) самый правый ноль его двоичной записи на единицу.

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

0

1

5

7

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

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

4

YES

5

NO

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

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

12

4

1

1

N: Количество единиц в двоичном представлении

Дано целое положительное число \(a\). Определите число единиц в его двоичной записи.

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

179

5

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

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

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

Пример

00000101

5

11111011

-5

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

Дано целое число \(А\) и целое \(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

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

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

Программа получает на вход строку, состоящую только из заглавных и строчных латинских букв и должна вывести преобразованную строку.

Hello

hELLO

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

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

Программа должна использовать \(O(1)\) памяти. Любое использование списков или аналогичных контейнеров запрещено.

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

83
19
19
179
83

179

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

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

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

5
1
4
2
3
4

4

T: Максимальный XOR

Вам дано несколько чисел. Из них нужно выкинуть ровно одно число так, чтобы XOR оставшихся чисел был максимальным. Выведите значение получившегося XOR.

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

И в этой задаче размер памяти должен быть \(O(1)\), т.е. нельзя использовать списки и аналогичные контейнеры. Что же делать? Вероятно, вам поможет повторное открытие и считывание файла, в этой задаче разрешается так сделать.

57
179
2007

2030

Пояснение к примеру. Даны три числа: \(57\), \(179\), \(2007\). Выкинуть одно число можно тремя способами. \(57\oplus179=138\), \(57\oplus 2007=2030\), \(179\oplus 2007=1892\). Поэтому ответ будет \(2030\).

U: Шифрование при помощи XOR

Операция XOR является обратимой, например, \(a\oplus b\oplus b = a\), благодаря чему XOR часто используется в операциях с данными, таких как шифрование и вычисление контрольных сумм. Например, если \(a\) — исходное сообщение, а \(b\) — ключ шифрования, то сделав XOR сообщения и ключа можно получить зашифрованное сообщение (\(a\oplus b\)), а для расшифровки нужно выполнить XOR зашифрованного сообщения с ключом.

В этой задаче вам даны две строки: первая строка – сообщение, вторая строка — ключ. Для шифрования сообщения применяется операция XOR последовательно с символами (вернее, их кодами) сообщения и ключа — первый символ сообщения с первым символом ключа, второй символ сообщения со вторым символом ключа и т.д. Если длина ключа меньше длины сообщения, то ключ циклически повторяется.

Hello
123

yW_]]

В примере из условия первый символ ответа получается применением операции XOR к символам «H» и «1». Их коды равны 72 и 49, \(72\oplus49=121\), а 121 — это код буквы «y».

В ответе записан посимволный XOR сообщения «Hello» с повторением ключа «12312».

V: Шифрование сдвигом

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

Например, код символа «A» равен 65, что в двоичном виде (выровненном до 8 бит) есть 01000001. При циклическом сдвиге вправо на 3 получается значение 00101000, то есть число 40, которое есть код символа «(».

Дана строка, выполните операцию циклического сдвига вправо на 3 бита с каждым символом строки.

ABC

(Hh

W: МегаXOR

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

3
6

4

X: Псевдослучайные числа xorshift

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

Псевдослучайные последовательнсти используются в программах вместо случайных чисел (нельзя сгенерировать по-настоящему случайное число при помощи алгоритма, потому что алгоритм сам по себе не содержит ничего случайного). Псевдослучайные последовательности — это последовательности чисел, которые выглядят, как случайные, на самом деле вычисляются при помощи детерминированного алгоритма.

Обычно такие последовательности задаются при помощи функции, вычисляющей следующее псевдослучайное число, как функцию от предыдущего числа: \(x_{n+1}=f(x_n)\). Функция \(f\) должна быть максимально запутанной (и при этом иметь хорошие свойства, например, у неё должен быть большой период).

Рассмотрим довольно простой пример построения псевдослучайных чисел при помощи алгоритма Xorshift. В этом алгоритме с данным числом \(a\) выполняются последовательно следующие преобразования. Все вычисления проводятся в 32-битной арифметике, т.е. если результат всегда обрезается до 32 бит.

1. \(a\) сдвигается влево на 13 и делается XOR с числом \(a\).
2. Делается XOR результата предыдущего пункта с этим же числом, сдвинутым вправо на 17.
3. Делается XOR результата предыдущего пункта с этим же число, сдвинутым влево на 5.

Например, пусть начальное значение \(a\) равно 1, тогда будут выполнены следующие операции:

(a) 00000000 00000000 00000000 00000001

Сдвиг (a) влево на 13:
(b) 00000000 00000000 00100000 00000000
(c) = (a) ^ (b)
(c) 00000000 00000000 00100000 00000001

Сдвиг (c) вправо на 17
(d) 00000000 00000000 00000000 00000000
(e) = (c) ^ (d)
(e) 00000000 00000000 00100000 00000001

Сдвиг (e) влево на 5
(f) 00000000 00000100 00000000 00100000
(g) = (e) ^ (f)
(g) 00000000 00000100 00100000 00100001

Последнее число и будет результатом функции \(f\), в данном примере это 270369.

Последовательность, порождённая этим генератором, имеет период \(2^{32}-1\), то есть в этой последовательности циклически повторяются все 32-битные ненулевые числа.

Программа получает на вход два числа \(n\) и \(a\), и должна вывести \(n\) членов последовательности, порождённой начальным значением \(a\), то есть \(f(a)\), \(f(f(a))\), \(f(f(f(a)))\) и т.д.

1
5

270369
67634689
2647435461
307599695
2398689233

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

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

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-битного беззнакового 0целого числа.

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