Программирование на C++

Цель занятия: закрепить работу с битовыми масками, упаковкой данных и воспроизводимыми случайными экспериментами.

Необходимые темы и конструкции C++:

• беззнаковые целые типы и системы счисления
• побитовые операции &, |, ^, ~, <<, >>
• битовые маски и упаковка полей
• std::mt19937, std::uniform_int_distribution, фиксированный seed

• Код с самого начала на 100% покрыт тестами.
• Тесты выступают в роли актуальной документации к коду.
• Помогает лучше продумать интерфейс и архитектуру функции до ее реализации.
• Дает разработчику уверенность при внесении изменений в проект.

Структура проекта

Прежде, чем приступить к выполнению задания, скачайте файлы bit_tasks.h и bit_tasks.cpp и добавьте их в свой проект. Создайте файл main.cpp с функцией main(). Далее создайте тестовый проект и добавьте в него тесты из tests.cpp. Пишите задания так, чтобы ваш код проходил все тесты.

Общие требования

• Соблюдайте указанные сигнатуры функций: ввод и вывод организуйте в main.
• Не используйте средства, которые не перечислены в разделе необходимых тем, если условие прямо их не разрешает.

Основные задания

1. Операции над отдельным битом

   Реализовать чтение, установку, сброс и переключение бита беззнакового 32-битного числа. Биты нумеруются от младшего, начиная с нуля. Каждую из следующих четырёх задач следует решить не используя циклы и условные операторы. Допустимые операции: <<, >>, &, |, ^, ~

   Требуемая сигнатура:

   bool get_bit(std::uint32_t value, unsigned int position);
   std::uint32_t set_bit(std::uint32_t value, unsigned int position);
   std::uint32_t clear_bit(std::uint32_t value, unsigned int position);
   std::uint32_t toggle_bit(std::uint32_t value, unsigned int position);

   Требования:

   • Предусловие: position < 32.

   Входные данные / вызов	Результат
   set_bit(8, 1)	10
   toggle_bit(10, 3)	2

2. Упаковка цвета

   Упаковать компоненты красного, зелёного, синего и альфа-канала в число формата 0xRRGGBBAA, затем выполнить обратное извлечение компонентов.

   Требуемая сигнатура:

   std::uint32_t pack_rgba(std::uint8_t red, std::uint8_t green, std::uint8_t blue, std::uint8_t alpha);
   void unpack_rgba(std::uint32_t color, std::uint8_t& red, std::uint8_t& green, std::uint8_t& blue, std::uint8_t& alpha);

   Входные данные / вызов	Результат
   pack_rgba(255, 128, 0, 255)	0xFF8000FF

3. Сумма двух кубиков

   Выполнить \(n\) бросков двух честных шестигранных кубиков и оценить вероятность того, что сумма не меньше 10. Вернуть отношение числа успешных испытаний к общему числу испытаний.

   Требуемая сигнатура:

   double estimate_large_sum(std::mt19937& generator, int experiments);

   Требования:

   • Для тестов используйте фиксированный seed.
   • Предусловие: experiments >= 0.

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

1. Чётность числа единичных битов

   Вернуть 0, если число содержит чётное количество единичных битов, и 1 в противном случае.

   Требуемая сигнатура:

   unsigned int parity(std::uint64_t value);

   Требования:

   • Не используйте std::bitset и std::popcount.

   Входные данные / вызов	Результат
   parity(7)	1
   parity(15)	0

2. Сжатая дата

   Упаковать дату в 16 бит: 7 бит для номера года после 2000, 4 бита для месяца и 5 бит для дня. Реализовать распаковку.

   Требуемая сигнатура:

   std::uint16_t pack_date(const Date& date);
   Date unpack_date(std::uint16_t packed);

   Требования:

   • Допустимы годы 2000–2127.
   • До упаковки проверьте календарную корректность даты.

3. Оценка числа pi

   Методом Монте-Карло оценить число \(\pi\). Генерируйте точки равномерно в квадрате \([-1,1]\times[-1,1]\) и используйте формулу \(\pi\approx4\frac{m}{n}\), где \(m\) — число точек внутри единичного круга.

   Требуемая сигнатура:

   double estimate_pi(std::mt19937& generator, int experiments);

   Требования:

   • Сравните результаты для 100, 10 000 и 1 000 000 испытаний.