Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > efficient approach to check a set bit

Reply
Thread Tools

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


Thanks in advanced

Regards
Sanjib
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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.
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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.
>
>
>
>
>
> > 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
 
Reply With Quote
 
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
 
Reply With Quote
 
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

 
Reply With Quote
 
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
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.

 
Reply With Quote
 
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the point of having 16 bit colour if a computer monitor can only display 8 bit colour? How do you edit 16 bit colour when you can only see 8 bit? Scotius Digital Photography 6 07-13-2010 03:33 AM
efficient approach to reverse a std::string object July C++ 2 07-18-2005 12:07 PM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit, Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new ! vvcd Computer Support 0 09-17-2004 08:15 PM
Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there better approach? mrhicks C Programming 3 09-01-2004 06:01 AM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit,Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new! Ionizer Computer Support 1 01-01-2004 07:27 PM



Advertisments