# Position of the lowest bit

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

## 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 on other sites
log2(x ^ (x - 1)) will give you what you want.

There are other options, tho.

From,
Nice coder

##### Share on other sites
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 on other sites
Quote:
 Original post by Dancin_Foolhmmm 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 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 on other sites
What are you using this for?
DENC

##### 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 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 on other sites
Quote:
 Original post by Frunywhile(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 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

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633705
• Total Posts
3013464
×