Conversion of a 40 bit binary number to decimal using 32 bit numbers

algorithms

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)?

Best Answer

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.

Related Question