Position of the lowest bit
Author
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
log2(x ^ (x - 1)) will give you what you want.
There are other options, tho.
From,
Nice coder
There are other options, tho.
From,
Nice coder
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?
*edit*
What are you storing the binary number in?
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
Author
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
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
Author
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?
Is log2 legal in math.h? If so, does anyone know the time complexity?
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]
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
Author
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
