C routine speeds decimal-to-binary conversion

Giovanni Motta, Brandeis University, Waltham, MA -- EDN, 11/24/1999

A previous Design Idea ("Program provides integer-to-binary conversion," EDN, March 2, 1998, pg 110) describes a C/C++ function that provides integer-to-binary conversion. The function, named cintbin/classicC, implements a conversion in a straightforward way that defines decimal and binary numbers in terms of powers. Although this function can be useful for testing or educational purposes, its low efficiency precludes its use in embedded or other fast applications. The main source of inefficiency is the use of the pow C function, which requires linking the math library. By carefully rewriting the function and by directly accessing the binary representation of the integers in C, you can speed the conversion by as much as 58 times. The rewrite also results in more compact code, because linking the math library is unnecessary. Listing 1 shows a simple calling program and two functions, fast_d2b and fast_b2d, that implement conversion between decimal and binary integer representations.

In fast_d2b, the main loop is a for loop, in which the variable, i, accesses the array, c, sequentially, from 0 to 31. At each iteration, x, the number to convert, right-shifts by i positions (the >> operator), and the routine extracts its least significant bit by masking x with the constant 1 (the & operator). The routine finally assigns the result to the i^th term of the vector c. The symmetric fast_b2d function converts a binary number to its decimal equivalent. The function performs the conversion through a sequence of left shifts and sums. To compare the performance of fast_d2b with the function classicC, we ran several tests on two platforms, both running Unix-like OSs. We used the GNU C compiler (gcc) with and without turning on "aggressive optimization" (the O3 flag). Table 1 shows the time to convert the first 100 million integers. The Unix time command produces the running-time figure. Fast_d2b is 20 to 58 times faster than classicC. (DI #2443).