Convert int to a string binary..

[wookieboy]

This code takes in any in..convert to binary and reverse it in string.. forms a 8 bit binary string.enjoy~


string binary(int K)
{
string fBin = "", addZero = "";
int a,b = K, binSize = 0;
string itos(int);

while(b > 0)
{
a = b % 2;
b = b / 2;

fBin += itos(a);
}

binSize = 8 - fBin.length();

//add trailing zeros
for(int i=0;i<binSize;i++)
{
addZero += "0";
}

if(fBin.length()<8)
{
fBin+=addZero;
}

//reverse the string of binary
int x = fBin.length(); //takes length of string
for(int y = x; y >= (x/2)+1; y--) //for loop arranging the string
{
swap(fBin[x-y],fBin[y-1]); // swaps letters
}

return fBin;
}

//Convert in to string..this converts int to string
string itos(int i)
{
stringstream s;
s<<i;
return s.str();
}

[helios]

How did you manage to cram so much fail into so few lines?

std::string dec2bin(unsigned n){
    const int size=sizeof(n)*8;
    std::string res;
    bool s=0;
    for (int a=0;a<size;a++){
        bool bit=n>>(size-1);
        if (bit)
            s=1;
        if (s)
            res.push_back(bit+'0');
        n<<=1;
    }
    if (!res.size())
        res.push_back('0');
    return res;
}

[Hammurabi]

> How did you manage to cram so much fail into so few lines?

It's an artform, really.

[Duthomhas]

Y'all are doing too much thinking:

string binary( unsigned long n )
  {
  char     result[ (sizeof( unsigned long ) * 8) + 1 ];
  unsigned index  = sizeof( unsigned long ) * 8;
  result[ index ] = '\0';

  do result[ --index ] = '0' + (n & 1);
  while (n >>= 1);

  return string( result + index );
  }

This will, of course, only work for integral types...

[edit] Oh yeah, if you don't mind ignoring ISO C++ standards and using compiler extensions, you could substitute unsigned long long on lines 1, 3, and 4.

[edit 2] Also, the OP's choice of using reverse was a good idea, for more simplicity:

string binary( unsigned long n )
  {
  string result;

  do result.push_back( '0' + (n & 1) );
  while (n >>= 1);

  reverse( result.begin(), result.end() );
  return result;
  }

OK, I'm done now... [edit 3] man... to slow...

Enjoy!

[PanGalactic]

That still seems convoluted, Helios.

std::string dec2bin(unsigned n)
{
    std::string res;

    while (n)
    {
        res.push_back((n & 1) + '0');
        n >>= 1;
    }

    if (res.empty())
        res = "0";
    else
        std::reverse(res.begin(), res.end());
 
   return res;
}

[helios]

Duoas: Oh, nice!

PanGalactic: I didn't want to do string reversal.

[Duthomhas]

Yeah, string reversal costs something... trying to keep accesses down...

:-)

[PanGalactic]

Nice use of do/while, Duoas. +1

[Bazzy]

What about using a bitset? It would be a lot easier!
http://www.cplusplus.com/reference/stl/bitset/

[Duthomhas]

...but more problematic because bitsets have a fixed number of bits, and the to_string() method always converts that many digits. You'd need to jump through a few more hoops than a simple reverse() to get the output just right... (meaning, sans leading zeros)

When performing an integer to binary conversion (or any other such conversion) it is always best to traverse the bits once, and again to only traverse the resulting string once -- preferably traverse them at the same time. This is nothing more than a pure speed advantage. Addition of the reverse() function is significant.

string binary( unsigned long n )
  {
  bitset <sizeof( unsigned long ) * 8> bits( n );
  string result = bits.to_string <char, char_traits <char>, allocator <char> > ();
  string::size_type x = result.find( '1' );
  if (x != string::npos)
    result = result.substr( x );
  return result;
  }

Makes me want to barf... :-@

;-)

My $0.02

[PanGalactic]

Bazzy: I had no idea bitset had those features. That's cool.

Duoas:

This will collapse your first two lines into something more readable:

std::string result = std::bitset<sizeof(n) * 8>(n).to_string();

You don't need the template arguments for to_string().

In my line of work, code readability/maintainability is the first priority. If it is not fast enough, then optimize. The bitset and reverse methods are much easier to comprehend on first reading than your first example. Also, since reverse is working on a small dataset that was just used, it is almost certainly working in the CPU's level 1 cache. You'd have to be doing *a lot* of binary conversions to ever notice the difference. All of the time in both functions will be spend allocating memory for the strings. The optimization that will likely make the most difference in reverse() case is to reserve(sizeof(n) * 8) in the result string.

Note that in your first method, you have to traverse your char array three times. Once to set the values. Once to get the length for the string assignment. And then again to copy the data into the string buffer.

