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

• Представление целого числа в виде линейки битов
  • char, short int, int, long int
• Операции побитового сдвига:

  • A<<n == A*2^n^

  • A>>n == A/2^n^

  • биты, вышедшие за границу типа, отбрасываются

• Побитовая конъюнкция & (И):

  A&B	0	1
  0	0	0
  1	0	1

  • A&(2ⁿ-1) == A%(2ⁿ)

• Побитовая дизъюнкция | (ИЛИ):

  A|B	0	1
  0	0	1
  1	1	1

• Побитовое отрицание ~ (НЕ):

  ~0 == 1

  ~1 == 0

  • A & ~A == 0

  • A | ~A == все единицы, или (для char) 2⁸-1

• Побитовое исключающее или ^ («не равно»)

  A^B	0	1
  0	0	1
  1	1	0

  • A^B^A == B

  • A^A == 0
  • Поменять местами значения A и B без использования третьей переменной:

    • A = A ^ B; B = A ^ B; A = A ^ B;

    • или, что то же самое, A ^= B; B ^= A; A ^= B;

• Представление целых отрицательных чисел:
  • Очевидно, один бит уходит на знак (0…255 → -128…127)

  • 12 == 00001100,,2,, ⇒ -14 == 10001100 — неудобно!

  • -12 = 0 - 14, то есть (для char)

      ·······
      00000000 == 0
      00001100 == 12
      ________
      11110010 == 242 == -12

    • При таком представлении действительно -12 + 14 == 2; -12 + 8 == -4 и т. п.

    • никакого «нового формата», просто появление 1 в 7-м бите
    • понятие «знаковый бит» сохраняется

    • «формула» -N == ~N+1 не столь очевидна

• Типы unsigned: unsigned short int и типы signed

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

0. Прочитать про побитовые операции в учебнике

1. Ввести целое число, вывести первые пять битов этого числа
   • в обратном порядке

     • Ввод: 25 (11001₂) Вывод: 10011

   • ИЛИ (посложнее) в правильном порядке

     • Ввод: 25 (11001₂) Вывод: 11001

   • Подсказка: если в строке формата printf() не указывать '\n', данные выводятся в одной строке непрерывно.

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

   • Пример: ввод: 46 (…00101110); вывод 53 (…00110101)

3. Используя только побитовые операции и операцию сложения
   • ввести число A, получить A*8
   • ввести число A, получить A*21

   • ввести число A и число B (в диапазоне 0…31), получить A*B