Convert binary number to any base

Conversion of binary to decimal numbers is often needed in firmware. And it’s done easily enough if multiplication and division by ten are acceptable. However, these operations, especially division, may be too resource-hungry for a low cost microcontroller (MCU).

I was therefore pleased to learn about the double dabble algorithm, which converts binary to decimal efficiently; it went into my bag of tricks immediately. Still, I want to tailor it to my needs – to work with any base. To do that, I needed to know how it actually works.

The double dabble belongs to the second of two groups of algorithms (shift-adjust and adjust-shift). Both can be used to convert binary numbers to other formats. Among them, conversion to the time or angle format of HMS is especially useful. Additionally, there have been ternary (base-3)-related designs & discussions on EDN recently to which this Design Idea is applicable.

The conversion begins with a binary number:

Partner Content

Telink Semiconductor Takes the Lead in Supporting Bluetooth® Channel Sounding   

11.19.2024

From Customer to Collaborator – How Nexperia and Synapticon’s Relationship Evolved

11.18.2024

Unlocking New Possibilities with Smart Sensors 

11.14.2024

   A = 2^{N –1} a_{N –1} + … + 2ⁿ a_n + … + 2 a ₁ + a ₀                    (1)

where a 's are bits. N bits are needed to store the number A . The a 's are either 0 or 1. An example number is 11011011₂ .

The number A is defined by a sum:

   A = B_M p_M + … + B_m p_m + … + B ₁ p ₁ + p₀                      (2)

The constants B_m depend on the numerical system. In decimal, these are products of base constants b as follows in (3). In the definition (2), the p 's correspond to decimal places.

b ₀ = 10                          B ₁ = b ₀ = 10
b ₁ = 10                          B ₂ = b ₁ B ₁ = 100
…
b_{m –1} = 10                      B_m = b_{m –1} B_{m –1} = 10^m                      (3)
…

The decimal system is not the only interesting system. For example, time, in base 60. Now, p ₀ , p ₁ , and p ₂ are seconds, minutes, and hours respectively.

b ₀ = 60                          B ₁ = b ₀ = 60
b ₁ = 60                          B ₂ = b ₁ B ₁ = 3600                             (4)

Except on mechanical clock dials, time is displayed by Arabic numerals that end at 9, which is far less than 59. Since it is not necessary that all b 's in the (2) be equal, the solution is simple. To write time with Arabic numerals, the next numerical system (5) is used. Places p ₀ and p ₁ together are seconds in the decimal system, p ₂ and p ₃ are minutes, and p ₄ shows hours.

b ₀ = 10                          B ₁ = b ₀ = 10
b ₁ = 6                            B ₂ = b ₁ B ₁ = 60
b ₂ = 10                          B ₃ = b ₂ B ₂ = 600
b ₃ = 6                            B ₄ = b ₃ B ₃ = 3600                              (5)

Another system’s constants could be b ₀  = 12 and b ₁  = 3; A is length in inches, while p ₂ , p ₁ , and p ₀ are yards, feet, and inches respectively.

Later in the text, a ternary system will be discussed. It has the following base constants:

b ₀ = 3                            B ₁ = b ₀ = 3
b ₁ = 3                            B ₂ = b ₁ B ₁ = 9
…
b_{m –1} = 3                        B_m = b_{m –1} B_{m –1} = 3^m                         (6)
…

When numerical systems are discussed, then the places p_m are integers, which are limited to the interval

   0 ≤ p_m  b_m                                                                          (7)

p_m must be less than the corresponding base constant b_m . For decimal, p_m is an integer: 0 ≤ p_m   holds true also when places p_m take values beyond the interval (7)! It is not even necessary that p 's are integers, but we should keep to the positive integers because, well, MCUs.

Let’s assume that A is a binary number 0xFF and that base constants B_m belong to the decimal system (3). The equation (2) holds even when p ₀  = 255, p ₁  = 0, and p ₂  = 0. This is an extreme. It holds also when p ₀  = 25, p ₁  = 13, and p ₂  = 1. But normally, the values are p ₀  = 5, p ₁  = 5, and p ₂  = 2. That is, 0xFF = 255.

