Decimal to Binary String competition

Hi All!

I've not posted on here before, but I thought I'd start somewhere with a small competition/point of interest!

Anyway, i've always had a nagging for producing an efficient method of creating a binary representation of a string. It's a deceptively simple problem - perhaps because it relates so closely with the raw bits of the system, but more often that not, the solution is a boring for() loop!

So the challenge (if you choose to accept it) is to come up with an interesting, efficient, fast way of producing a binary representation of a string in either C/C++.

Mine is,

Code:

std::string to_bin(const int *data){
	/* Were going to assume 32-bit ints */
	unsigned int mask = 0x00000001;
	std::string ret_string;
	
	while( !(mask & 0x00000000) ){
		if(mask & *(data))
			ret_string = '1' + ret_string;
		else 
			ret_string = '0' + ret_string;
				
		mask <<= 1;
	}
	return ret_string;
}

Happy Coding!

D

Code:

#include <iostream>
#include <bitset>
#include <climits>

typedef std::bitset<sizeof(unsigned long) * CHAR_BIT> long_set;

std::string Long2BinStr(const long_set& bits)
{
   return bits.to_string();
}

int main()
{
   std::cout << "Stop crying 40, you're in bits: " << Long2BinStr(40) << std::endl;
}

Originally Posted by adeyblue

Code:

#include <iostream>
#include <bitset>
#include <climits>

typedef std::bitset<sizeof(unsigned long) * CHAR_BIT> long_set;

std::string Long2BinStr(const long_set& bits)
{
   return bits.to_string();
}

int main()
{
   std::cout << "Stop crying 40, you're in bits: " << Long2BinStr(40) << std::endl;
}

Probably not an efficient one!...

Originally Posted by hutchid

i've always had a nagging for producing an efficient method of creating a binary representation of a string.

Looking at your code, it looks like you want a binary representation of a 32-bit integer as a string of '0's and '1's.

Your program appears to be infinitely slow (x & 0 is always false).

Apart from that one might also avoid prepending to a std::string which is a slow operation.

How about:

Code:

#include <string>
#include <climits>

std::string to_bin(unsigned data){

	std::string ret_string( sizeof(unsigned) * CHAR_BIT, '0');
	std::string::size_type index = ret_string.size();
	while( data ){
		ret_string[--index] = (data & 1) + '0';
		data >>= 1;
	}
	return ret_string;
}

Your program appears to be infinitely slow (x & 0 is always false).

