Conversion of a 40 bit binary number to decimal using 32 bit numbers I have a pin code calculation algorithm that returns a 40 bit number, let's call it N.
The pin code is the first 4 decimal digits of N. Examples:
If N = 0xABCDEF1234, the pin code is 7378
If N = 0x000523CD10, the pin code is 8623
If N = 0x0000000001, the pin code is 0001
Unfortunately I can only handle 32 bit numbers, so I need to split N into N1 and N2. For example:
N1 = 0xABCDEF12 and N2 = 0x00000034, or
N1 = 0x00ABCDEF and N2 = 0x00001234
Is there a way to retrieve the 4 digit pin from N1 and N2 without having to handle a number greater than 32 bits (i.e. 4,294,967,295)?
 A: You can emulate 40 bit unsigned arithmetic in terms of pairs of 20 bit unsigned integers (so there is enough room in 32 but integers to hardly have trouble with carries).
H = int represented by top 20 bits
L = int represented by low 20 bits
While H > 0 or L > 9999
    Integer divide by 10:
    L = L + ((H % 10) << 20)
    H = H / 10
    L = L / 10
Return L (with leading zeroes)

The key is that H % 10 fits into 4 bits, hence when shifted by 20 bits is still small enough.
A: The simplest way using only integer arithmetic is to first implement binary addition and subtraction, then implement integer division by $10,$ returning both the integer quotient and the remainder.
I’ll skip binary addition and subtraction.
We implement the remainder first. If the binary tor $n$ is $b_kb_{k-1}\dots b_0,$ then we do as follows:

*

*Set $p_0=1,$ $r_0=0.$

*For $i=0,\dots, k,$ $r_{i+1}=(r_i+p_ib_i)\bmod{10}, p_{i+1}=2p_i\bmod 10.$ That last step can be done with a lookup, since we are limited to $0\leq p_i<10.$ Also, since $b_i$ are either $0$ or $1,$ the computation of $p_{i+1}$ does not really require multiplication, just addition and a lookup of $m\bmod 10$ for some $0\leq m<20.$

*The value $r_{k+1}$ is the remainder $r.$
We could speed this up by handling multiple digits at a time.  For example , four digits at a time gives $p_0=1,$ $p_i=6$ for $i>0,$ and the lookup table will need to be a bit bigger to handle values of $0-15$ instead of binary digits.
Next, we want to compute $\frac{n-r}{10}.$ This can be done by computing:
$$\frac1{8\cdot 4^{k+2}}\sum_{2j\leq k+2} (-1)^j4^{k+2-j}(n-r)\tag1$$
Then take the nearest integer.
This works because $$\frac1{10}=\frac18\cdot \frac{1}{1+\frac14}=\frac18\sum_{j=0}^{\infty} \frac{(-1)^j}{4^j},$$ and, since we know that $(n-r)/10$ is an integer, we can compute the sum far enough to know we are within an integer of $(n-r)/10,$ and round.
We can compute $(1)$ using “simple” binary operations - addition, subtraction, and multiplication by powers of $2,$ followed by division by a power of $2.$ This will take $O(k^2)$ time, if addition two $k$-bit numbers takes $O(k)$ time. But really, since $k$ is bounded, we get $O(1)$ time.
The final algorithm is to recursively take the remainder and quotient. Start with $n_0=n,$ compute the quotient and remainder $n_{i+1}$ and $r_i,$ until you get to $n_{m}=0.$ Then the last four remainders are your four digits. If there are fewer than four remainders, then pad on the left with zeros.
All together, this will take $O(k^3)$ time in the general case.
