Jump to content
  • Advertisement
Sign in to follow this  
Sagar_Indurkhya

Position of the lowest bit

This topic is 4768 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a binary number, and I'm trying to find the lowest bit: binaryNumber b = 0010000; int i = getLowBit(b); display i; output: i = 2; so if the number is 0100000, I want 1. if it were 00000100 I want 5. I have seen how to do this somewhere when I was investigating bitboards for chess programming, but I can't find it at all! If someone can help me out, I've been trying to figure it out for hours! Thanks - Sagar

Share this post


Link to post
Share on other sites
Advertisement
hmmm there should be someway to set it up using a for loop and some bit shifting.

*edit*

What are you storing the binary number in?

Share this post


Link to post
Share on other sites
Quote:
Original post by Dancin_Fool
hmmm there should be someway to set it up using a for loop and some bit shifting.

*edit*

What are you storing the binary number in?


x ^ (x - 1) will give you the bit. (tho not the bit number, which is what he wants).

The log2 gives him the number.

Sagar_Indurkhya - You don't EVER use the number. Its too costly to put in/out. You store the number, for eg. 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,2048, 4096, 8192, 16364, ect. This means you only need X ^ ( x - 1) rather then having to do heaps of log2's/pow2's.

From,
Nice code4r

Share this post


Link to post
Share on other sites
no what I have right now is:

some integers, represent a set of 13 true false values.

the array numbers(integer)

numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 4;
etc

so what I do is to test the nth bit(see if it is true of false),

i do

for(int i = 0; i < width; i++)
if(numbers[n] & valueImInvestigating)
... do stuff

I then use i.

I want to jump directly to the first 1 in a binary number, so I don't have to waste time searching.

In other words, for a binary number n digits long, I want an operation that is about O(1 or 2 or something low).

I didn't see log2 in math.h

Share this post


Link to post
Share on other sites
This is for training for the USACO, and as long as it doesn't directly relate to the problem, its ok. But this particular problem applies to many different programs where I mess around with bits.

Is log2 legal in math.h? If so, does anyone know the time complexity?

Share this post


Link to post
Share on other sites
while(n>0)
{
low_bit = ((n^(n-1))+1) >> 1;
switch(low_bit)
{
case 1: do_stuff_for_bit_0(); break;
case 2: do_stuff_for_bit_1(); break;
case 4: do_stuff_for_bit_2(); break;
// ...
}
n &= ~low_bit;
}


And actually, to find the least significant bit, using a lookup table isn't unconceivable. The above code is probably more expensive than the naive loop, not to mention the cost of the actual operations you want to do (or not).

[Edited by - Fruny on July 28, 2005 10:22:18 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
while(n>0)
{
low_bit = ((n^(n-1))+1) >> 1;
switch(low_bit)
{
case 1: do_stuff_for_bit_0(); break;
case 2: do_stuff_for_bit_1(); break;
case 4: do_stuff_for_bit_2(); break;
// ...
}
n &= ~low_bit;
}


And actually, to find the least significant bit, using a lookup table isn't unconceivable. The above code is probably more expensive than the naive loop, not to mention the cost of the actual operations you want to do (or not).


1. Just do a bunch of if's. They are faster then what your doing.

2. low_bit = ((n^(n-1))+1) >> 1;
?

Lowbit = n ^ (n - 1);
End of story.

From,
Nice coder

Share this post


Link to post
Share on other sites
Never mind. I figured out better optimizations, and got it done in one second(.9 seconds).

Thanks for the help everybody! If I find that nifty trick again(from the Chess Programming Page), I'll put it up here!

Thanks Again.
- Sagar

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!