Author: Miguel A. Ballicora
Date: 00:01:53 01/22/02
Go up one level in this thread
On January 22, 2002 at 00:12:43, Dann Corbit wrote:
Thanks Dann!
I am very interested on this. I do not use such a function yet, but
I am planning a partial rewrite of the structures of my program
and when I do, I think that I will need something like lowbit.
However, I want to have it in pure ANSI C, at least to have that
option. These are two options for lowbit that I thought before.
I give it in the same framework as L. Kirby so you can test it if you want.
When the times come, I will test them for performance.
To be honest, I have no clue what Kirby's idea is.
My two versions could be slower, I do not know. The only advantage is
that do not use multiplications or branches and could be easily adapted
for 64 bits, particularly lowbit().
#include <stdio.h>
static const unsigned int S_lowbit_lookup[] = {
0, 1, 2, 6, 3, 11, 7, 16, 4, 14, 12, 21, 8, 23, 17, 26,
31, 5, 10, 15, 13, 20, 22, 25, 30, 9, 19, 24, 29, 18, 28, 27
};
#define NUMBITS 32
#define LOWBIT(x) S_lowbit_lookup[(((x) & -(x))*0x04653adf >> 27) & 0x1f]
/******************************/
unsigned char lookup[] =
{
0,1,0,2,0,0,0,3,0,0,0,0,0,0,0,4,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,
/* this second part is only needed for lowbit2*/
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,
};
int lowbit (unsigned long int x);
int lowbit2 (unsigned long int x);
/********************************/
int main(void)
{
int bit;
printf("%08lx:%2u\n", 0UL, LOWBIT(0UL));
for (bit = 0; bit < NUMBITS; bit++) {
unsigned long value1 = 1UL << bit;
unsigned long value2 = value1 * 15;
/* try LOWBIT, lowbit, lowbit2 */
printf("%08lx:%2u %08lx:%2u\n", value1, lowbit(value1),
value2, lowbit(value2));
}
return 0;
}
int lowbit (unsigned long int x)
{
unsigned long int b, p, y, z, counter;
/*ASSERT(x != 0);*/
counter = 0;
b = (x & -x) - 1; /* counting how many bits are "on" in b will give
the answer */
/* split in two halves (x,y) and select the appropiate one with p */
y = b & 0xffff;
z = b >> 16;
p = (y >> 15) - 1;
/* if y is full add 16 to the counter */
counter += 16 & ~p;
b = (z & ~p) | (y & p);
/* procedue similar to above now applied to two halves of 8 bits */
y = b & 0xff;
z = b >> 8;
p = (y >> 7) - 1;
counter += 8 & ~p;
b = (z & ~p) | (y & p);
/*ASSERT(b < 128);*/
/* count the rest with a lookup */
counter += lookup[b];
return counter;
}
int lowbit2 (unsigned long int x)
{
unsigned long int b;
/*ASSERT(x != 0);*/
b = (x & -x) - 1; /* counting how many bits are "on" in b will give
the answer */
return
lookup[b & 0xff] +
lookup[b>> 8 & 0xff] +
lookup[b>>16 & 0xff] +
lookup[b>>24 & 0xff];
}
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.