efficient approach to check a set bit

Discussion in 'C Programming' started by sanjib, Dec 4, 2009.

  1. sanjib

    sanjib Guest

    Friends,
    I need a help to clear about following query. Seeking the help from
    the group to solve and clear my doubts.

    1. What might be an efficient and fastest way to check set bits of an
    integer ? Suppose I have one bit set out of 32 bits of an integer.
    (I can think of K&R approach i.e. based on iterations which is
    equal to the no of set bits in an integer.)


    Thanks in advanced

    Regards
    Sanjib
     
    sanjib, Dec 4, 2009
    #1
    1. Advertising

  2. >> 1. What might be an efficient and fastest way to check set bits of an
    >> integer ? Suppose I have one bit set out of 32 bits of an integer.
    >> (I can think of K&R approach i.e. based on iterations which is
    >> equal to the no of set bits in an integer.)


    From a theoretical point of view:
    you're searching withing a sparse space (an array in this case). Lots of
    methods exist to do the job.
    What comes to my mind is adaptations of sorting algorithms: e.g.:

    0) N = 16
    1) take your int and shift it by N bits right
    2) is the value > 0 ?
    3) YES => (N = N/2; get back to 1) )
    4) (NO) shift you int by N bits

    5) is the value > 0 ?
    6) YES => (N = N/2; get back to 4) )

    Pseudocode errors aside, summing up all the shifts you get to the
    position of the set bit within less than log2(32) = 5 checks...
    Or maybe I'm just saying bullshit as usual.. at least I tried ;)
    R​
     
    Riccardo Manfrin, Dec 4, 2009
    #2
    1. Advertising

  3. "Paul" <-> writes:

    > "sanjib" <> wrote in message
    > news:...
    >> Friends,
    >> I need a help to clear about following query. Seeking the help from
    >> the group to solve and clear my doubts.
    >>
    >> 1. What might be an efficient and fastest way to check set bits of an
    >> integer ? Suppose I have one bit set out of 32 bits of an integer.
    >> (I can think of K&R approach i.e. based on iterations which is
    >> equal to the no of set bits in an integer.)

    >
    > If you definitely only have one bit set, you could try using a switch/
    > case, and hope that the compiler makes it a fast one.


    If there really is only one bit set another possibility is:

    int bit_set(uint32_t x)
    {
    return !(0x55555555 & x) +
    (!(0x33333333 & x) << 1) +
    (!(0x0f0f0f0f & x) << 2) +
    (!(0x00ff00ff & x) << 3) +
    (!(0x0000ffff & x) << 4);
    }

    but i don't think that is what the OP wants. I think they want to
    iterate through all the 1s in an unsigned int (well, lets hope it's
    unsigned). I think the K&R reference might be to using x & (~x + 1).
    The two can be combined of course to print the numbers corresponding
    to bits set:

    while (x) {
    uint32_t low_bit = x & (~x + 1);
    printf(" %d", bit_set(low_bit));
    x &= ~low_bit;
    }

    --
    Ben.
     
    Ben Bacarisse, Dec 4, 2009
    #3
  4. On Dec 4, 9:16 am, "Paul" <-> wrote:
    > "sanjib" <> wrote in message
    > > 1. What might be an efficient and fastest way to check set bits of an
    > > integer ? Suppose I have one bit set out of 32 bits of an integer.
    > >   (I can think of K&R approach i.e. based on iterations which is
    > > equal to the no of set bits in an integer.)

    >
    > If you definitely only have one bit set, you could try using a switch/
    > case, and hope that the compiler makes it a fast one.


    From the evil tricks department, assuming you really do have exactly
    one bit set: the values 1, 2, 4, ..., 1<<31 are all distinct modulo
    37,
    so simply reduce modulo 37 and then use a lookup table.

    --
    Mark
     
    Mark Dickinson, Dec 4, 2009
    #4
  5. sanjib

    mohangupta13 Guest

    On Dec 4, 6:48 pm, Ben Bacarisse <> wrote:
    > "Paul" <-> writes:
    > > "sanjib" <> wrote in message
    > >news:....
    > >> Friends,
    > >>   I need a help to clear about following query. Seeking the help from
    > >> the group to solve and clear my doubts.

    >
    > >> 1. What might be an efficient and fastest way to check set bits of an
    > >> integer ? Suppose I have one bit set out of 32 bits of an integer.
    > >>   (I can think of K&R approach i.e. based on iterations which is
    > >> equal to the no of set bits in an integer.)

    >
    > > If you definitely only have one bit set, you could try using a switch/
    > > case, and hope that the compiler makes it a fast one.

    >
    > If there really is only one bit set another possibility is:
    >
    >   int bit_set(uint32_t x)
    >   {
    >        return  !(0x55555555 & x)       +
    >               (!(0x33333333 & x) << 1) +
    >               (!(0x0f0f0f0f & x) << 2) +
    >               (!(0x00ff00ff & x) << 3) +
    >               (!(0x0000ffff & x) << 4);
    >   }
    >
    > but i don't think that is what the OP wants.  I think they want to
    > iterate through all the 1s in an unsigned int (well, lets hope it's
    > unsigned).  I think the K&R reference might be to using x & (~x + 1).
    > The two can be combined of course to print the numbers corresponding
    > to bits set:
    >
    >      while (x) {
    >           uint32_t low_bit = x & (~x + 1);
    >           printf(" %d", bit_set(low_bit));
    >           x &= ~low_bit;
    >      }
    >
    > --
    > Ben.

    Ben can you kindly explain how all this stuff
    is working, it looks quite arcane to me (still a young programmer ).
    Thanks
    Mohan
     
    mohangupta13, Dec 4, 2009
    #5
  6. sanjib

    sanjib Guest

    On Dec 4, 2:16 pm, "Paul" <-> wrote:
    > "sanjib" <> wrote in message
    >
    > news:...
    >
    > > Friends,
    > >   I need a help to clear about following query. Seeking the help from
    > > the group to solve and clear my doubts.

    >
    > > 1. What might be an efficient and fastest way to check set bits of an
    > > integer ? Suppose I have one bit set out of 32 bits of an integer.
    > >   (I can think of K&R approach i.e. based on iterations which is
    > > equal to the no of set bits in an integer.)

    >
    > If you definitely only have one bit set, you could try using a switch/
    > case, and hope that the compiler makes it a fast one.
    >
    > Otherwise, you could try some sort of binary search, or perhaps
    > cast  to an array of four bytes and check each one is not zero,
    > before you loop through it.
    >
    > I'm not sure this saves much time for a 32 bit integer though.
    >
    > P.
    >
    >
    >
    >
    >
    > > Thanks in advanced

    >
    > > Regards
    > > Sanjib- Hide quoted text -

    >
    > - Show quoted text -


    Hi Paul
    Will you please kindly explain about the use of binary search
    technique for this.(I am Still a learner)
    Thanks in advanced.

    sanjib
     
    sanjib, Dec 4, 2009
    #6
  7. sanjib

    Richard Bos Guest

    Mark Dickinson <> wrote:

    > On Dec 4, 9:16=A0am, "Paul" <-> wrote:
    > > "sanjib" <> wrote in message
    > > > 1. What might be an efficient and fastest way to check set bits of an
    > > > integer ? Suppose I have one bit set out of 32 bits of an integer.
    > > > =A0 (I can think of K&R approach i.e. based on iterations which is
    > > > equal to the no of set bits in an integer.)

    > >
    > > If you definitely only have one bit set, you could try using a switch/
    > > case, and hope that the compiler makes it a fast one.

    >
    > From the evil tricks department, assuming you really do have exactly
    > one bit set: the values 1, 2, 4, ..., 1<<31 are all distinct modulo
    > 37, so simply reduce modulo 37 and then use a lookup table.


    That's a _very_ evil trick. I like it.

    Richard
     
    Richard Bos, Dec 4, 2009
    #7
  8. sanjib

    bartc Guest

    "sanjib" <> wrote in message
    news:...
    > Friends,
    > I need a help to clear about following query. Seeking the help from
    > the group to solve and clear my doubts.
    >
    > 1. What might be an efficient and fastest way to check set bits of an
    > integer ? Suppose I have one bit set out of 32 bits of an integer.
    > (I can think of K&R approach i.e. based on iterations which is
    > equal to the no of set bits in an integer.)


    This is another approach if you have an integer that you know has exactly 1
    bit set:

    #include <math.h>
    int findsetbit(unsigned int a) {
    static double ilg2=1.0/log(2);
    return round(log(a)*ilg2);
    }

    I doubt it's fast or efficient though.

    Will the number in general have any number of bits set?

    And how do you want the results presented? Anything involving an array will
    probably require more work in setting up and traversing, let alone doing
    anything with the information, than simply shifting and masking the integer
    to get at the positions.

    Probably the most compact way of recording the bit positions is to use a map
    of '1' bits; in other words, do nothing!

    --
    Bartc
     
    bartc, Dec 4, 2009
    #8
  9. On 4 Dec 2009 at 16:30, Richard Bos wrote:
    > Mark Dickinson <> wrote:
    >> From the evil tricks department, assuming you really do have exactly
    >> one bit set: the values 1, 2, 4, ..., 1<<31 are all distinct modulo
    >> 37, so simply reduce modulo 37 and then use a lookup table.

    >
    > That's a _very_ evil trick. I like it.


    It's all very clever - great if you're looking to impress geeky chicks
    - but in practice I'd be extremely surprised if it beats Ben
    Becarisse's bit-twiddling solution, which just has a few ands, shifts
    and adds.

    Even if you're doing lots of these at once, so that the LUT will usually
    be available in cache, an integer division and a memory access will
    probably be expensive compared to a dozen or so basic arithmetic and
    logical operations.
     
    Antoninus Twink, Dec 4, 2009
    #9
  10. (Richard Bos) writes:

    > Mark Dickinson <> wrote:
    >
    >> On Dec 4, 9:16=A0am, "Paul" <-> wrote:
    >> > "sanjib" <> wrote in message
    >> > > 1. What might be an efficient and fastest way to check set bits of an
    >> > > integer ? Suppose I have one bit set out of 32 bits of an integer.
    >> > > =A0 (I can think of K&R approach i.e. based on iterations which is
    >> > > equal to the no of set bits in an integer.)
    >> >
    >> > If you definitely only have one bit set, you could try using a switch/
    >> > case, and hope that the compiler makes it a fast one.

    >>
    >> From the evil tricks department, assuming you really do have exactly
    >> one bit set: the values 1, 2, 4, ..., 1<<31 are all distinct modulo
    >> 37, so simply reduce modulo 37 and then use a lookup table.

    >
    > That's a _very_ evil trick. I like it.


    And, as it happens, if you need to do the same for 64 bits, the
    smallest modulus is 67 -- the 7 making both 37 and 67 reasonably easy
    to remember.

    In case anyone cares, the array contents would be:

    0, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
    4, 0, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 47,
    5, 32, 0, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 29, 50,
    43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, 7, 48, 35,
    6, 34, 33

    --
    Ben.
     
    Ben Bacarisse, Dec 4, 2009
    #10
  11. sanjib

    Willem Guest

    Ben Bacarisse wrote:
    ) And, as it happens, if you need to do the same for 64 bits, the
    ) smallest modulus is 67 -- the 7 making both 37 and 67 reasonably easy
    ) to remember.

    Question for the mathematically inclined: Does it work iff the
    modulus has no factors smaller than the number of bits you need ?


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Dec 4, 2009
    #11
  12. On 4 Dec 2009 at 18:22, Willem wrote:
    > Question for the mathematically inclined: Does it work iff the
    > modulus has no factors smaller than the number of bits you need ?


    What do you mean by "it"?

    The "trick" is: given k, find a small integer m such that 1, 2, 4, ...,
    2^k all have distinct reductions modulo m. Such an m always exists, of
    course (e.g. m = 2^k is a not very helpful example).

    Is your question when m can be chosen to be not much larger than k, as
    in the k = 31 and k = 63 examples in this thread? I don't immediately
    see a way to make a statement along those lines that's both precise and
    meaningful.
     
    Antoninus Twink, Dec 4, 2009
    #12
  13. mohangupta13 <> writes:

    [asking for an explanation...]

    > On Dec 4, 6:48 pm, Ben Bacarisse <> wrote:
    >> "Paul" <-> writes:
    >> > "sanjib" <> wrote in message
    >> >news:...
    >> >> Friends,
    >> >>   I need a help to clear about following query. Seeking the help from
    >> >> the group to solve and clear my doubts.

    >>
    >> >> 1. What might be an efficient and fastest way to check set bits of an
    >> >> integer ? Suppose I have one bit set out of 32 bits of an integer.
    >> >>   (I can think of K&R approach i.e. based on iterations which is
    >> >> equal to the no of set bits in an integer.)

    >>
    >> > If you definitely only have one bit set, you could try using a switch/
    >> > case, and hope that the compiler makes it a fast one.

    >>
    >> If there really is only one bit set another possibility is:
    >>
    >>   int bit_set(uint32_t x)
    >>   {
    >>        return  !(0x55555555 & x)       +
    >>               (!(0x33333333 & x) << 1) +
    >>               (!(0x0f0f0f0f & x) << 2) +
    >>               (!(0x00ff00ff & x) << 3) +
    >>               (!(0x0000ffff & x) << 4);
    >>   }


    This is, in essence, the binary search that has been described in
    words but with the loop unrolled.

    Start with the last term. 0x0000ffff & x is non zero when the bit in
    x is in the bottom half. The ! inverts this test and gives 1 when the
    bit is in the top half and 0 otherwise. The << 4 turn this 1/0 into
    16 or 0 and, lo, all this xs whose bit is in the top half should
    return a number > 16.

    The previous term does the same but looking for the bit in the top
    half of either half. The result being to add 8 or 0 to the sum
    depending on which quart of the bits the single set bit is in.

    Each of the other terms adds another component to the sum depending on
    finer and finder details about position of the bit we are looking for.

    >> but i don't think that is what the OP wants.  I think they want to
    >> iterate through all the 1s in an unsigned int (well, lets hope it's
    >> unsigned).  I think the K&R reference might be to using x & (~x + 1).
    >> The two can be combined of course to print the numbers corresponding
    >> to bits set:
    >>
    >>      while (x) {
    >>           uint32_t low_bit = x & (~x + 1);
    >>           printf(" %d", bit_set(low_bit));
    >>           x &= ~low_bit;
    >>      }


    ~x flips all the (value) bits in the unsigned int. A run on zeros at
    the least significant end of x turns into a run of 1s. For example,
    if x is 100011000, ~x is 011100111. Adding 1 to this will put the
    zeros back again and leave a 1 where the least significant bit was
    set: 011101000. The "and" of x and this value will have only one bit
    set -- the least significant one: 000001000. After printing the
    positional number of this bit (3) the x &= ~low_bit clears that bit
    from x (~low_bit == 111110111 so x & ~low_bit is 100010000) so the
    loop can then find the next least significant bit.

    <snip>
    > Ben can you kindly explain how all this stuff
    > is working, it looks quite arcane to me (still a young programmer ).


    I hope that helps.

    --
    Ben.
     
    Ben Bacarisse, Dec 4, 2009
    #13
  14. sanjib

    bartc Guest

    "Antoninus Twink" <> wrote in message
    news:...
    > On 4 Dec 2009 at 16:30, Richard Bos wrote:
    >> Mark Dickinson <> wrote:
    >>> From the evil tricks department, assuming you really do have exactly
    >>> one bit set: the values 1, 2, 4, ..., 1<<31 are all distinct modulo
    >>> 37, so simply reduce modulo 37 and then use a lookup table.

    >>
    >> That's a _very_ evil trick. I like it.

    >
    > It's all very clever - great if you're looking to impress geeky chicks
    > - but in practice I'd be extremely surprised if it beats Ben
    > Becarisse's bit-twiddling solution, which just has a few ands, shifts
    > and adds.
    >
    > Even if you're doing lots of these at once, so that the LUT will usually
    > be available in cache, an integer division and a memory access will
    > probably be expensive compared to a dozen or so basic arithmetic and
    > logical operations.


    On my machine the modulo 37 method was 2 to 5 times as slow as the shift and
    mask one.

    --
    bartc
     
    bartc, Dec 4, 2009
    #14
  15. On Dec 4, 6:22 pm, Willem <> wrote:
    > Ben Bacarisse wrote:
    >
    > ) And, as it happens, if you need to do the same for 64 bits, the
    > ) smallest modulus is 67 -- the 7 making both 37 and 67 reasonably easy
    > ) to remember.
    >
    > Question for the mathematically inclined: Does it work iff the
    > modulus has no factors smaller than the number of bits you need ?


    No. As an example, there are only 20 distinct powers of 2 modulo 41,
    so this wouldn't work if 37 were replaced with 41.

    For 1, 2, 4, ..., 2^(n-1) to be distinct modulo p all you need is that
    the order of 2 modulo p is at least n. A nice sufficient condition is
    that p is a prime > n and 2 is a primitive root modulo p (in other
    words, 1, 2, ..., 2^(p-1) are all distinct modulo p). Since
    (conjecturally) around 37.4% of primes p have this property[1], you
    generally don't have to look very far beyond n before finding one.

    --
    Mark

    [1] http://en.wikipedia.org/wiki/Artin's_conjecture_on_primitive_roots
     
    Mark Dickinson, Dec 4, 2009
    #15
  16. On Dec 4, 5:40 pm, Antoninus Twink <> wrote:
    > It's all very clever  - great if you're looking to impress geeky chicks
    > - but in practice I'd be extremely surprised if it beats Ben
    > Becarisse's bit-twiddling solution, which just has a few ands, shifts
    > and adds.
    >
    > Even if you're doing lots of these at once, so that the LUT will usually
    > be available in cache, an integer division and a memory access will
    > probably be expensive compared to a dozen or so basic arithmetic and
    > logical operations.


    Hmm, yes. Oh well. I'll file it in the 'fun but useless' folder,
    then.

    Mark
     
    Mark Dickinson, Dec 4, 2009
    #16
  17. Antoninus Twink <> wrote:
    >- but in practice I'd be extremely surprised if it beats Ben
    >Becarisse's bit-twiddling solution, which just has a few ands, shifts
    >and adds.


    Relative runtimes on a quick-and-dirty benchmark on my Athlon64 (I'm
    presuming the LUT was cached):

    unoptimized -O2
    Ben: 1.0 1.0
    Mod37: 1.4 0.7

    Looking at the assembly, gcc replaced the mod 37 with some hacker
    goodies (not a div).

    -Beej
     
    Beej Jorgensen, Dec 4, 2009
    #17
  18. Mark Dickinson <> writes:

    > On Dec 4, 5:40 pm, Antoninus Twink <> wrote:
    >> It's all very clever  - great if you're looking to impress geeky chicks
    >> - but in practice I'd be extremely surprised if it beats Ben
    >> Becarisse's bit-twiddling solution, which just has a few ands, shifts
    >> and adds.
    >>
    >> Even if you're doing lots of these at once, so that the LUT will usually
    >> be available in cache, an integer division and a memory access will
    >> probably be expensive compared to a dozen or so basic arithmetic and
    >> logical operations.

    >
    > Hmm, yes. Oh well. I'll file it in the 'fun but useless' folder,
    > then.


    I timed my bit-twiddling version against the mod 37 table look-up
    solution and mine was (almost) a factor of 2 slower on a x86_64 laptop
    (gcc 4.4.1). The look-up was faster by the same factor at various
    optimisation levels.

    --
    Ben.
     
    Ben Bacarisse, Dec 4, 2009
    #18
  19. On 4 Dec 2009 at 21:33, Beej Jorgensen wrote:
    > unoptimized -O2
    > Ben: 1.0 1.0
    > Mod37: 1.4 0.7
    >
    > Looking at the assembly, gcc replaced the mod 37 with some hacker
    > goodies (not a div).


    Clever old gcc!

    If it was doing an integer division (as it surely is in the unoptimized
    version), that's probably 50 cycles plus, which would easily outweigh
    Ben's few masks and shifts.

    Assuming your test consists of calling the routine thousands of times in
    succession, the LUT will easily fit in L1 cache, so we're only talking a
    couple of cycles for each memory access once it's been cached the first
    time.
     
    Antoninus Twink, Dec 4, 2009
    #19
  20. Antoninus Twink <> wrote:
    >If it was doing an integer division (as it surely is in the unoptimized
    >version)


    There's a mult in the unoptimized version, but surprisingly no div.
    My x86-fu is weak, so I can't really decode it, but I know there are no
    DIVs in there. :) Lotsa moves, a mult, four shifts, two adds, and two
    subtracts.

    Most fun is the use of the constant 0xBACF914D in the mod calculation.
    They multiply that by the value to lookup, and discard the low 32-bits
    of the result. Then from that they subtract the value to lookup, and
    shift the result right by one. From there, things start to get strange,
    until, 11 instructions later, they magically end up with an index into
    the lookup table.

    In short, I'm very glad that people specialize in exactly this thing. :)

    >Assuming your test consists of calling the routine thousands of times in
    >succession, the LUT will easily fit in L1 cache, so we're only talking a
    >couple of cycles for each memory access once it's been cached the first
    >time.


    Yup.

    -Beej
     
    Beej Jorgensen, Dec 5, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    1,855
    Timothy Bendfelt
    Jan 19, 2007
  2. July
    Replies:
    2
    Views:
    286
    msalters
    Jul 18, 2005
  3. Replies:
    9
    Views:
    1,049
    Juha Nieminen
    Aug 22, 2007
  4. Jeff.M
    Replies:
    6
    Views:
    204
    Lasse Reichstein Nielsen
    May 4, 2009
  5. prati
    Replies:
    0
    Views:
    501
    prati
    Oct 27, 2012
Loading...

Share This Page