# efficient approach to check a set bit

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

1. ### sanjibGuest

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

Regards
Sanjib

sanjib, Dec 4, 2009

2. ### Riccardo ManfrinGuest

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

3. ### Ben BacarisseGuest

"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
4. ### Mark DickinsonGuest

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
5. ### mohangupta13Guest

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
6. ### sanjibGuest

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

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

>
> - Show quoted text -

Hi Paul
technique for this.(I am Still a learner)

sanjib

sanjib, Dec 4, 2009
7. ### Richard BosGuest

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
8. ### bartcGuest

"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
9. ### Antoninus TwinkGuest

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

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
10. ### Ben BacarisseGuest

(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
11. ### WillemGuest

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
12. ### Antoninus TwinkGuest

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
13. ### Ben BacarisseGuest

mohangupta13 <> writes:

> 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
14. ### bartcGuest

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

--
bartc

bartc, Dec 4, 2009
15. ### Mark DickinsonGuest

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
16. ### Mark DickinsonGuest

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
>
> 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
17. ### Beej JorgensenGuest

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

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
18. ### Ben BacarisseGuest

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
>>
>> 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
19. ### Antoninus TwinkGuest

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

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
20. ### Beej JorgensenGuest

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