Побитовые операции (практика)

• Разбор домашнего задания за прошлый раз
  • Все переменные целочисленные
  • Решается с использованием только побитовых операций
• План решения задания 2:

  • Ввести целое число в диапазоне 0…2⁶-1. Поменять местами в этом числе две тройки битов (то есть переставить биты 0,1,2 с битами 4,5,6, нумерация начинается справа).

    • Пример: ввод: 46 (…00101110); вывод 53 (…00110101)
  • Из введённого числа выделить первые три бита с помощью числа …0111 (7) и сдвинуть на 3 влево
  • Из введённого числа выделить следующие три бита с помощью …0111000 (56) и сдвинуть на 3 вправо

  • (этот шаг нужен, только если число превышает диапазон 0…2⁶-1) Из введённого числа вырезать первые 6 битов, остальные оставить (для типа short int это будет 1111111111000000₂ == 65472, а для типа int — 11111111111111111111111111000000₂ == 4294967232)

  • Объединить все полученные на предыдущих шагах значения с помощью побитовой дизъюнкции
• План решения задания 3

  • Используя только побитовые операции и операцию сложения (1) ввести число A, получить A*8; (2) ввести число A, получить A*21; (3) ввести число A и число B (в диапазоне 0…31), получить A*B

  • Решение 3.1 очевидно

  • Решение 3.2: 21 — это 2⁴+2²+2⁰

    • ⇒ A*21 = A*(2⁴+2²+2⁰), раскрываем скобки и заменяем умножение на степень двойки сдвигом

  • Решение 3.3:

    • составим формулу для всех пяти битов числа B (назовём их B₀ … B₄)

    • A*B = A*(2⁴*B₄+2³*B₃+2²*B₂+2¹*B₁+2⁰*B₀)

    • раскрываем скобки и заменяем умножение на степень двойки сдвигом

    • что делать с …*B_k?

      • можно так оставить: в конце концов, умножение на 0 и на 1 — это не умножение в действительности

      • наша задача — сделать из чисел A*2^k И B_k

        • 0, если B_k == 0

        • A*2^k (то же самое, что и было), если B_k == 1

        • Подсказка: B_k — это либо …00000000, либо …00000001.

          • А чему равно -B_k?

Домашнее задание

Дорешать задачи 2 и 3.