CodinGame | Chuck Norris | C++

Приветствую! А вы знаете, что такое #bitmask и #побитовые_операторы? Если нет, то самое время это исправить!

Описание задачи: Двоичное кодирование обычно осуществляется с помощью 0 и 1. Но что, если пользоваться одним лишь нулём? Именно Чак Норрис (но это не точно) разработал эту концепцию для отправки унарных сообщений. Так вот, Чак, конечно, крут, но программисты здесь — мы! Давайте напишем программу, которая на вход принимает сообщение-строку и кодирует его.

Принцип кодирования:

• Входное сообщение состоит из символов ASCII (7 бит);

• Закодированное сообщение состоит из групп пробелов;

• Группа отделяется от другой группы пробелом;

• Две последовательные группы используются для создания серии одинаковых битов: — Первая группа: это всегда 0 или 00. Если это 0, то серия содержит 1, если нет, она содержит 0; — Вторая группа: число 0 в этом блоке является количеством битов в серии.

Примеры: Рассмотрим простой пример с сообщением, состоящим только из одного символа: заглавная буква C. C в двоичном виде представлена ​​как 1000011 (см. ASCII table), поэтому при использовании метода Чака Норриса это дает:

• 0 0 (первая серия состоит только из одного 1);

• 00 0000 (вторая серия состоит из четырех 0);

• 0 00 (третья состоит из двух 1);

• Таким образом, C кодируется как: 0 0 00 0000 0 00.

Во втором примере мы хотим закодировать сообщение CC (то есть 14 битов 10000111000011):

• 0 0 (один 1);

• 00 0000 (четыре 0);

• 0 000 (три 1);

• 00 0000 (четыре 0);

• 0 00 (два 1).

Так что CC кодируется так: 0 0 00 0000 0 000 00 0000 0 00.

Входные данные: Строка: сообщение, состоящее из N символов ASCII (без символа возврата каретки).

Выходные данные: Закодированное сообщение (без символа возврата каретки). Chuck Norris решение на C++:

Для начала считаем входные данные. Что же делать? Очевидно, как-то обработать символы битовой цепочки. Во-первых, мы должны отслеживать смену бита, во-вторых, подсчитывать количество одинаковых битов идущих подряд.

Первый символ сообщения в данном контексте компилятор воспримет как целое десятичное число. Для того, чтобы определить первый бит этого числа, я применяю к нему и к двоичному числу 1000000 (40 в шестнадцатеричной системе счисления) побитовое «‎И». Бинарный оператор & в данном случае вернёт 1 или 0, которые затем преобразуются в логические true или false. Для вывода я использую тернарный оператор.

Что же делать теперь? Начнём перебор всех символов в сообщении. Для этого воспользуемся range-based циклом. Обязательно используем ссылку, чтобы не создавать копии объектов! Мы не собираемся изменять сами символы, поэтому используем константную ссылку.

Теперь пройдёмся по двоичному представлению ASCII-кода текущего символа. Предлагаю сделать это с помощью динамической bitmask. Для этого в for цикле после каждой итерации применим побитовый сдвиг вправо.

Шаг алгоритма следующий:

1. смотрим текущий бит;

2. если текущий бит и предыдущий бит совпадают, просто пишем "0";

3. иначе если не совпадают;

4. если текущий бит 1, выводим " 0 0";

5. иначе если текущий бит равен 0, выводим " 00 0";

6. запоминаем текущее значение бита.

Обратите внимание, что операция присваивания в качестве значения возвращает значение переменной справа! Это не опечатка!

Итоговый код:

Послесловие:

Порешать задачи по программированию можно на CodinGame. -- © Bezukh Vladimir, 2019