Author: KarinsDad
Date: 12:59:57 10/13/99
Go up one level in this thread
On October 13, 1999 at 14:23:53, Landon Rabern wrote:
>What is quick way to get the LSB of a 64 bit unsigned int? If I take n & -n, I
>can clear all the bits except the one that I want. Then I could either do a
>loop shifting right until I got 1 or do a log base 2. These both seem slow, is
>there a faster way?
>
>Thanks,
>
>Landon
I haven't thought about this a lot, but here is a silly idea:
x = n & -n;
y = 1;
count = 0;
while (x > y)
{
x >>= 1;
y <<= 2;
count++;
}
if (y == x)
{
answer = (count * 3);
}
else if (y == (x << 2))
{
answer = (count * 3) - 2;
}
else
{
answer = (count * 3) - 1;
}
What this does is reduce the number of shifts in some of the cases at the
expense of a multiplication (which I think the compiler optimizes in the case of
multiplying by 3) since you are using one variable to shift to the right one and
another to shift to the left two (i.e. approximately a 33% decrease in the
number of shifts).
In any case, I'm sure somebody has thought about this for real, I was just
goofing around here.
KarinsDad :)
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.