Thread: Decimal to Binary String competition

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    3

    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

  2. #2
    'Allo, 'Allo, Allo
    Join Date
    Apr 2008
    Posts
    639
    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;
    }

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by adeyblue View Post
    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!...
    Devoted my life to programming...

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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;
    }
    Last edited by anon; 02-02-2011 at 10:52 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Feb 2011
    Posts
    3
    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!

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    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?

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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...
    Last edited by Sebastiani; 02-03-2011 at 12:18 PM. Reason: expand print stmt, -&nbsp;, add generator, amend example, cmt
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Sebastiani
    Code:
    /*
        Disregard; used internally only
    */
    Unnamed namespace FTW
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by laserlight View Post
    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...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 11
    Last Post: 06-16-2011, 11:59 AM
  2. OOP Question DB Access Wrapper Classes
    By digioz in forum C# Programming
    Replies: 2
    Last Post: 09-07-2008, 04:30 PM
  3. Compile Error that i dont understand
    By bobthebullet990 in forum C++ Programming
    Replies: 5
    Last Post: 05-05-2006, 09:19 AM
  4. hex to binary,hex to decimal
    By groovy in forum C Programming
    Replies: 2
    Last Post: 01-25-2006, 02:14 AM
  5. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM