Воплощение деления с неотрицательным остатком

Те, кто хотят использовать в программе предметное деление с остатком сталкиваются с тем, что во многих языках программирования деление сделано по-другому, что обусловлено воплощением в распространённых машинных языках. Если для обычного деления остаток всегда ≥ 0, то во многих Си-подобных языках остаток отрицательный для отрицательного делимого, которое не делится нацело.

Результаты деления

делимое	делитель	частное	остаток	/	%
5	3	1	2	1	2
-5	3	-2	1	-1	-2
-4	3	-2	2	-1	-1
-3	3	-1	0	-1	0

Я рассмотрю воплощение получения частного для положительного делителя.

Для положительного делимого всё просто, так как результаты совпадают.

int div(int n, int d) {
    assert(n >= 0);
    return n / d;
}

Для отрицательного делимого требуется корректировка. Можно догадаться, что если делимое увеличить по модулю на делитель без единицы, то это позволит получить искомый результат.

int div(int n, int d) {
    assert(n < 0);
    return (n - (d - 1)) / d;
}

Этот вариант плох тем, что допускает переполнение при вычитании из делимого. Его можно преобразовать, вынеся вычитание делителя за пределы деления

int div(int n, int d) {
    assert(n < 0);
    /* (n + 1 - d) / d */
    return (n + 1) / d - 1;
}

Если отрицательное делимое в языке нежелательно, например, из-за применения ISO C90, то нужно преобразовать выражение ещё раз

int div(int n, int d) {
    assert(n < 0);
    return -1 - (-1 - n) / d;
}

Этот вариант хорош и тем, что для чисел, кодируемых дополнительным кодом вычитание из -1 эквивалентно побитовому отрицанию.

int div(int n, int d) {
    assert(n < 0);
    return ~((~n) / d);
}

Нет большого смысла писать такой код напрямую в случае использования оптимизирующего компилятора, так как компилятор сам отлично преобразовывает вычитание в более эффективную инструкцию. Но этот код, если его, наконец, свести с делением положительного делимого, подталкивает к следующему изменению.

int div(int n, int d) {
    int r;
    if (0 <= n) {
        r =     n  / d;
    } else {
        r = ~((~n) / d);
    }
    return r;
}

Видно, что разница между ветками для неотрицательного и отрицательного делимого невелика, а, значит, можно попытаться свести их к единому выражению, исключив ветвление.

Известно, что для логического типа отрицание тождественно "исключительному или" с TRUE

NOT a = a XOR TRUE

А "исключительное или" с FALSE эквивалентно другому параметру в исходном виде

    a = a XOR FALSE

В побитовом выражении для 32-битных чисел, которые можно рассматривать как массивы логических значений, это эквивалентно

 ~a = a ^ 0xFFFFFFFF

  a = a ^ 0x00000000

Для сведения выражений достаточно ввести элемент, который равен 0 для неотрицательного делимого и -1 (все биты = 1, то есть 0xFFFFFFFF) для отрицательного. Такое поведение обеспечивается арифметическим побитовым сдвигом вправо на количество бит минус один.

int div(int n, int d) {
    int mask;
    mask = n >> 31;
    return mask ^ ((mask ^ n) / d);
}

Такой код верен для Java и для тех компиляторов Си, которые дают соответствующие гарантии насчёт размера int и представления отрицательных чисел. Как минимум, это работает с gcc, clang, tcc, CompCert. Для общего случая в Си он не подходит из-за стандарта, который отдаёт определение части семантики на откуп создателям компиляторов, а те, зачастую, опираются на поведение целевой платформы.

Для общего случая в Си следует ограничиться промежуточным вариантом, который в сведённом виде может выглядеть так:

int div(int n, int d) {
    int r;
    if (0 <= n) {
        r = n / d;
    } else {
        r = -1 - ((-1 - n) / d);
    }
    return r;
}

Схожим образом выводится функция вычисления остатка для Java и некоторых компиляторов C:

int mod(int n, int d) {
    int mask;
    mask = n >> 31;
    return (d & mask) + (mask ^ ((mask ^ n) % d));
}

Для общего случая:

int mod(int n, int d) {
    int r;
    if (0 <= n) {
        r = n % d;
    } else {
        r = d + (-1 - (-1 - n) % d);
    }
    return r;
}