любой-язык – 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.)

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.