In code or hardware for conversion between bases, R_m bits of memory are allocated for each place p_m . Usually, nibbles (R_m  = 4) or bytes (R_m  = 8) are used. The allocated memory is big enough when 2^Rm   ≥  b_m holds. Still, the allocated chunk of memory should be a bit larger to provide some space for bit carrying. Thus, the place p_m is an integer that is limited to the interval 0 ≤ p_m  ^Rm .

Additional space in p_m eases bit carrying from p_m  to p_{m +1} . What is this bit carrying? It is executed when p_{m +1} is incremented by one (a bit) and p_m is decremented by the base constant b_m . Decrementing is possible as long as p_m  ≥ b_m . Let us have a binary number A  = 0xDB and base constants b_m of the decimal system (3). Then, let the places be p ₂  = 2, p ₁  = 0, and p ₀  = 19. We can see that the equation (2) holds. We can also see that at least five bits are necessary to store p ₀ . To carry from p ₀ to p ₁ , the place p ₁ is incremented by 1 and p ₀ is decremented by b ₀  = 10. The p ₀ and p ₁ are adjusted. Now, the places are p ₂  = 2, p ₁  = 1, and p ₀  = 9. That is, 0xDB = 219. During the bit carrying, the equation (2) is always valid.

As said, the bit carrying consists of two steps. In one step, the place p_{m +1} is incremented. In the other step, the base constant b_m is subtracted from p_m . The two steps can be reduced into one by combining the two places p_{m +1} and p_m into one number 2^Rm  p_{m +1}  + p _m . This number already exists if p 's are allocated successively in the MCU's memory. That is, two successive bytes form one unsigned int. Then, a carry constant 2^Rm  – b _m is added to this new number. The effect can be seen in (8). The higher byte is incremented by one and the lower byte is decremented by b_m .

   p_m  ≥ b_m , (2^Rm p_{m +1} + p _m ) + (2^Rm – b _m ) = 2^Rm (p_{m +1} + 1) + (p_m – b _m )                    (8)

The order of adjusting places p_m in (2) plays no role. Either pair of places p ₀ , p ₁ or p_M , p_{M –1} , or any other pair, can be adjusted first. It is because equation (2) holds after any bit carrying. Despite that, it is beneficial that adjustment is executed from p ₀ upwards. This way, no p_m needs to be adjusted twice. By repeating adjustments, values of individual p 's are made smaller until the condition (7) is valid for all p_m . The places p_m are considered adjusted then.

Conversion of binary to some other system is possible by bit carrying only. The initial binary number A is moved into p ₀ , which must be large enough. Then, bit carrying is repeated until the condition (7) is fulfilled for all p 's. At this point, the number A is converted. Although this method works, it is inefficient. To speed up the conversion, left shifting, which has the same effect as multiplying by two, is introduced. Then, shifting and bit carrying are executed sequentially. The bit carrying is executed after each shift to keep the needed size of p 's as small as possible. At the same time, condition (7) is fulfilled. Because of the sequence, this is called a shift-adjust algorithm.

The algorithm runs in iterations. In the initializing iteration i  = 0, all p 's are cleared. Because of that, equation (9) is zero. Of course, condition (7) holds for all p_m , too.

   B_M p_M (i = 0) + … + B_m p_m (i = 0) + … + B ₁ p ₁ (i = 0) + p ₀ (i = 0) = 0            (9)

Now, the equation is multiplied by two. At the same time, bit a_{N –1} , which is the MSb of A in (1), is added to p ₀ . In assembler, this is done by left rotate through carry on A and p ₀ . Memory chunks of other p 's should be large enough so that p 's do not overflow during the shifting. They are shifted individually.

   2(B_M p_M (i = 0) + … + B_m p_m (i = 0) + … + B ₁ p ₁ (i = 0) + p ₀ (i = 0)) + a_{N –1} = a_{N –1}              (10)

After shifting, (10), the bit carries are repeated until the conditions in (7) are met for all m . Adjusting is not yet needed after the first shift. But to keep to the shift-adjust algorithm, adjusting of p 's by bit carrying takes place after each shift. After the first iteration is completed, (7) holds for all m . An equation (11) is obtained, which is an input to the second iteration.

   B_M p_M (i = 1) + … + B_m p_m (i = 1) + … + B ₁ p ₁ (i = 1) + p ₀ (i = 1) = a_{N –1}                 (11)

