Question:
Multiplication by 10 can be represented as
x * 10 = x * 8 + x * 2 = (x << 3) + (x << 1)
Is it possible to divide by 10 in some similar way (by shifts, additions and subtractions)? (Subtracting 10 from x
until you're blue is not good.)
Answer:
Divide unsigned integers of 32 and 64 bits by 10, returning the quotient and getting the remainder.
// 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);
}
Practically used to output uint64_t
on a 32-bit microprocessor that does not have a 64-bit multiplication.