Your very right, very right indeed, I think it should read 0x80000000! (Of course that would give us -1 the number of bits were looking for.

Looking at your code, it looks like you want a binary representation of a 32-bit integer as a string of '0's and '1's.

Again apologies for my typo, I actually meant to say a binary string representation of a given input!

-----

The std::bitset is a nice idea as it abstracts away from the system nicely (assuming you like that sort of thing). Does anyone know how efficient it actually is, in fact, I'll compile all these functions together and run some kind of benchmark on them when a couple more have been posted.

How about:

Code:

Code:
#include <string>
#include <climits>

std::string to_bin(unsigned data){

	std::string ret_string( sizeof(unsigned) * CHAR_BIT, '0');
	std::string::size_type index = ret_string.size();
	while( data ){
		ret_string[--index] = (data & 1) + '0';
		data >>= 1;
	}
	return ret_string;

}

I really like this approach, very efficient, ok for small values passed in by value.

But now to up the game, modify any functions to work on a bit stream of arbitrary length, data to be 'bit-stringed' is passed in via unsigned char* with it's length in bytes.

Code:

std::string to_bin(const unsigned char* c, size_t len)

My submission to follow later!

You could always use a 64-bit multiply to spread out the bits and then add the +1 offsets to 8 '0' bytes at a time. See the bithacks website for something similar. Of course there would be an even better way to do it using intrinsics or mmx / sse etc I expect. All because what's asked for here is fixed-length of course, and the competition is lacking in specification so I can assume any platform I want.

Code:

while( !(mask & 0x00000000) ){

Spot the person who doesn't write units test, or even so much as execute their own code.

Given that you didn't specify the byte ordering, something like this should work(untested code, but you get the idea).

Code:

for (size_t i = 0; i < len * CHAR_BITS; i++)
   string += '0' + (c[i / CHAR_BITS] >> ((CHAR_BITS - 1) - (i % CHAR_BITS))) & 0x1;

Change the index of c[] if you want it in reverse order.

Talking about efficiency is a premature optimization at this point. How fast does it need to be?

What can I say? I was bored!

So I decided to use a lookup table for each byte, and to use iterators rather than strings, for flexibility.

Code:

/*
    Functions 'to_binary_text' and 'integer_to_binary_text' convert objects and 
    integers to binary representation using iterators. Class 'additive_iterator' 
    can be used as an adaptor for std::strings and the like.
*/
/*
    TODO: Address localization issues...
*/
#include <string>
#include <iterator>
#include <vector>
/*
    Disregard; used internally only
*/
std::vector< std::string > to_binary_text_table_generate_( void ) {
    size_t cnt = 1 << CHAR_BIT;
    std::vector< std::string > tab( cnt );
    for( size_t idx = 0; idx < cnt; ++idx )
        for( size_t msk = cnt >> 1; msk; msk >>= 1 )
            tab[ idx ] += idx & msk ? "1" : "0";
    return tab;
}
/*
    Copies the binary representation of an object to an iterator, 
    ordered from lowest to highest address, by default
*/
template < typename Type, typename OutputIterator >
OutputIterator to_binary_text( 
    Type const& value, 
    OutputIterator result, 
    std::string const & separator = " ", 
    bool ascending_order = true 
) {
    typedef unsigned char* Iter;
    int inc = 1;
    Iter seq = Iter( &value ), fin = seq + sizeof( Type );
    if( !ascending_order ) {
        inc = -inc;
        std::swap( --seq, --fin );
    }
    static std::vector< std::string > tab = to_binary_text_table_generate_( );
goto skip;
    for( ; seq != fin; seq += inc ) {
        *result++ = separator;
skip:    
        *result++ = tab[ *seq ];
    }
    return result;
}
/*
    Copies the binary representation of an integer to an iterator, 
    in 'standard' (ie: big-endian) position, by default
*/
template < typename Integer, typename OutputIterator >
OutputIterator integer_to_binary_text(
    Integer const& value, 
    OutputIterator result, 
    std::string const & separator = " ", 
    bool big_endian = true 
) {
    static Integer tst = 1;
    static bool big = !*( unsigned char* )&tst;
    return to_binary_text( value, result, separator, big == big_endian );
}
/*
    An iterator interface adaptor for containers that implement operator += (eg: std::string)
*/    
template < class Container >
class additive_iterator : public std::iterator< std::output_iterator_tag, void, void, void, void > {
public:
    additive_iterator( Container& object )
    : ptr( &object ) {
    }
    template < typename Other >
    additive_iterator< Container >& operator = ( Other const& value ) { 
        *ptr += value;
        return *this; 
    }
    additive_iterator< Container >& operator* ( void ) { 
        return *this; 
    }
    additive_iterator< Container >& operator++ ( void ) { 
        return *this; 
    }
    additive_iterator< Container > operator++ ( int ) { 
        return *this; 
    }
protected:
    Container* ptr;
};
/*
    Type-deductive generator helper function
*/
template < class Container >
inline additive_iterator< Container > make_additive_iterator( Container& object ) {
    return additive_iterator< Container >( object );
}
/*
    Example
*/
#include <iostream>
#pragma pack( push, 1 )
struct test {
    int i;
    char c;
};
#pragma pack( pop )
int main( void ) {
    using namespace std;
    test tst = { 1024, 'a' };
    string sts, sti, stc;
    to_binary_text( tst, make_additive_iterator( sts ) );
    integer_to_binary_text( tst.i, make_additive_iterator( sti ) );
    integer_to_binary_text( tst.c, make_additive_iterator( stc ) );
    cout << "- Entire structure, ordered from lowest to highest address -" << endl;
    cout << "Bin: " << sts << endl;
    cout << "- Integer in structure, in standard (big-endian) position -" << endl;
    cout << "Dec: " << tst.i << endl;
    cout << "Bin: " << sti << endl;
    cout << "- Character in structure -" << endl;
    cout << "Dec: " << ( int )tst.c << endl;
    cout << "Bin: " << stc << endl;
}

May need some improvement, tho...

Originally Posted by Sebastiani

Code:

/*
    Disregard; used internally only
*/

Unnamed namespace FTW

Originally Posted by laserlight

Unnamed namespace FTW

Yeah, inexplicably, I just went with the old C convention there: choose a long-winded identifier followed by an underscore...and hope for the best! Anyway, the whole lot of the code should be put in a namespace, really...