Converting decimal integer to binary string

Question

I'm wondering how I can make this function better, more compact, even faster.

char* DectoBin(int dec) {
    int counter = 0;
    int x =0;
    while (dec>=x) {
        counter++;
        x = pow(2, counter);
    }
    //counter is the # of bits in the converted binary number
    char* bin = new char[counter+1];
    //+1 for nul byte
    int y = counter;
    int remainder = 0;

    while (counter > 0) {
        //% the dec number with the base 2 each time and if remainder>0 then set the bit
        remainder = dec % 2;
        dec /= 2;
        if (counter == y) {
            bin[counter] = '\0';
        }

        if (remainder > 0) {
            bin[(counter - 1)] = '1';
        }
        else {
            bin[(counter - 1)] = '0';
        }
        counter--;
    }
    return bin; 
}

Answer 1

What about taking the trailing zero out of the loop?

while (counter > 0) {

// ...

    if (counter == y) {
        bin[counter] = '\0';
    }

might look like this

bin[counter] = '\0';
--counter;

while (counter > 0) {

// ...

and you don't need int y anymore.

Also --counter might be tiny bit faster than counter-- in case your optimizer is not going to help you.

---

As the code is not dealing with negative values I guess

char* DectoBin(unsigned dec) {

would be more appropriate.

Answer 2

MORTAL gave a good answer on how to print the value of the number, but if you still want to compute the exact number of characters needed before, then:

int x =0;
while (dec>=x) {
    counter++;
    x = pow(2, counter);
}

This calculates the pow each time, it's a bit overkill.

Using your later approach would be more efficient:

unsigned x = dec;
do {
    counter++;
    x >>=1; //Or x /= 2
} while (x > 0);

I also notice that although you tagged your code c++, the only c++ thing you're using is new[] and this could as easily be C code if you used malloc().

If you're doing C++, check out its standard library and notably things like std::vector, std::string and auto.

Answer 3

new [] is always wrong

I usually try to stay away from absolutes, but this is an exception. I've become convinced that there is no good reason to use the array form of new in C++¹. It's better to forget that this even exists.

You want to use some sort of container instead. For this, the obvious choice would be std::string, but there's a fair argument to be made in favor of std::deque instead.

pow doesn't make a lot of sense here

For integer powers of 2, you can use bit-shifting. You're going a binary conversion, which deals with bits. Embrace that, and deal with bits as bits.

% isn't really helpful here either

Again, you're dealing with bits, so deal with bits. This deals in binary, and for anything dealing in binary, foo & 1 makes perfectly good sense. We're trying to see if a bit is set, and that's exactly what this does.

Consider math or data over flow control

When you get the least significant bit of your input, you get either a 0 or a 1. Right now, you use an if/else to determine what to do with it. Some of the other answers have recommended a conditional operator instead. My preference would be to get rid of using flow control here at all, and just use the number of index into an array:

char bits[] = "01";
std::deque<char> result;

while (input != 0) {
    result.push_front(bits[input & 1]);
    input >>= 1;
}

Alternatively, we could do a bit of math instead:

for (int i=0; i<bits; i++) {
   result.push_front((input & 1) + '0');
   input >>= 1;
}

Now you can see why I mentioned deque previously--it has a push_front, which lets us generate our results in the order we need them. If we want the result as a string instead, we can create a string from the deque:

return std::string(result.begin(), result.end());

Using a deque doesn't make a huge difference though. We can just as easily create the string in reverse, but then return a reversed copy:

std::string result;

for (int i=0; i<bits; i++) {
    result.push_back((input & 1) + '0');
    input >>= 1;
}
return std::string(result.rbegin(), result.rend());

Consider generating bits from most to least significant

As noted above, when we look at the least significant bit of the input to find a bit, then shift it right to find the next, we end up generating the bits from least to most significant, which can be somewhat difficult to deal with after we're done. It may be worth considering generating the bits from most significant to least significant instead. This can give an inner loop something on this order:

for (int i=bits-1; i > -1; i--) {
    auto val = U >> i;
    result.push_back((val & 1) + '0');
}

Consider a template

There's nothing unique to int here. Converting short, long, long long, etc., are all pretty much the same.

Consider using unsigned internally

When dealing with bits, I prefer to do everything on unsigned types. This makes things like dealing with negative inputs much simpler and cleaner.

Consider using numeric_limits to get the bit count

The standard library has std::numeric_limits, which includes a digits member. For a binary type, that gives you the number of bits in a type, so you don't need to compute the size on your own. Note: this only gives the number of bits that hold the value in a type, so (for example) a 32-bit signed int will have digits == 31 because the sign bit isn't included. If, however, you use an unsigned type as advised above, this isn't really a concern.

Testing

Even if it doesn't attempt to do truly comprehensive testing, I always prefer to include at least a little test/demo code with almost any function like this.

Final code

Putting all those together, we might end up with code something on this general order:

#include <string>
#include <iostream>
#include <type_traits>
#include <iomanip>
#include <limits>

template <class T>
std::string to_bin(T in) { 
    using U = typename std::make_unsigned<T>::type;

    U input( in );

    std::string result;

    unsigned bits = std::numeric_limits<U>::digits;

    for (int i=bits-1; i > -1; i--) {
        auto val = input >> i;
        result.push_back((val & 1) + '0');
    }
    return result;
}

template <class T>
void test(std::string const &label, std::initializer_list<T> inputs) {
    static const int width = 20;

    std::cout << "\n" << label << "\n";

    for (auto i : inputs)
        std::cout << std::setw(width) << std::showbase << std::hex << i << "\t" << to_bin(i) << "\n";
}

int main() { 
    test("unsigned", { 1u, 2u, 3u, 17u, -1u });
    test("int", { 1, 3, 5, 10, 255, -1, 17, 0x5a5a5a5a });
    test("long long", { -1LL, 0x5a5a5a5a5a5a5a5a });
}

---

^{1. Since people routinely bring it up: no, you don't use it even when implementing a container. For that you use an allocator to allocate raw memory, then placement new to create objects in that memory. The allocator shouldn't use new [] either--it should typically use operator new.}