I'm pretty well convinced that reverse() with reserve() is the fastest method. It only traverses the string twice at the expense of a few wasted bytes.

[helios]

This calls for a benchmark.

#include <iostream>
#include <cstdlib>
#include <ctime>

std::string Helios_dec2bin(unsigned n){
    const int size=sizeof(n)*8;
    std::string res;
    bool s=0;
    for (int a=0;a<size;a++){
        bool bit=n>>(size-1);
        if (bit)
            s=1;
        if (s)
            res.push_back(bit+'0');
        n<<=1;
    }
    if (!res.size())
        res.push_back('0');
    return res;
}

std::string Duoas_dec2bin(unsigned n){
    char result[(sizeof(unsigned)*8)+1];
    unsigned index=sizeof(unsigned)*8;
    result[index]='\0';
    do result[--index]='0'+(n&1);
    while (n>>=1);
    return std::string(result+index);
}

std::string PanGalactic_dec2bin(unsigned n){
    std::string res;
    while (n){
        res.push_back((n&1)+'0');
        n>>=1;
    }
    if (res.empty())
        res="0";
    else
        std::reverse(res.begin(),res.end());
    return res;
}

typedef std::string(*func_p)(unsigned);

unsigned rnd32(){
    return rand()|(rand()<<15)|(rand()<<30);
}

int main(){
    srand(time(0));
    func_p array[]={
        &Duoas_dec2bin,
        &Helios_dec2bin,
        &PanGalactic_dec2bin,
        0
    };
    for (int a=0;array[a];a++){
        unsigned t0=clock();
        for (unsigned b=0;b<100000;b++)
            array[a](rnd32());
        unsigned t1=clock();
        std::cout <<a<<": "<<t1-t0<<std::endl;
    }
    return 0;
}

Output without optimizations:
0: 62
1: 1312
2: 1344
Output with optimizations:
0: 62
1: 1297
2: 1265

PanGalactic: No, it doesn't traverse it three times. The first time, the size of the traverse is log(x)/log(2)+1, the second traverse creates the std::string and is the same size as the first, and there's no third time.


EDIT: Oh, by the way, most of the time on yours and mine is spent push_back()ing. This is the output reserve()ing 64 characters and optimizing:
0: 78
1: 250
2: 297

[wookieboy]

hahaha...thats nice of everyone to send it their stuff..it was for a assignment..wanted to find codes for that purpose but cant find a reasonable good one..so i wrote mine and thot it was useful..hope it helped others in future..

[PanGalactic]

