Как поделить двоичное натуральное на 10 фиксированным количеством сдвигов, сложений и вычитаний?

#любой_язык

Умножение на 10 можно представить в виде

x * 10 = x * 8 + x * 2 = (x << 3) + (x << 1)


А можно ли каким-то подобным способом (сдвигами, сложениями и вычитаниями) делить
на 10? (Вычитание 10 из x до посинения - не подходит.)
    

Ответы

Ответ 1

Деление беззнаковых целых 32 и 64 разрядных на 10 с возвратом частного и получением
остатка.

// http://www.hackersdelight.org/divcMore.pdf
uint32_t divu10(uint32_t n, uint32_t *rem) {
  uint32_t q, r;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q >> 3;
  //  orig: r = n - q*10;
  r = n - ((q << 3) + (q << 1));
  *rem = r > 9 ? r - 10 : r;

  //  orig: return q + ((r + 6) >> 4);
  return q + (r > 9);
}


uint64_t divu64_10(uint64_t n, uint32_t *rem) {
  uint64_t q, r;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q + (q >> 32);
  q = q >> 3;
  //  orig: r = n - q*10;
  r = n - ((q << 3) + (q << 1));
  *rem = r > 9 ? r - 10 : r;

  //  orig: return q + ((r + 6) >> 4);
  return q + (r > 9);
}


Практически используется для вывода uint64_t на 32-bit микропроцессоре, в котором
нет 64-разрядного умножения.


Ответ 2

Давайте посмотрим, как оптимизируют деление на 10 популярные компиляторы. Например,
для вот такой функции:

int divide10(int32_t num)
{
    return num / 10;
}


MSVC производит такой код:

mov      eax, 1717986919      ; 66666667H
imul     ecx
sar      edx, 2

mov      eax, edx
shr      eax, 31
add      eax, edx


Переведём его на нормальный язык.

Первые 3 строчки означают умножение числа на 0x66666667 = (2^34 + 6)/10 (тут ^ означает
степень). Старшие 32 бита результата (edx) мы затем сдвигаем ещё на 2 бита вправо,
итого выходит (x * 0x66666667) >> 34.

Команда shr eax, 31 — сдвиг на 31 бит, получает знаковый бит результата. Он прибавляется
к самому результату. То есть, для отрицательных чисел прибавляется 1. Итого

int r = (int)((x * 0x66666667L) >> 34);
r += (r < 0);


GCC, Clang и Intel Compiler производят аналогичный код, только они делают знаковое
расширение вместо беззнакового.



Разбор математического обоснования такой замены проводится здесь. Вот краткая выжимка:

Для делимого n >= 0 можно представить n в виде 10 * q + r, где q — искомый результат,
а r — остаток. Получаем

(x * 0x66666667L) >> 34 == [(10 * q + r) * (0x66666667L) / 2^34]


(^ означает возведение в степень, [] — целую часть от деления). Наш числитель:

(2^34 + 6)/10 * (10 * q + r) = q * 2^34 + 6 * q + 0x66666667L * r


При делении на 2^34 первое слагаемое делится нацело и даёт искомое q, так что нужно
убедиться, что остальное даёт 0. Это так, поскольку q < [2^31/10], а r <= 9, так что

6 * q + 0x66666667L * r < 6 * 214748364 + 0x66666667L * 9 == 15676630635 < 2^34


Для отрицательных n аналогично доказывается, что «хвост» нашего выражения даёт нулевой
вклад, но т. к. при делении отрицательных чисел процессор должен делать округление
в сторону нуля, приходится добавлять компенсирующую единицу.



Как именно получать такое представление, лучше справится в книжках. Но мораль этого
такова: подобные мелкие оптимизации компиляторы делают куда лучше нас. Поэтому не нужно
пытаться «помочь» компилятору, он, поверьте, делает это (мелкие оптимизации кода) куда
лучше нас с вами.

Эпоха ручных оптимизаций прошла. Оптимизируйте алгоритмы.

Дополнительное чтение по теме: Matt Godbolt: Что мой компилятор сделал для меня?