Быстрый пол целочисленного деления со знаком в C / C++
В C может быть сделано разделение на пол, например:
int floor_div(int a, int b) {
int d = a / b;
if (a < 0 != b < 0) { /* negative output (check inputs since 'd' isn't floored) */
if (d * a != b) { /* avoid modulo, use multiply instead */
d -= 1; /* floor */
}
}
return d;
}
Но, похоже, это можно упростить.
Есть ли более эффективный способ сделать это в C?
Обратите внимание, что это почти противоположность этого вопроса: быстрый потолок целочисленного деления в C / C++
5 ответов
Этажное деление может быть выполнено с использованием деления и по модулю.
Нет причин избегать вызова по модулю, поскольку современные компиляторы оптимизируют разделение и деление по модулю.
int floor_div(int a, int b) {
int d = a / b;
int r = a % b; /* optimizes into single division. */
return r ? (d - ((a < 0) ^ (b < 0))) : d;
}
Я думаю, меньше инструкций по сборке в сгенерированном коде и более быстрый путь к результату.
Для машин RISC с огромным количеством регистров этот лучше, так как ветвей вообще нет, и это хорошо для конвейера и кеша.
Для x86 на самом деле это не имеет значения.
int floor_div3(int a, int b) {
int d = a / b;
return d * b == a ? d : d - ((a < 0) ^ (b < 0));
}
div() функции в стандарте C
Я думаю, вы должны посмотреть на div() функции от <stdlib.h>, (Они являются стандартными функциями C и определены во всех версиях стандарта, несмотря на ссылку на спецификацию POSIX.)
Стандарт C11 §7.22.6.2 определяет:
div… Функции вычисляютnumer / denomа такжеnumer % denomв одной операции.
Обратите внимание, что C11 определяет целочисленное деление в §6.5.5 (и C99 был похож):
Когда целые числа делятся, результат
/оператор - это алгебраический фактор, любая дробная часть которого отбрасывается. 105)105) Это часто называют "усечением до нуля".
но C90 (§6.3.5) был более гибким, но менее полезным:
Когда целые числа делятся и деление является неточным. если оба операнда положительны, результат
/оператор является наибольшим целым числом меньше, чем алгебраический фактор и результат%Оператор положительный. Если любой операнд отрицательный, является ли результат/оператор является наибольшим целым числом, меньшим или равным алгебраическому частному, или наименьшим целым числом, большим или равным алгебраическому частному, определяется реализацией, как и знак результата%оператор.
floor_div()
Вычислительный код для запрошенного floor_div() с помощью div() аккуратный и опрятный.
int floor_div(int a, int b)
{
assert(b != 0);
div_t r = div(a, b);
if (r.rem != 0 && ((a < 0) ^ (b < 0)))
r.quot--;
return r.quot;
}
Тестовый код
Форматирование печати в приведенном ниже коде довольно точно адаптировано к образцу данных. (Было бы лучше, но более обширно, чтобы использовать %4d а также %-4d на протяжении). Этот код печатает строки длиной 89 символов плюс перевод строки; более общий макет будет печатать строки длиной 109. Ни один из них не избегает горизонтальной полосы прокрутки на SO.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
static int floor_div(int a, int b)
{
assert(b != 0);
div_t r = div(a, b);
if (r.rem != 0 && ((a < 0) ^ (b < 0)))
r.quot--;
return r.quot;
}
static void test_floor_div(int n, int d)
{
assert(d != 0);
printf( "%3d/%-2d = %-3d (%3d)", +n, +d, floor_div(+n, +d), +n / +d);
printf("; %3d/%-3d = %-4d (%4d)", +n, -d, floor_div(+n, -d), +n / -d);
if (n != 0)
{
printf("; %4d/%-2d = %-4d (%4d)", -n, +d, floor_div(-n, +d), -n / +d);
printf("; %4d/%-3d = %-3d (%3d)", -n, -d, floor_div(-n, -d), -n / -d);
}
putchar('\n');
}
int main(void)
{
int numerators[] = { 0, 1, 2, 4, 9, 23, 291 };
enum { NUM_NUMERATORS = sizeof(numerators) / sizeof(numerators[0]) };
int denominators[] = { 1, 2, 3, 6, 17, 23 };
enum { NUM_DENOMINATORS = sizeof(denominators) / sizeof(denominators[0]) };
for (int i = 0; i < NUM_NUMERATORS; i++)
{
for (int j = 0; j < NUM_DENOMINATORS; j++)
test_floor_div(numerators[i], denominators[j]);
putchar('\n');
}
return 0;
}
Тестовый вывод
0/1 = 0 ( 0); 0/-1 = 0 ( 0)
0/2 = 0 ( 0); 0/-2 = 0 ( 0)
0/3 = 0 ( 0); 0/-3 = 0 ( 0)
0/6 = 0 ( 0); 0/-6 = 0 ( 0)
0/17 = 0 ( 0); 0/-17 = 0 ( 0)
0/23 = 0 ( 0); 0/-23 = 0 ( 0)
1/1 = 1 ( 1); 1/-1 = -1 ( -1); -1/1 = -1 ( -1); -1/-1 = 1 ( 1)
1/2 = 0 ( 0); 1/-2 = -1 ( 0); -1/2 = -1 ( 0); -1/-2 = 0 ( 0)
1/3 = 0 ( 0); 1/-3 = -1 ( 0); -1/3 = -1 ( 0); -1/-3 = 0 ( 0)
1/6 = 0 ( 0); 1/-6 = -1 ( 0); -1/6 = -1 ( 0); -1/-6 = 0 ( 0)
1/17 = 0 ( 0); 1/-17 = -1 ( 0); -1/17 = -1 ( 0); -1/-17 = 0 ( 0)
1/23 = 0 ( 0); 1/-23 = -1 ( 0); -1/23 = -1 ( 0); -1/-23 = 0 ( 0)
2/1 = 2 ( 2); 2/-1 = -2 ( -2); -2/1 = -2 ( -2); -2/-1 = 2 ( 2)
2/2 = 1 ( 1); 2/-2 = -1 ( -1); -2/2 = -1 ( -1); -2/-2 = 1 ( 1)
2/3 = 0 ( 0); 2/-3 = -1 ( 0); -2/3 = -1 ( 0); -2/-3 = 0 ( 0)
2/6 = 0 ( 0); 2/-6 = -1 ( 0); -2/6 = -1 ( 0); -2/-6 = 0 ( 0)
2/17 = 0 ( 0); 2/-17 = -1 ( 0); -2/17 = -1 ( 0); -2/-17 = 0 ( 0)
2/23 = 0 ( 0); 2/-23 = -1 ( 0); -2/23 = -1 ( 0); -2/-23 = 0 ( 0)
4/1 = 4 ( 4); 4/-1 = -4 ( -4); -4/1 = -4 ( -4); -4/-1 = 4 ( 4)
4/2 = 2 ( 2); 4/-2 = -2 ( -2); -4/2 = -2 ( -2); -4/-2 = 2 ( 2)
4/3 = 1 ( 1); 4/-3 = -2 ( -1); -4/3 = -2 ( -1); -4/-3 = 1 ( 1)
4/6 = 0 ( 0); 4/-6 = -1 ( 0); -4/6 = -1 ( 0); -4/-6 = 0 ( 0)
4/17 = 0 ( 0); 4/-17 = -1 ( 0); -4/17 = -1 ( 0); -4/-17 = 0 ( 0)
4/23 = 0 ( 0); 4/-23 = -1 ( 0); -4/23 = -1 ( 0); -4/-23 = 0 ( 0)
9/1 = 9 ( 9); 9/-1 = -9 ( -9); -9/1 = -9 ( -9); -9/-1 = 9 ( 9)
9/2 = 4 ( 4); 9/-2 = -5 ( -4); -9/2 = -5 ( -4); -9/-2 = 4 ( 4)
9/3 = 3 ( 3); 9/-3 = -3 ( -3); -9/3 = -3 ( -3); -9/-3 = 3 ( 3)
9/6 = 1 ( 1); 9/-6 = -2 ( -1); -9/6 = -2 ( -1); -9/-6 = 1 ( 1)
9/17 = 0 ( 0); 9/-17 = -1 ( 0); -9/17 = -1 ( 0); -9/-17 = 0 ( 0)
9/23 = 0 ( 0); 9/-23 = -1 ( 0); -9/23 = -1 ( 0); -9/-23 = 0 ( 0)
23/1 = 23 ( 23); 23/-1 = -23 ( -23); -23/1 = -23 ( -23); -23/-1 = 23 ( 23)
23/2 = 11 ( 11); 23/-2 = -12 ( -11); -23/2 = -12 ( -11); -23/-2 = 11 ( 11)
23/3 = 7 ( 7); 23/-3 = -8 ( -7); -23/3 = -8 ( -7); -23/-3 = 7 ( 7)
23/6 = 3 ( 3); 23/-6 = -4 ( -3); -23/6 = -4 ( -3); -23/-6 = 3 ( 3)
23/17 = 1 ( 1); 23/-17 = -2 ( -1); -23/17 = -2 ( -1); -23/-17 = 1 ( 1)
23/23 = 1 ( 1); 23/-23 = -1 ( -1); -23/23 = -1 ( -1); -23/-23 = 1 ( 1)
291/1 = 291 (291); 291/-1 = -291 (-291); -291/1 = -291 (-291); -291/-1 = 291 (291)
291/2 = 145 (145); 291/-2 = -146 (-145); -291/2 = -146 (-145); -291/-2 = 145 (145)
291/3 = 97 ( 97); 291/-3 = -97 ( -97); -291/3 = -97 ( -97); -291/-3 = 97 ( 97)
291/6 = 48 ( 48); 291/-6 = -49 ( -48); -291/6 = -49 ( -48); -291/-6 = 48 ( 48)
291/17 = 17 ( 17); 291/-17 = -18 ( -17); -291/17 = -18 ( -17); -291/-17 = 17 ( 17)
291/23 = 12 ( 12); 291/-23 = -13 ( -12); -291/23 = -13 ( -12); -291/-23 = 12 ( 12)
Остаток от "деления по полу" либо равен 0, либо имеет тот же знак, что и делитель.
(the proof)
a: dividend b: divisor
q: quotient r: remainder
q = floor(a/b)
a = q * b + r
r = a - q * b = (a/b - q) * b
~~~~~~~~~
^ this factor in [0, 1)
И, к счастью, результат / а также % в C/C++ стандартизирован как "усеченный до нуля" после C99/C++11. (до этого библиотечная функция div в С и std::div в C++ играл те же роли).
Давайте сравним "деление по полу" и "усеченное деление", сосредоточив внимание на диапазоне остатка:
"floor" "truncate"
b>0 [0, b-1] [-b+1, b-1]
b<0 [b+1, 0] [b+1, -b-1]
Для удобства обсуждения:
- пусть a, b = дивиденд и делитель;
- пусть q, r = частное и остаток от "деления по полу";
- пусть q0, r0 = частное и остаток от "усеченного деления".
Предположим, что b>0, и, к сожалению, r0 находится в [-b+1, -1]. Однако мы можем получить r довольно легко: r = r0+b, и r гарантированно находится в [1, b-1], что находится внутри диапазона "floor". То же самое верно для случая b<0.
Теперь, когда мы можем исправить остаток, мы также можем исправить частное. Правило простое: мы добавляем b к r 0, затем мы должны вычесть 1 из q0.
В завершение, реализация "разделения пола" в C++11:
void floor_div(int& q, int& r, int a, int b)
{
int q0 = a / b;
int r0 = a % b;
if (b > 0){
q = r0 >= 0 ? q0 : q0 - 1;
r = r0 >= 0 ? r0 : r0 + b;
}
else {
q = r0 <= 0 ? q0 : q0 - 1;
r = r0 <= 0 ? r0 : r0 + b;
}
}
По сравнению со знаменитым (a < 0) ^ (b < 0) Метод, этот метод имеет преимущество: если делитель является константой времени компиляции, для исправления результатов требуется только одно сравнение.
Безответственная версия:
int floor_div(int x, int y)
{
return x / y - (x % y != 0) * ((x < 0) ^ (y < 0));
}
https://godbolt.org/z/9n3637brs
Я вижу, что для других ответов компилятор генерирует условные переходы, а это означает более медленный код.
Провел некоторые тесты производительности, и результаты интересны:
- для gcc моя функция незначительно быстрее
- for clang моя функция на 3-м месте на 10% медленнее, чем 2 и 3
Проверка кода, сгенерированного clang, показывает, что clang смог оптимизировать удаленные ветки (
Итак, это показывает: сначала измеряйте при оптимизации :).