Author: Ricardo Gibert
Date: 16:24:52 04/30/00
Go up one level in this thread
On April 29, 2000 at 16:05:59, KarinsDad wrote:
>Most every programmer knows the simple b & -b to calculate least significant
>bit. However, us run of the mill programmers do not know of a simple way to
>calculate most significant bit.
>
>Is there such a beast?
>
>KarinsDad :)
Here's a puzzle for you:
#include <stdio.h>
#include <assert.h>
int main(void)
{
// compute LSB bit position
int i, x, c = 589944560;
int q[] = {30, 29, 28, 24, 27, 19, 23, 14, 26, 16, 18, 9, 22, 7, 13,
4, 0, 25, 20, 15, 17, 10, 8, 5, 1, 21, 11, 6, 2, 12, 3};
x = 1;
for (i = 0; i < 31; i++)
{
if ((i & 3) == 0) puts("");
assert((x != 0) && (x != 0x80000000));
printf("%11i%3i ", x, q[(c/(x & -x)) & 31]);
x *= 2;
}
return 0;
}
This works for any int x except 0 and 0x80000000. These exceptions are intrinsic
to the "x & -x" method. The array q[] is not strictly necessary in many
applications, so it is possible to speed things up a bit and save a little
space.
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.