§ 27. Битовые операции в языке программирования
Упражнения
1. Даны два натуральных числа a и b. Составить программу, реализующую для этих чисел битовую операцию по модулю два.
2. Вычислите xor всех чисел на отрезке [a, b].
3. Реализуйте программы из примера 27.16. Протестируйте для различных входных данных.
4. Дано число n. Используя битовые операции, замените единицу в младшем разряде двоичной записи числа n на ноль.
5. Даны два натуральных числа a и n. Найдите такое минимальное натуральное число b, что a xor b нацело делится на n.
6. Даны натуральные числа а и k. Выведите число, которое состоит только из k последних бит числа а (то есть, используя битовые операции, обнулите все биты числа а, кроме последних k).
7. Даны натуральные числа n и k. Используя битовые операции, обнулите в числе n его последние k бит и выведите результат.
8. Значением функции Фенвика для числа n называется максимальная степень двойки, на которую нацело делится число n. По заданному числу n определите для него значение функции Фенвика.
9. Дано натуральное число. Определите, сколько раз встречаются две подряд идущие единицы (11) в двоичном представлении этого числа (в двоичном представлении 11110111 оно встречается 5 раз).
10. Дано натуральное десятичное число n. Поменяйте местами два бита с заданными номерами в двоичном представлении этого числа. Например, если n = 5 и требуется поменять биты с номерами 1 и 2, то ответом будет 3.
11. Дано натуральное десятичное число n. Вычеркните i-й бит из двоичного представления этого числа (младшие i-го биты остаются на месте, старшие сдвигаются на один разряд вправо). Например, если n10 = 29 (n2 = 111012) и i = 1, ответом будет 1510 (11112).
12. Даны три натуральные числа. Найдите новое число, каждый бит которого равен тому значению, которое встречается чаще среди битов с таким же номером у данных чисел.
13. Для настольной игры используются карточки с номерами от 1 до n (натуральное число n не превышает 106). Одна карточка потерялась. Составьте программу ее поиска. Задано: число n и n - 1 номеров оставшихся карточек.
14. Дома у Ксюши было 2 одинаковых набора кубиков из английских букв, но во время очередной уборки один из кубиков затерялся. Помогите Ксюше определить, какой из кубиков отсутствует в одном из наборов.
15. Дано натуральное десятичное число n. Образуются все возможные левые циклические сдвиги двоичного представления числа n, у которых первая цифра числа переносится в конец.
Например, если n = 1110 (10112), то его циклические сдвиги: 01112, 11102, 11012, 10112. Максимальное значение m у всех полученных таким образом чисел будет иметь число 11102 = 1410.
Составьте программу, которая для заданного числа n определяет максимальное значение m.
16. Дано натуральное число n. С этим числом разрешено неограниченное количество раз проводить перестановку значащих бит заданного числа, получая таким образом новые числа. Найдите наибольшую разность двух чисел, каждое из которых можно получить в результате выполнений таких перестановок.
17. Дано натуральное число a. Напишите выражение, результатом которого является значение данного числа, у которого младший нулевой бит установлен в 1.
18. Дано натуральное число a. Напишите выражение, результатом которого является преобразование данного числа в число, у которого все биты установлены в 1, кроме младшего нулевого бита.