efficient approach to check a set bit

[sanjib]

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

 

[Riccardo Manfrin]

1. What might be an efficient and fastest way to check set bits of an
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​

 

[Ben Bacarisse]

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

 

[Mark Dickinson]

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.

 

[mohangupta13]

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 can you kindly explain how all this stuff
is working, it looks quite arcane to me (still a young programmer ).
Thanks
Mohan

 

[sanjib]

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.







- 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

 

[Richard Bos]

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

 

[bartc]

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!

 

[Antoninus Twink]

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.

 

[Ben Bacarisse]

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

 

[Willem]

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

 

[Antoninus Twink]

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.

 

[Ben Bacarisse]

[asking for an explanation...]

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.

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

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.

 

[bartc]

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.

 

[Mark Dickinson]

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

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

 

[Beej Jorgensen]

- 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

 

[Ben Bacarisse]

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.

 

[Antoninus Twink]

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.

 

[Beej Jorgensen]

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