Thread: bit value check efficiency

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    bit value check efficiency

    Hello everyone,


    I have a long array (char*) and I need to check which bit is the first bit whose value is 1.

    I have two ways to implement,

    1. Iterate each byte, then iterate each bit in each byte one by one;
    2. Iterate each byte, and check whether the value of the byte itself is non-zero, if yes, then iterate each bit in the byte to find which bit is the first bit which is set to 1, or else skip this byte and continue to iterate next byte.

    I think (2) is always faster, right? But I do not know why (2) is faster since it is just my personal estimation without any concrete basis analysis.


    thanks in advance,
    George

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    char * would be a pointer to a char or char array .

    I'd go with 2 (from bit 0 to CHAR_BIT), especially if you're looking for speed (the loop only runs for the size of the array + n (from non-zero byte to first 'on' bit)). Whereas 2 runs CHAR_BIT * size of the array times.

    1, could look something like;

    Code:
    char longCharArray[] = "stuff and gruff";     /* whatever is supposed to be in here, crummy test data */
    size_t i = 0, b = 0;
    
    /* ... */
    
    for(i = 0; i < sizeof(longCharArray); i++)
    {
        /* non-zero byte */
        if(longCharArray[i] != 0)
        {
            /* find first 'on' bit */
            for(b = 0; b < CHAR_BIT; b++)
            {
                /* http://www.cprogramming.com/tutorial/bitwise_operators.html */
            }
        }
    }
    Last edited by zacs7; 11-04-2007 at 06:26 AM.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Need more information about the expected data.
    Does every bit have a high chance of being set, or...
    Is the data likely to contain long sequences of zeros before a one is found almost every time?

    If each bit has a 50% chance of being set, then checking the whole byte first is useless. So no, number 2 is not always fastest.
    If there are usually about 10 bytes of zeros at the start then checking each bit one at a time would be silly.
    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"

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Note also that there are processor instructions that do things like "find first bit set" from either end of a 32-bit value.

    If this is beyond what you can do [there is no intrinsic function and you don't want to use inline assembler] you could have a table of 256 values that return the highest bit within a byte, rather than checking each individual bit in a loop.
    The table would look something like this:
    Code:
    char array[256] = { -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,  // 0..15
                                    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,   // 16..31
                                    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,   // 32..47
                                    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,   // 48..63
                                    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,   // 64
                                    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,   // .
                                    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,   // .
                                    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,   // 127
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,   // 128
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 }; // 255
    Now, you just have to count the number of bytes and add 8 for each byte, then follow the above table when you hit a non-zero.

    --
    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.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Or you can go with a divide and conquer approach which gives the answer in 3 comparisons.

    Just fill out this idea with the rest of the tests.
    Code:
    if ( c >= 0x10 ) { /* is it in bits 4 to 7 */
      if ( c >= 0x40 ) { /* is it in bits 6 or 7 */
      }
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Branches are often less efficient than memory reads of an array. But it depends on how critical it is...

    --
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BN_CLICKED, change button style
    By bennyandthejets in forum Windows Programming
    Replies: 13
    Last Post: 07-05-2010, 11:42 PM
  2. 32 bit to 64 bit Ubuntu
    By Akkernight in forum Tech Board
    Replies: 15
    Last Post: 11-17-2008, 03:14 AM
  3. Replies: 7
    Last Post: 12-10-2004, 08:18 AM
  4. Copy bit to bit
    By Coder2Die4 in forum C Programming
    Replies: 15
    Last Post: 06-26-2003, 09:58 AM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM