Печатать эту главуПечатать эту главу

§ 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, кроме младшего нулевого бита.