# любой-язык – How to divide a binary integer by 10 by a fixed number of shifts, additions and subtractions?

## 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.)

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.

Scroll to Top