2026/27, 10В, Python: Битовые операции (часть2)

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

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

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

0

1

5

7

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

4

YES

5

NO

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

12

4

1

1

Программа получает на вход последовательность неизвестной длины, состояющую из целых неотрицательных чисел, не превосходящих \(10^9\). В этой последовательности все числа встречаются ровно по два раза, кроме одного. Найдите это число.

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

В этой задаче ввод-вывод может быть как стандартным, так и файловым (input.txt, output.txt). Для чтения последовательности до конца ввода используйте конструкцию while (cin >> a).

83
19
19
179
83

179

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

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

5
1
4
2
3
4

4

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

3
7

7 3

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

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

78

141

Поскольку в языке Питон встроенная целочисленная арифметика является длинной, то создается иллюзия того, что целые числа имеют бесконечное число разрядов. При этом у положительных чисел лидирующие разряды в двоичной системе счисления заполнены битом 0, а у отрицательных чисел — битом 1. Этот факт мы будем записывать следующим образом: символы “0~” будут обозначать бесконечное число нулевых бит, а символы “1~” бесконечное число единичных бит. То есть число 5 в дополнительном коде мы будем записывать, как 0~101, а число -5 как 1~011.

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

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

0~101

5

1~011

-5

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

5

0~101

-5

1~011

В операционной системе 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

В алгоритме 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

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

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

AND

15595937027161525016

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

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

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

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

AND

17956

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

3
6

4

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

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

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

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

27656404

AND

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

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

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

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

sha

d8f4590320e1343a915b6394170650a8f35d6926