# Практика. Деление без деления ## Описание проекта Напишите функцию `divide()` в файле `div.cppm`. Она принимает два параметра `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`. Ожидаемое поведение функции: ```cpp 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`. Количество проделанных вычитаний и есть результат деления. Этот алгоритм легко реализовать. Но представьте, что вы делите большое число на маленькое. В цикле придётся сделать огромное количество вычитаний, прежде чем получится результат. Такой подход не оптимален: можно добиться сокращения количества итераций. И сделать это поможет [оператор побитового сдвига влево.](/courses/cpp/chapters/cpp_chapter_0023/#block-bitwise) `<<`. ### Реализация функции через побитовый сдвиг При наивной реализации алгоритма деления мы в цикле уменьшали значение `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`. Этого легко добиться с помощью побитового сдвига литерала. Не забудьте про [суффикс](/courses/cpp/chapters/cpp_chapter_0023/#block-suffix-uz) `uz`! Если у вас возникнут проблемы при выполнении практики, воспользуйтесь подсказкой. Она доступна по кнопке со знаком вопроса.