C ++: converting binary to decimal

Question

I am trying to convert a binary array to decimal as follows:

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 need to convert a 64-bit binary array to decimal, and I have to do it a million times.

Can anybody help me if there is a faster way to do this? Or is it good?

Answer 1

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

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

or

  decimal = decimal * 2 + array[i]; 

Answer 2

Before attempting any optimization, it is important to profile the code. It is time to look at the generated code and optimize only when you understand what is happening.

And as already indicated, the best optimization is not to do something, but to make a higher level change that eliminates the need.

But...

Most of the changes you might want to make here trivially are likely to be what the compiler has already done (the shift is the same as multiplying by the compiler). Some may actually prevent the compiler from doing optimization (changing add to or limit 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 should already create decent code for dereferencing the array, so you need to check that you have not actually done anything worse by introducing an additional variable.

In this case, the number of cycles is well defined and limited, so rolling out probably makes sense.

In addition, it depends on how dependently you want the result to be in your target architecture. If you want portability, it's hard (er) to optimize.

For example, the following here gives the best code:

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

Perhaps I could also flip the 64-bit version, which did 8 bits at a time, not 4.

But this is very definitely not portable code. I could use this locally if I knew what I was working on, and I just wanted to quickly type in the numbers. But I probably won’t put it in production code. Of course, without documenting what he did, and without an accompanying unit test, which checks that it really works.

Answer 3

You can use accumulate with doubling and adding a binary operation:

 int doubleSumAndAdd(const int& sum, const int& next) { return (sum * 2) + next; } int decimal = accumulate(array, array+ARRAY_SIZE, doubleSumAndAdd); 

This results in large-end integers, while OP code produces little-endian.

Answer 4

Binary "compression" can be generalized as a weighted sum problem - and there are some interesting methods for this.

• X mod (255) means the summation of all independent 8-bit numbers.

• X mod 254 means summing each digit with doubling the weight, since 1 mod 254 = 1, 256 mod 254 = 2, 256 * 256 mod 254 = 2 * 2 = 4, etc.

  If the encoding was large endian, then the array * (unsigned long long)% 254 would create a weighted sum (with a truncated range of 0.253). Then deleting the value with a weight of 2 and adding it manually will lead to the correct result:

  uint64_t a = * (uint64_t *) array; return (a and ~ 256)% 254 + ((a → 9) and 2);

Another mechanism for gaining weight is to pre-multiply each binary digit by 255 and mask the correct bit:

 uint64_t a = (*(uint64_t *)array * 255) & 0x0102040810204080ULL; // little endian uint64_t a = (*(uint64_t *)array * 255) & 0x8040201008040201ULL; // big endian 

In both cases, you can take the rest of 255 (and now fix it with a weight of 1):

 return (a & 0x00ffffffffffffff) % 255 + (a>>56); // little endian, or return (a & ~1) % 255 + (a&1); 

For a skeptical mind: I really worked out a module version to be (slightly) faster than iterating on x64.

To continue with JasonD's answer, iterative selection of a parallel bit can be used. But first, expressing the equation in full form will help the compiler remove the artificial dependency created by the iterative approach using accumulation:

 ret = ((a[0]<<7) | (a[1]<<6) | (a[2]<<5) | (a[3]<<4) | (a[4]<<3) | (a[5]<<2) | (a[6]<<1) | (a[7]<<0)); 

vs.

 HI=*(uint32_t)array, LO=*(uint32_t)&array[4]; LO |= (HI<<4); // The HI dword has a weight 16 relative to Lo bytes LO |= (LO>>14); // High word has 4x weight compared to low word LO |= (LO>>9); // high byte has 2x weight compared to lower byte return LO & 255; 

Another interesting method is to use crc32 as a compression function; it just turns out that the result is LookUpTable [crc32 (array) and 255]; since there is no collision with this given small subset of 256 different arrays. However, to apply this, you have already chosen a path with even less portability and could also use SSE functions.

Answer 5

Try this, I converted the binary digit to 1020 bits

 #include <sstream> #include <string> #include <math.h> #include <iostream> using namespace std; long binary_decimal(string num) /* Function to convert binary to dec */ { long dec = 0, n = 1, exp = 0; string bin = num; if(bin.length() > 1020){ cout << "Binary Digit too large" << endl; } else { for(int i = bin.length() - 1; i > -1; i--) { n = pow(2,exp++); if(bin.at(i) == '1') dec += n; } } return dec; } 

Theoretically, this method will work for a binary digit of length infinate