If you use reserve(), use do/while (see Duoas's example), and actually assign the results to a string in your benchmark code, the results look a little different.

Also, there is too much variation in the results. Creating a set list of random values that all three use results in more predictable results.

But I concede. Douas's method is faster. But not by the amount given.

Output on Linux, GCC 4.3.0, counter bumped up to 1000000, -O3
0: 160000
1: 330000
2: 330000

[helios]

Also, there is too much variation in the results.

16 ms is not too much variation. Actually, it seems to be my clock()'s granularity.

The same code, feeding 0xFFFFFFFF (worst case) to all functions, using reserve(), no optimizations, and n=10,000,000:
First run:
0: 5062
1: 23547
2: 30140
Second run:
0: 5046
1: 23610
2: 30047
Third run:
0: 5109
1: 23516
2: 30015
(By the way, same as above, plus optimizations reduces your time by 10 seconds.)
Average variation: .68%
I wouldn't say that's a lot.

If you use reserve(), use do/while (see Duoas's example), and actually assign the results to a string in your benchmark code, the results look a little different.

The point was to find which of the three functions was the fastest as they were posted, but okay.

Manual optimizations:

#include <iostream>
#include <cstdlib>
#include <ctime>

#define METHODB

std::string Helios_dec2bin(unsigned n){
    const int size=sizeof(n)*8;
    bool s=0;
#ifndef METHODB
    std::string res;
    for (int a=0;a<size;a++){
        bool bit=n>>(size-1);
        if (bit)
            s=1;
        if (s)
            res.push_back(bit+'0');
        n<<=1;
    }
    if (!res.size())
        res.push_back('0');
    return res;
#else
    char temp[size+1]={0};
    int a=0,b=0;
    do{
        bool bit=n>>(size-1);
        if (bit)
            s=1;
        if (s)
            temp[b++]=bit+'0';
        n<<=1;
    }while (++a<size);
    if (!b)
        temp[b++]='0';
    return std::string(temp);
#endif
}

std::string Duoas_dec2bin(unsigned n){
    char result[(sizeof(unsigned)*8)+1];
    unsigned index=sizeof(unsigned)*8;
    result[index]='\0';
    do result[--index]='0'+(n&1);
    while (n>>=1);
    return std::string(result+index);
}

std::string PanGalactic_dec2bin(unsigned n){
#ifndef METHODB
    std::string res;
    while (n){
        res.push_back((n&1)+'0');
        n>>=1;
    }
    if (res.empty())
        res="0";
    else
        std::reverse(res.begin(),res.end());
    return res;
#else
    const int size=sizeof(n)*8;
    char temp[size+1]={0};
    int a=0;
    do{
        temp[a++]=(n&1)+'0';
        n>>=1;
    }while (n);
    if (!a)
        temp[a++]='0';
    else
        std::reverse(temp,temp+a);
    return std::string(temp);
#endif
}

typedef std::string(*func_p)(unsigned);

unsigned rnd32(){
    return rand()|(rand()<<15)|(rand()<<30);
}

int main(){
    /*std::cout <<Helios_dec2bin(0)<<' '<<Helios_dec2bin(10)<<std::endl
        <<PanGalactic_dec2bin(0)<<' '<<PanGalactic_dec2bin(10)<<std::endl;
    return 0;*/
    srand(time(0));
    func_p array[]={
        &Duoas_dec2bin,
        &Helios_dec2bin,
        &PanGalactic_dec2bin,
        0
    };
    for (int a=0;array[a];a++){
        unsigned t0=clock();
        for (unsigned b=0;b<10000000;b++)
            array[a](0xFFFFFFFF);
        unsigned t1=clock();
        std::cout <<a<<": "<<t1-t0<<std::endl;
    }
    return 0;
}

F:\Documents and Settings\root\Desktop>g++ test.cpp -o test -O3

F:\Documents and Settings\root\Desktop>test
0: 5000
1: 4859
2: 5282
LOL WUT?
I have to see that again.
0: 4953
1: 4890
2: 5360

I think I won (somehow).

[PanGalactic]

Try this for main():

int main(){

    const size_t iterations = 10000000;
    
    srand(time(0));
    func_p array[]={
        &Duoas_dec2bin,
        &Helios_dec2bin,
        &PanGalactic_dec2bin,
        0
    };

    std::string results[3];

    std::vector<unsigned int> random_values(iterations);
    std::generate(random_values.begin(), random_values.end(), rnd32);
    
    for (int a=0;array[a];a++){
        unsigned t0=clock();
        for (unsigned b=0;b<iterations;b++)
            results[a] = array[a](random_values[b]);
        std::cout << results[a] << std::endl;
        unsigned t1=clock();
        std::cout <<a<<": "<<t1-t0<<std::endl;
    }
    return 0;
}

You are missing an include for <algorithm> (for reverse()) and you'll need to add <vector>.

Here are the results I get:

g++ -O3 -march=k8 -m64 -o binbench2 binbench2.C
./binbench2
1101111011110111101010001010101
0: 1700000
1101111011110111101010001010101
1: 2990000
1101111011110111101010001010101
2: 1960000

[helios]

You are missing an include for <algorithm> (for reverse())

Somehow, g++ didn't complain. ¯\(°_o)/¯

I can't use any of the CPU-specific optimization, since I'm using a Core 2 Duo.

10000000111010011100110000100001
0: 6203
10000000111010011100110000100001
1: 8016
10000000111010011100110000100001
2: 6937

Yeah, these look more reasonable. All those checks inside the loop really cost me. Also, I overestimated std::reverse()'s penalty. However, it seems the biggest bottleneck was push_back(). Even without optimizations, the three times are very close.
How did you manage to duplicate the time for 1 and 2 in relation to 0 in your previous post?

[jsmith]

Just for grins you could try defining NDEBUG to turn off debugging in the STL since that tends to slow it down a lot.

[PanGalactic]

Helios: No clue how I got the times the same. I cannot duplicate it now. Probably my clock frequency was changing.

Jsmith: No difference with GCC 4.3.0 on Linux.

Here's a slightly faster version based on Duoas's code.

std::string Duoas_dec2bin(unsigned n)
{
    const size_t size = sizeof(n) * 8;
    char result[size];

    unsigned index = size;
    do {
        result[--index] = '0' + (n & 1);
    } while (n >>= 1);

    return std::string(result + index, result + size);
}

Runs in 1.41 seconds instead of 1.70. It eliminates the double scan of result when assigning the string. The double scan happens because std::string has to get the strlen() first to allocate the buffer, then copies the data into the string buffer. This way the string constructor just uses the difference between the pointers to get the size needed.

You really cannot beat allocating the buffer on the stack for speed.

[jsmith]

True, though the construction of the string requires a memory allocation and a copy.

It could probably be made faster if string didn't initialize the internal buffer to all zeros when it allocates it, as then you could use string's buffer directly, avoiding the extra copy.

EDIT: RVO might also have an effect on the speed, as otherwise returning the value from the function requires a second allocation and copy.

Personally I'd pull out the cout from the timing loop to ensure that just the function is being timed.