C++: Binary to Decimal Conversion

Question

I am trying to convert a binary array to decimal in following way:

uint8_t array[8] = {1,1,1,1,0,1,1,1} ;
int decimal = 0 ;    

for(int i = 0 ; i < 8 ; i++)
    decimal = (decimal << 1) + array[i] ;

Actually I have to convert 64 bit binary array to decimal and I have to do it for million times.

Can anybody help me, is there any faster way to do the above ? Or is the above one is nice ?

Answer 1

Your method is adequate, to call it nice I would just not mix bitwise operations and "mathematical" way of converting to decimal, i.e. use either

    decimal = decimal << 1 | array[i];

or

    decimal = decimal * 2 + array[i];

Answer 2

It is important, before attempting any optimisation, to profile the code. Time it, look at the code being generated, and optimise only when you understand what is going on.

And as already pointed out, the best optimisation is to not do something, but to make a higher level change that removes the need.

However...

Most changes you might want to trivially make here, are likely to be things the compiler has already done (a shift is the same as a multiply to the compiler). Some may actually prevent the compiler from making an optimisation (changing an add to an or will restrict the compiler - there are more ways to add numbers, and only you know that in this case the result will be the same).

Pointer arithmetic may be better, but the compiler is not stupid - it ought to already be producing decent code for dereferencing the array, so you need to check that you have not in fact made matters worse by introducing an additional variable.

In this case the loop count is well defined and limited, so unrolling probably makes sense.

Further more it depends on how dependent you want the result to be on your target architecture. If you want portability, it is hard(er) to optimise.

For example, the following produces better code here:

unsigned int x0 = *(unsigned int *)array;
unsigned int x1 = *(unsigned int *)(array+4);

int decimal = ((x0 * 0x8040201) >> 20) + ((x1 * 0x8040201) >> 24);

I could probably also roll a 64-bit version that did 8 bits at a time instead of 4.

But it is very definitely not portable code. I might use that locally if I knew what I was running on and I just wanted to crunch numbers quickly. But I probably wouldn't put it in production code. Certainly not without documenting what it did, and without the accompanying unit test that checks that it actually works.