Velocity Reviews > efficient approach to check a set bit

# efficient approach to check a set bit

sanjib
Guest
Posts: n/a

 12-04-2009
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

Riccardo Manfrin
Guest
Posts: n/a

 12-04-2009
>> 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 [left]
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
Guest
Posts: n/a

 12-04-2009
"Paul" <-> writes:

> "sanjib" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> 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.

Mark Dickinson
Guest
Posts: n/a

 12-04-2009
On Dec 4, 9:16*am, "Paul" <-> wrote:
> "sanjib" <(E-Mail Removed)> 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

mohangupta13
Guest
Posts: n/a

 12-04-2009
On Dec 4, 6:48*pm, Ben Bacarisse <(E-Mail Removed)> wrote:
> "Paul" <-> writes:
> > "sanjib" <(E-Mail Removed)> wrote in message
> >news:(E-Mail Removed)....
> >> 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

sanjib
Guest
Posts: n/a

 12-04-2009
On Dec 4, 2:16*pm, "Paul" <-> wrote:
> "sanjib" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
> > 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

Richard Bos
Guest
Posts: n/a

 12-04-2009
Mark Dickinson <(E-Mail Removed)> wrote:

> On Dec 4, 9:16=A0am, "Paul" <-> wrote:
> > "sanjib" <(E-Mail Removed)> 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

bartc
Guest
Posts: n/a

 12-04-2009

"sanjib" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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

Antoninus Twink
Guest
Posts: n/a

 12-04-2009
On 4 Dec 2009 at 16:30, Richard Bos wrote:
> Mark Dickinson <(E-Mail Removed)> 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.

Ben Bacarisse
Guest
Posts: n/a

 12-04-2009
http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Bos) writes:

> Mark Dickinson <(E-Mail Removed)> wrote:
>
>> On Dec 4, 9:16=A0am, "Paul" <-> wrote:
>> > "sanjib" <(E-Mail Removed)> 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.