Now, shifting and adjusting take place again.

   B_M p_M (i = 2) + … + B_m p_m (i = 2) + … + B ₁ p ₁ (i = 2) + p ₀ (i = 2) = 2a_{N –1} + a_{N –2}          (12)

The sequence is repeated N -times.

   B_M p_M (i = N ) + … + B_m p_m (i = N ) + … + B ₁ p ₁ (i = N ) + p ₀ (i = N ) = 2^{N –1} a_{N –1} + … + 2 a ₁ + a ₀      (13)

After the last bit carrying is over, binary number A is on the right side of (13). On the left side, A is converted into numerals of the desired numerical system. These numerals are stored in the p 's.

Examples

In Example 1 , a binary number A  = 0xDB is converted into decimal, using the structure p ₂ .p ₁ .p ₀ :A . For each p , we allocate one byte (it is convenient to allocate bytes in 8-bit MCUs).

As we can see in shift₁ , the MSb from binary number A is shifted into p ₀ . After this shift, no bit carrying is needed in adjust₁ because conditions (7) for all p 's are already fulfilled. For the first time, bit carrying is executed in the adjust₄ . There, a carry constant, 2⁸  – 10, is added to a two-byte structure 0x000D to get 0x0103. This way, the bit carrying or adjusting is done on places p ₀ to p ₁ as explained in (8). After adjust₈ , there are decimal digits in the p 's.

Example 1  Converting 0xDB to 219 by the shift-adjust algorithm.

We now have a procedure for converting binary numbers to other bases, but it can be made even more code-efficient if we switch shifting and adjusting , which we’ll call an adjust-shift algorithm. In each iteration, all necessary bit carrying is executed first, then positions p_m are shifted. After both steps are over, the condition (7) must be fulfilled. Since the last step in an iteration is shifting, p_m 's must be properly adjusted before that. Therefore, the bit carry must be executed if p_m (i ) ≥ b_m /2. In this case, the carry constant (2^Rm  – b _m )/2 is added to p_m , as in (14).

   p_m  ≥ b_m /2, p _m + (2^Rm – b _m )/2 = 2^{Rm –1} + (2 p _m – b _m )/2                        (14)

At the beginning of each iteration of the adjust-shift algorithm, all places p_m comply to (7). Because of that, the (2 p _m  – b _m )/2 from (14) is always less than b _m /2. Furthermore, the b _m /2 is less than 2^{Rm –1} . Consequently, the p_m does not overflow when the carry constant (2^Rm  – b _m )/2 is added to it. That is, the right side of (14) is always less than 2^Rm . At the same time, adding the carry constant always sets an MSb, as we can see in (14). This MSb increments p_{m +1} during the following shifting phase of the iteration. The MSb from p_m must be carried to the LSb of p_{m +1} . Because of that, places of p_m in adjust-shift algorithms must be shifted as one big number.

Let's highlight the differences between the shift-adjust and adjust-shift algorithms. In the shift-adjust algorithm, two successive p_m 's take place in each bit carrying. On the other hand, p_m 's are adjusted individually in adjust-shift algorithm. Shifting is a different story. In the shift-adjust algorithm, each p_m is shifted individually. An exception is p ₀ , which is shifted together with A . On the other hand, all p 's and A are shifted as one big binary number in adjust-shift.

The carry constant (2^Rm   – b _m )/2 is the reason why the adjust-shift algorithm is suitable for even bases only. If the b_m is odd as in the ternary system, the carry constant would not be integer anymore.

The double dabble algorithm is an adjust-shift algorithm. It converts from binary to decimal (b_m  = 10) and its places p are stored in nibbles (R_m  = 4). Therefore, bit carry must be executed when p_m  ≥ 5 and the carry constant is (2^Rm – b _m )/2 = 3. That is why the double dabble is called the add 3 algorithm sometimes. In Example 2 , the binary number 0xDB is converted to decimal by the double dabble algorithm.

Example 2  Converting 0xDB to 219 by the double dabble algorithm.