Bits and bytes- Please help.

This is a discussion on Bits and bytes- Please help. within the C Programming forums, part of the General Programming Boards category; Lol, this discussion took all kinds of turns. The OP needed to know the first MSB set to decide on ...

  1. #61
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Lol, this discussion took all kinds of turns. The OP needed to know the first MSB set to decide on the lowest numbered channel available. I believe I am clear now, but there was mention that the rest of the bits or bytes were to be summed up and added to the result, though not clear on what that was to achieve.

    That computing trailing zeros howto was real interesting.

  2. #62
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,725
    Quote Originally Posted by quzah
    The ordering didn't confuse me, the OP saying they wanted "first" when really they wanted "last" confused me.
    Me too, but based on the examples it became obvious what the OP actually meant.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #63
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by laserlight View Post
    Me too, but based on the examples it became obvious what the OP actually meant.
    Obvious if you haven't just woken up, sure.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #64
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,725
    Quote Originally Posted by slingerland3g
    but there was mention that the rest of the bits or bytes were to be summed up and added to the result, though not clear on what that was to achieve.
    Are you referring to the explanations of how to use a smaller lookup table?

    Quote Originally Posted by quzah
    Obvious if you haven't just woken up, sure.
    Heh. I am going to sleep now.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #65
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Well, after running a few tests, it appears that the lookup table method is probably the fastest route (roughly 10 times faster than the bit-by-bit and ceil/log2 (I'm not sure if this could be optimized for integers, though) approaches).

    Code:
    int initialize_table( unsigned char table[ 256 ] )
    {
        table[ 0 ] = 0;
        int
            min = 1;
        for( int i = min; i < 9; i++ )
        {
            int 
                max = 1 << i;
            for( int j = min; j < max; j++ )
            {
                table[ j ] = 9 - i;
            }
            min = max;
        }
    }
    
    /*
        Returns on interval [0 (error), 32 (LSB)]   
    */
    
    int get_first_available_channel( unsigned channels )
    {
        static unsigned char 
            table[ 256 ];
        static int 
            unused = initialize_table( table );
        int 
            index = table[ channels >> 24 ];
        if( index )
            return index;
        index = table[ ( channels >> 16 ) & 0xff ];
        if( index )
            return index + 8;
        index = table[ ( channels >> 8 ) & 0xff ];
        if( index )
            return index + 16;
        index = table[ channels & 0xff ];
        if( index )
            return index + 24;
        return 0;    
    }
    For the sake of simplicity I assumed 32 bit integers...
    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;
    }

  6. #66
    Registered User
    Join Date
    May 2008
    Location
    India
    Posts
    30
    Quote Originally Posted by slingerland3g View Post
    Lol, this discussion took all kinds of turns. The OP needed to know the first MSB set to decide on the lowest numbered channel available. I believe I am clear now, but there was mention that the rest of the bits or bytes were to be summed up and added to the result, though not clear on what that was to achieve.

    That computing trailing zeros howto was real interesting.
    What I meant was if suppose four bytes has the value say x'00558844'. So I will take the first byte(from the left), x'00'. Since it is zero I will add 8 to the result and now go with second byte x'55'. Use the lookup table suggested by LaserLight and add to the result. That would be the final.

    There would be an exception.If all the bytes are 0, then no channel free.

    This is why I thought to be the fastest, when compared to binary log.

    Code:
    int binlog(unsigned int n) {
      int res = 0;
      if (n >= 1<<16) { n >>= 16; res += 16; }
      if (n >= 1<< 8) { n >>=  8; res +=  8; }
      if (n >= 1<< 4) { n >>=  4; res +=  4; }
      if (n >= 1<< 2) { n >>=  2; res +=  2; }
      if (n >= 1<< 1) { res +=  1; }
      return  ((n == 0) ? (-1) : res);
    subtract from 32 if the result is not -1
    Last edited by chakra; 05-28-2009 at 07:34 PM.

  7. #67
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    int log( unsigned int n )
    {
        return n == 0   ?                         -1 :
            n     < 257 ?      LUT[  n      & 0xFF ] :
            n>>8  < 257 ?  8 + LUT[ (n>> 8) & 0xFF ] :
            n>>16 < 257 ? 16 + LUT[ (n>>16) & 0xFF ] :
                          24 + LUT[ (n>>24) & 0xFF ] ;
    }
    You'll always have a zero check. Beyond that:

    Zero check.
    Less than check.
    Shift, less than.
    Shift, less than.
    Shift, add, AND, LUT.

    Ten..damn I keep forgetting something...maximum operations? Should end up a few shorter than your last post.


    Quzah.
    Last edited by quzah; 05-28-2009 at 07:51 PM.
    Hope is the first step on the road to disappointment.

  8. #68
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by Sebastiani View Post
    Well, after running a few tests, it appears that the lookup table method is probably the fastest route (roughly 10 times faster than the bit-by-bit and ceil/log2 (I'm not sure if this could be optimized for integers, though) approaches).
    Hmm! IBTD

  9. #69
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> IBTD

    How so?

    >> Ten..damn I keep forgetting something...maximum operations? Should end up a few shorter than your last post.

    You could optimize out the two comparison shifts by replacing them with straight compares (ie: 0x10000 and 0x100000).
    Last edited by Sebastiani; 05-28-2009 at 10:22 PM.
    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. #70
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    I too did some testing and the results were nearly identical off only by a hundreths of a second.
    Not sure how you're getting an order of magnitude improvement with the LUT/bit-shifting/bit-masking approach.

    Edit: this ofcourse is w/o any optimization

  11. #71
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    No optimizations, but after cleaning the code up somewhat the bit-by-bit approach was twice as fast as before, but still much slower than the lookup table. Here's a crude test program that should be easy to compile:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h>
    
    #define array_size( array ) ( sizeof( array ) / sizeof( array[ 0 ] ) )
    
    int initialize_table( unsigned char table[ 256 ] )
    {
    	table[ 0 ] = 0;
    	int
    		min = 1;
    	for( int index = min; index < 9; index++ )
    	{
    		int 
    			max = 1 << index;
    		for( int j = min; j < max; j++ )
    		{
    			table[ j ] = 9 - index;
    		}
    		min = max;
    	}
    }
    
    int get_first_available_channel_table_lookup( unsigned channels )
    {
    	static unsigned char 
    		table[ 256 ];
    	static int 
    		unused = initialize_table( table );
    	return 
    		channels == 0 ? 0 
    		: channels < 0x100 ? table[ channels & 0xff ] + 24
    		: channels < 0x10000 ? table[ ( channels >> 8 ) & 0xff ] + 16
    		: channels < 0x1000000 ? table[ ( channels >> 16 ) & 0xff ] + 8
    		: table[ ( channels >> 24 ) & 0xff ];
    }
    
    int get_first_available_channel_ceil_log( unsigned channels )
    {
    	int
    		index = ( int )ceil( log2( channels + 1 ) );
    	return index ? 33 - index : 0;	
    }
    
    int get_first_available_channel_bit_by_bit( unsigned channels )
    {   
    	for( unsigned index = 1, mask = 0x80000000; mask; mask >>= 1, index++ )
    	{
    		if( channels & mask )
    			return index;
    	}		
    	return 0;
    }
    
    typedef int ( * get_first_available_channel_function )( unsigned );
    
    void test( unsigned* values, size_t length, const char* name, get_first_available_channel_function function, size_t repetitions )
    {
    	size_t
    		iterations = repetitions * length;	
    	unsigned
    		* v, 
    		* e = values + length;
    	clock_t
    		elapsed,
    		stop,
    		start = clock( );
    	while( repetitions-- )
    	{	
    		v = values;
    		while( v != e )
    		{
    			function( *v++ );
    		}
    	}	
    	stop = clock( );
    	elapsed = ( clock_t )( ( ( double ) ( stop - start ) / ( double )CLK_TCK ) * 1000 );
    	printf( "%s : %d iterations performed in %d milliseconds\n", name, iterations, ( size_t )elapsed );
    } 
    
    int main( void ) 
    { 
    	srand( time( 0 ) );
    	unsigned
    		data[ 256 ];
    	size_t
    		repetitions = 30000, 
    		tests = 10;
    	struct
    	{
    		char* 
    			name;
    		get_first_available_channel_function 
    			function;
    	}
    		functions[ ] = 
    	{
    		{ "ceil_log", get_first_available_channel_ceil_log }, 
    		{ "table_lookup", get_first_available_channel_table_lookup }, 
    		{ "bit_by_bit", get_first_available_channel_bit_by_bit }		
    	};
    	while( tests-- )
    	{	
    		for( int index = 0; index < array_size( data ); ++index )
    		{
    			data[ index ] = rand( );
    		}	
    		for( int index = 0; index < array_size( functions ); ++index )
    		{
    			test( data, array_size( data ), functions[ index ].name, functions[ index ].function, repetitions );
    		}
    	}	
    	return 0;
    }
    Last edited by Sebastiani; 05-28-2009 at 11:12 PM. Reason: tyypos, other corrections
    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;
    }

  12. #72
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,725
    Quote Originally Posted by Sebastiani
    No optimizations, but after cleaning the code up somewhat the bit-by-bit approach was twice as fast as before, but still much slower than the lookup table.
    Optimisations make sense when doing such a comparison, methinks. I think initialize_table() should return void, and you should change this in get_first_available_channel_table_lookup()'s implementation:
    Code:
    static int
        unused = initialize_table( table );
    to:
    Code:
    static int
        unused = 1;
    if( unused )
    {
        initialize_table( table );
        unused = 0;
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #73
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> Optimisations make sense when doing such a comparison, methinks.

    True, but since some compilers fare worse than others in optimizations I was just treating the comparison as "computational complexity" to address the general performance traits of the algorithms. But yes, optimizations could well change the numbers quite a bit (but I'm guessing they wouldn't "turn the tables" on the results, anyway).

    >> I think initialize_table() should return void, and you should change this in get_first_available_channel_table_lookup()'s implementation:

    It's just a kludge to deal with the fact that the language has no facilities for calling a function "statically". Maybe instead of returning an int it could return a dummy object (ie: 'class unused'), but other than that, I really don't see what's wrong with that method. On the other hand, the test-and-set approach is much less appealing, as it unnecessarily performs the test every invocation, and besides that just clutters the function. But I guess it's just a matter of taste.
    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;
    }

  14. #74
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,725
    Quote Originally Posted by Sebastiani
    It's just a kludge to deal with the fact that the language has no facilities for calling a function "statically". Maybe instead of returning an int it could return a dummy object (ie: 'class unused'), but other than that, I really don't see what's wrong with that method. On the other hand, the test-and-set approach is much less appealing, as it unnecessarily performs the test every invocation, and besides that just clutters the function. But I guess it's just a matter of taste.
    The MinGW port of gcc 3.4.5 refused to compile your original code, reporting that the initialiser of the static variable was not constant.
    Last edited by laserlight; 05-29-2009 at 12:38 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #75
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    How about the BSR instruction? Or through GCC intrinsics:
    Code:
    int __builtin_clz (unsigned int x)
    Other Builtins - Using the GNU Compiler Collection (GCC)

    GCC will choose the best implementation for your architecture (probably just an asm instruction on x86, and software emulation for architectures that don't have this instruction).

    There's probably something like that for MSVC.

Page 5 of 6 FirstFirst 123456 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 12:48 PM
  2. SDLKey to ASCII without unicode support?
    By zacs7 in forum Game Programming
    Replies: 6
    Last Post: 10-07-2007, 03:03 AM
  3. trying to convert system bytes into bits and nibbles.
    By kraze_505 in forum C Programming
    Replies: 11
    Last Post: 01-25-2006, 01:27 AM
  4. Bits & Bytes
    By C of Green in forum C++ Programming
    Replies: 8
    Last Post: 06-21-2002, 06:50 PM
  5. Bits, Bytes & Nibbles!
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 10-13-2001, 10:22 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21