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

Умножение на 10 можно представить в виде
x * 10 = x * 8 + x * 2 = (x << 3) + (x << 1)
А можно ли каким-то подобным способом (сдвигами, сложениями и вычитаниями) делить на 10? (Вычитание 10 из x до посинения - не подходит.)

Ответ

Деление беззнаковых целых 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-разрядного умножения.