# Практика. Деление без деления ## Описание проекта Напишите функцию `divide()` в файле `div.h`. Она принимает два параметра `a` и `b` типа `std::size_t`. Функция должна вернуть результат целочисленного деления `a` и `b`. В решении нельзя применять операторы деления `/`, умножения `*` и получения остатка `%`. Вместо них используйте побитовый сдвиг `<<`. О нем вы узнаете ниже в разделе «Теория». Если `b` равен нулю, функция должна вернуть максимальное для типа `std::size_t` значение: `std::numeric_limits<std::size_t>::max()`. Что означает эта запись, вы узнаете уже в следующей главе. Значения `a` и `b` находятся в диапазоне от 0 до `std::numeric_limits<std::size_t>::max() - 1`. Ожидаемое поведение функции: ```c++ divide(6, 3); // 2 divide(3, 2); // 1 divide(7, 8); // 0 divide(1, 0); // std::numeric_limits<std::size_t>::max() ``` ## Тестирование По кнопке **«Запустить»** компилируется и запускается `main.cpp`. Внутри `main()` вы можете дописать свои варианты вызова `divide()` и проверить, как функция себя ведет на различных входных данных. По кнопке **«Отправить на проверку»** выполняются юнит-тесты из файла `tests.cpp`. Запустите их, когда функция `divide()` будет готова к тестированию. В `tests.cpp` можно посмотреть ожидаемые значения функции для набора входных данных. Проект будет засчитан как выполненный после успешного прохождения юнит-тестов. ## Теория ### Наивная реализация функции Что такое целочисленное деление числа `a` на число `b`? По сути это вычитание `b` из `a` до тех пор, пока `a` не станет меньше `b`. Количество проделанных вычитаний и есть результат деления. Этот алгоритм легко реализовать. Но представьте, что вы делите большое число на маленькое. В цикле придется сделать огромное количество вычитаний, прежде чем получится результат. Такой подход не оптимален: можно добиться сокращения количества итераций. И сделать это поможет оператор побитового сдвига. ### Бинарное представление чисел Каждое число в памяти представлено в виде последовательности бит. Например, 5 в бинарном виде — это `0b101`, 10 — это `0b1010`, а 7 — `0b111`. Префикс `0b` в C++ используется для записи значений в двоичной системе счисления. Если вы плохо с ней знакомы, самое время [восполнить знания.]( https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F) Сколько именно бит в памяти занимает число? Это зависит от типа числа и целевой платформы, под которую компилируется код. Например, под значения типа `std::size_t` _чаще всего_ выделяется 4 байта на 32-битных системах и 8 байт на 64-битных. Так выглядит в памяти число 3 типа `std::size_t`, занимающее 4 байта: ``` 00000000 00000000 00000000 00000011 ``` ### Побитовый сдвиг Побитовые операторы (bitwise operators) используются для манипуляции над отдельными битами значений. Они применимы только к целым числам. Нас интересуют два побитовых оператора: `<<` — сдвиг влево и `>>` — сдвиг вправо. Оператор `<<` — это **побитовый сдвиг влево.** Запись вида `x << n` означает, что каждый бит числа `x` сдвигается влево на `n` бит. Освобождающиеся биты заполняются нулями. Например, если число 3 сдвинуть на 2 бита влево, мы получим 12: ```c++ 3 << 2 // 12 ``` Чтобы понять, откуда берется 12, взглянем на число 3 в двоичном виде: ``` 00000000 00000000 00000000 00000011 ``` Сдвиг `0b11` на 2 бита влево приводит к тому, что биты числа смещаются в сторону старших разрядов, а на их место устанавливаются нули: `0b1100`. ``` 00000000 00000000 00000000 00001100 ``` Это и есть 12 в десятичной системе счисления. Сдвиг числа на один бит влево аналогичен умножению на 2: ```c++ x << 1 == x * 2 ``` Обобщим. Сдвиг числа на `n` бит влево аналогичен умножению на 2 `n` раз, то есть умножению на 2 в степени `n`: `2 ^ n`. Примеры: ```c++ 4 << 3 // 32 1 << 4 // 16 ``` Оператор `>>` — это **побитовый сдвиг вправо.** Запись `x >> n` означает, что биты числа `x` сдвигаются на `n` бит вправо. Для беззнаковых целых, таких как `std::size_t`, освобождающиеся биты заполняются нулями. Для знаковых целых, таких как `int`, поведение определяется реализацией в компиляторе (implementation-defined). Как можно догадаться, операция сдвига вправо обратна сдвигу влево. И она аналогична целочисленному делению на `2 ^ n`: ```c++ 9 >> 1 // 4 21 >> 2 // 5 ``` Приоритет операторов побитового сдвига ниже, чем у сложения `+` и вычитания `-`. Но выше, чем у операторов сравнения `<`, `>`. Таблицу с приоритетом всех операторов вы можете [посмотреть на cppreference.](https://en.cppreference.com/w/cpp/language/operator_precedence) Для побитовых сдвигов существуют операторы [составного присваивания](/courses/cpp/chapters/cpp_chapter_0020#block-compound-assignment) `<<=` и `>>=`: ```c++ x <<= n; // эквивалентно x = x << n; x >>= n; // эквивалентно x = x >> n; ``` Напоследок рассмотрим два нюанса работы со сдвигами. Их знание пригодится вам для выполнения проекта. ### Отбрасывание битов при сдвиге При побитовом сдвиге влево лишние биты **отбрасываются.** Допустим, у нас есть большое число: ``` 01101000 00000000 00000000 00000000 ``` Если мы сдвинем его на 1 бит влево, оно увеличится: ``` 11010000 00000000 00000000 00000000 ``` Но при дальнейшем сдвиге влево старшие разряды потеряются. Они вытеснятся за границы диапазона числа. И вместо того чтобы расти, число наоборот уменьшится: ``` 10100000 00000000 00000000 00000000 ``` Если применить к получившемуся числу сдвиг влево еще на 3 бита, число превратится в 0. ### Побитовый сдвиг литералов По умолчанию целочисленные литералы имеют тип `int`. И такая запись означает сдвиг значения типа `int` на `n` бит влево: ``` 5 << n ``` Однако у типов `int` и `std::size_t` разный диапазон значений. Побитовый сдвиг `int` на слишком большое значение, адекватное для `std::size_t`, приведет к ошибке в вычислениях. Если вы хотите применить сдвиг именно к значению `std::size_t`, воспользуйтесь суффиксом `uz`: ``` 5uz << n ``` [Суффикс uz](https://en.cppreference.com/w/cpp/language/integer_literal) был добавлен в C++23. Он означает, что у литерала тип `std::size_t`. Сравните результаты сдвига на 30 бит влево для значений типа `int` и `std::size_t`: ```c++ 3 << 30 // -1073741824 3uz << 30 // 3221225472 ``` В следующих главах вы узнаете причину, по которой значение типа `int` при побитовом сдвиге влево стало отрицательным. А пока просто запомните описанные особенности работы с побитовыми сдвигами. ### Реализация функции через побитовый сдвиг При наивной реализации алгоритма деления мы в цикле уменьшали значение `a` на `b` до тех пор, пока `a` не станет меньше `b`. Теперь мы знаем про побитовый сдвиг и можем драматически сократить количество итераций цикла! Для этого нужно уменьшать `a` на значение `b`, домноженное на `2 ^ n`. Но чему должно быть равно `n`? Его нужно вычислять на каждой итерации цикла. Оно подбирается таким образом, чтобы не нарушались условия: А) `a >= b * 2 ^ n`. Б) Сдвиг `b` на `2 ^ n` не приводит к отбрасыванию бит. То есть `b * 2 ^ n` умещается в диапазон значений `std::size_t`. Только при соблюдении этих двух условий `b * 2 ^ n` можно вычесть из `a`. Помимо уменьшения `a` следует увеличивать счетчик количества вычитаний `b` из `a`. Он и будет нашим результатом деления. Значение `a` на каждой итерации цикла уменьшается на `b * 2 ^ n`. Значит, счетчик должен увеличиваться на `2 ^ n`. Этого легко добиться с помощью побитового сдвига литерала. Не забудьте про суффикс `uz`! Если у вас возникнут проблемы при выполнении практики, воспользуйтесь подсказкой. Она доступна по кнопке со знаком вопроса.