Remainder and Division of Binary Number when divided by 10

Question

Is there any algorithm for the following problems:

1. Remainder of a binary number when divided by 10

   (1010...0101) mod 10 = ?

2. Result of dividing a binary number by 10

   (1010...0101) div 10 = ?

I'm looking for algorithms with the smallest calculations possible, mainly working on the bit string, shifting it, removing or manipulating some of its bits.

Suppose the input is "1110110" which is "118" in decimal. What I'm trying to do is, I want to convert this bit string into a decimal string using this algorithm ::

B: Bit String
D: Decimal String
while (B is not empty) {
    Add character to beginning of D: MOD10(B)
    DEVIDEBY10(B)
}

I need the functions MOD10 and DEVIDEBY10 to make this algorithm work. Their argument is a bit string, not a numeric data type.

Answer 1

There is no much better way than... division and remainder.

q = n / d, r = n % d

Even though it is possible to efficiently compute the quotient and the remainder simultaneously, high-level programming languages do not offer this option. As division and remainder are costly operations, you can trade the latter for a multiply:

q = n / d, r = n - q * d

---

An alternative is to perform a multiply by 1/10, simulating fixed-point arithmetic.

Take a sufficiently large power of two to scale the numbers and let a:= 2^f/10. Then the quotient is approximated by

q = (a * n) >> f

Due to truncation, the value of q will be underestimated. You can adjust with an additive constant

q = (a * n + b) >> f

in such a way that the estimate is always exact.

Complete treatment depends on the range of values that you need to handle and is out of the scope of this answer.

Answer 2

For a binary string stored as a character string, the answer is trivial for division by 2: the remainder is the rightmost digit and the quotient is what you get after dropping the rightmost character. No arithmetic involved.