Thread: Am I missing something here? (Calculation issue)

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    161

    Am I missing something here? (Calculation issue)

    Ok. Let's say I have an integer (X = 0x01000000) and I want to know which bit is active (1-32 or 0-32 depending on how you're counting). There's always only 1 bit active. Is there some equation I could use to do it? The only things I can think of involve looping. I would've thought there's a faster way to reduce it down through shifting or something. I just can't come up with it.

  2. #2
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    Suppose you want to know which bit is active in a character:
    Code:
    int main () {
      char data = 0x08, 
           mask = 0x01, 
           i    = 1;
    
    
      for( mask=0x01; mask; mask<<=1, i++ ) { /* mask is left shifted until the 1 has gone out of its scope */
        if ( mask & data ) { /* note bitwise and here. Not logical */
          printf( "bit &#37;d (or %d) is 1", i, i-1 ); /* depending on how you count */
        }
      }
    
      return 0;
    }
    Simply apply this to an integer and it should work.
    Last edited by twomers; 09-29-2008 at 02:31 PM.

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    161
    I knew I could do it with a loop like that. I was hoping there was a better way with less processing time involved, because this is already being done in a loop that takes a long time.
    Last edited by Viper187; 09-29-2008 at 03:02 PM.

  4. #4
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    If you're that concerned with time do a binary search...
    Code:
    inline int which_bit( char mydata ) {
      if ( mydata & 0x0F ) // in upper half
        if ( mydata & 0x03 ) // lower quarter
          if ( mydata & 0x01 ) 
            return 1;// first bit
          else 
            return 2; // second bit
    
        else // second quarter
          if ( mydata & 0x04 )
            return 3; // third bit
          else 
            return 4; // fourth bit
    
      else // in lower half
        if ( mydata & 0x30 ) // third quarter
          if ( mydata & 0x10 ) 
            return 5;// fifth bit
          else 
            return 6; // sixth bit
    
        else // last quarter
          if ( mydata & 0x40 )
            return 7; // seventh bit
          else 
            return 8; // eighth bit
    
      return 0xFF;
    }
    
    int main () {
      char data = 0x01;
      printf( "Bit #&#37;d", which_bit( data ) );  
    
      return 0;
    }
    It's up to you to expand it to an int.
    Last edited by twomers; 09-29-2008 at 03:42 PM.

  5. #5
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Why are you so concerned with the time it takes to iterate through this loop? Not to mention that most modern optimizers are fully capable of unrolling the loop in a similar fashion to twomers code. I think the real question that comes to mind when reading this thread is whether twomers name is pronounced like tumors or twom-ers. Random... but that is just how my brain works.

  6. #6
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    I'm bored, so here's a solution (assuming a 4-byte int)
    Code:
    inline int which_bit_char( const char mydata ) {
      if ( mydata & 0x0F ) // in upper half
        if ( mydata & 0x03 ) // lower quarter
          if ( mydata & 0x01 ) 
            return 1;// first bit
          else 
            return 2; // second bit
    
        else // second quarter
          if ( mydata & 0x04 )
            return 3; // third bit
          else 
            return 4; // fourth bit
    
      else // in lower half
        if ( mydata & 0x30 )
          if ( mydata & 0x10 ) 
            return 5;// fifth bit
          else 
            return 6; // sixth bit
    
        else // second quarter
          if ( mydata & 0x40 )
            return 7; // seventh bit
          else 
            return 8; // eighth bit
    
      return 0;
    }
    
    inline int which_bit_int( int mydata ) {
      if ( !mydata )
        return 0;
    
      if ( mydata & 0x0000FFFF ) 
        if ( mydata & 0x000000FF )
          return which_bit_char( (char)mydata );
        else
          return 8 + which_bit_char( (char)(mydata>>8) );
      else 
        if ( mydata & 0xFFFF0000 )
          if ( mydata & 0x00FF0000 )
            return 16 + which_bit_char( (char)(mydata>>16) );
          else 
            return 24 + which_bit_char( (char)(mydata>>24) );
    }
    
    int main () {  
      int mynum = 0x00400;
      printf( "Bit #&#37;d", which_bit_int( mynum ) ); 
    
      return 0;
    }
    I'm really bored today. Run this and lemme know what you get
    Code:
    #include <stdio.h>
    #include <time.h>
    int main () {  
      double bin_time = 0, for_time = 0;
    
      for ( int k=0; k<10; k++ ) {
        {
          clock_t start, end;
          start = clock();
    
          unsigned int num = 0, mask=1, i=1;
          for ( unsigned int j=0; j<0xfffffff; j++ )
            for ( num=mask; num; mask<<=1, num=mask, i++ )
              which_bit_int( num );
    
          end = clock();
          bin_time += (double)( end - start ) / (double)CLOCKS_PER_SEC;
    
          printf ( "Binary Search: %f seconds\n",
            (double)( end - start ) / (double)CLOCKS_PER_SEC );
    
        }
    
    
        
        {
          clock_t start, end;
          start = clock();
    
          unsigned int num = 0, mask=1, i=1;
          for ( unsigned int j=0; j<0xfffffff; j++ )
            for ( num=mask; num; mask<<=1, num=mask, i++ ) 
              for ( unsigned int mmask=1; mmask; mmask<<=1 )
                if ( num & mmask )
                  break;
          end = clock();
          for_time += (double)( end - start ) / (double)CLOCKS_PER_SEC;
    
          printf ( "Loop Search: %f seconds\n\n",
            (double)( end - start ) / (double)CLOCKS_PER_SEC );
        }
      }
    
      printf( "total binary time: %f\n", bin_time );
      printf( "total loop time: %f\n", for_time );
    
      return 0;
    }
    for runs faster for me (mostly, it varies). I've optimisers set to fast.

    Edit: I figure the loops must by un-looped, actually. I changed the wrapping for loop to run 1000 times, resulting in 8,321,499,105,000 iterations (maybe. Very back-of-envelope calculation) for both binary and loop searches. My binary search came out in 369.104 seconds and the loop comes out at 368.191... This results in a faster loop-search of about 120fs between per iteration (obviously not really, but with laws of averages 'n' all it is).

    A friend did it without optimisers set for 10 wrapping iterations and got 16.81 and 30.17 seconds for binary and for searches respectively.

    Conclusion -- Optimisers are smart.
    Last edited by twomers; 09-29-2008 at 04:38 PM.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If you really need to do this very quickly, then you could use inline assembler, such as:

    Code:
       __asm {
            xor   ecx, ecx      // ecx = 0
            bsf   eax, data    // First bit from top set into eax
            inc   eax
            cmovz eax, ecx   // Set to zero if there was no bit set. 
       }
    If you are using gcc, it needs to be written slightly differently as to syntax, but the method still works.

    If you have multiple bits, there are two different instructions, bsf and bsr. bsf starts from the highest bit, bsr starts at the lowest bit.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    If you do some reading on the mathematical principles of profiling used in optimizers you will find that they truly do aim to please. Which is why I always suggest letting the optimizer work its magic first, then use its generated assembly code as the basis for your own creation. Surely you have seen terminator. We can't beat the machines.... Or can we?

  9. #9
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    I always heard it, but never investigated the effects. Just doin' what the OP said though. The for loop would have prolly sufficed for me.

  10. #10
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Oh I know. I am just adding in my pedantic narration. It just wouldn't be the same without it, right?

  11. #11
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    matscp: if you really want a fast way why not use Intel's BSF (Bit Scan Forward) or BSR (Bit Scan Reverse) instructions.

  12. #12
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    He did, he used bsf... And mentioned how to use both.

  13. #13
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Sorry. I didn't see.

  14. #14
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    No biggy. No one is out to humiliate you nor point out your every misstep. Its just how it seems sometimes... Too often, if you ask me.

  15. #15
    Registered User
    Join Date
    Jun 2008
    Posts
    161
    Well, I got to thinking. I'm using an Int64 for this, but not all 64 bits are needed for this specific purpose (the rest are needed for others things though). I came up with an idea for a function with a switch() that might serve my purposes. Checking 20 or so cases shouldn't be bad in terms of time, should it?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Errors including <windows.h>
    By jw232 in forum Windows Programming
    Replies: 4
    Last Post: 07-29-2008, 01:29 PM
  2. failure to import external C libraries in C++ project
    By nocturna_gr in forum C++ Programming
    Replies: 3
    Last Post: 12-02-2007, 03:49 PM
  3. more then 100errors in header
    By hallo007 in forum Windows Programming
    Replies: 20
    Last Post: 05-13-2007, 08:26 AM
  4. ras.h errors
    By Trent_Easton in forum Windows Programming
    Replies: 8
    Last Post: 07-15-2005, 10:52 PM
  5. pointer to array of objects of struct
    By undisputed007 in forum C++ Programming
    Replies: 12
    Last Post: 03-02-2004, 04:49 AM