Author: Dann Corbit
Date: 18:19:51 08/19/99
Go up one level in this thread
On August 19, 1999 at 21:02:15, Robert Hyatt wrote:
>Those are the easy ones.. he is trying to find the number of the bit that
>is set (ie the FirstOne()/LastOne() functions in Crafty). That is harder..
Oh. High bit is easy. Here are some algorithms for finding the most
significant bit. If you have long long or __int64 most of them are easily
converted to other types:
/***********************************************/
/* Locate the postion of the highest bit set. */
/* A binary search is used. The result is an */
/* approximation of log2(n) [the integer part] */
/***********************************************/
int ilog2(unsigned long n)
{
int i = (-1);
/* Is there a bit on in the high word? */
/* Else, all the high bits are already zero. */
if (n & 0xffff0000) {
i += 16; /* Update our search position */
n >>= 16; /* Shift out lower (irrelevant) bits */
}
/* Is there a bit on in the high byte of the current word? */
/* Else, all the high bits are already zero. */
if (n & 0xff00) {
i += 8; /* Update our search position */
n >>= 8; /* Shift out lower (irrelevant) bits */
}
/* Is there a bit on in the current nybble? */
/* Else, all the high bits are already zero. */
if (n & 0xf0) {
i += 4; /* Update our search position */
n >>= 4; /* Shift out lower (irrelevant) bits */
}
/* Is there a bit on in the high 2 bits of the current nybble? */
/* 0xc is 1100 in binary... */
/* Else, all the high bits are already zero. */
if (n & 0xc) {
i += 2; /* Update our search position */
n >>= 2; /* Shift out lower (irrelevant) bits */
}
/* Is the 2nd bit on? [ 0x2 is 0010 in binary...] */
/* Else, all the 2nd bit is already zero. */
if (n & 0x2) {
i++; /* Update our search position */
n >>= 1; /* Shift out lower (irrelevant) bit */
}
/* Is the lowest bit set? */
if (n)
i++; /* Update our search position */
return i;
}
/*
** From: <bousek@$smtpg.compsys.com$>
** Subject: Re: Is there a faster way to find the highest bit set in a 32 bit
integer? [Includes C code listing]
** Newsgroups: comp.graphics.algorithms
** References: <01bc3fac$69b314c0$ca61e426@DCorbit.solutionsiq.com>
** Organization: TDS Telecom - Madison, WI
** Message-ID: <01bc405b$2c1c8740$ca61e426@DCorbit.solutionsiq.com>
** X-Newsreader: Microsoft Internet News 4.70.1155
** MIME-Version: 1.0
** Content-Type: text/plain; charset=ISO-8859-1
** Content-Transfer-Encoding: 7bit
**
** "Dann Corbit" <dcorbit@solutionsiq.com> wrote:
** <snip>
** hey Dann:
** you could modify your routine something like this (although i would tend to
** put this type of routine in assembler)...
*/
int qlog2(unsigned long n)
{
register int i = (n & 0xffff0000) ? 16 : 0;
if ((n >>= i) & 0xff00)
i |= 8, n >>= 8;
if (n & 0xf0)
i |= 4, n >>= 4;
if (n & 0xc)
i |= 2, n >>= 2;
return (i | (n >> 1));
}
int klog2(unsigned long n)
{
register int p = 16,
i = 0;
do {
unsigned long t = n >> p;
if (t)
n = t, i |= p;
} while (p >>= 1);
return i;
}
#include <math.h>
/*
* FROM: steve@tangled-web.compulink.co.uk
* This is the fully portable version, which uses
* the 'frexp' function to get the mantissa and
* exponent of a number.
*/
int slog2( unsigned long value )
{
int exponent ;
double d_val = (double)value ;
double mantissa = frexp ( d_val, &exponent ) ;
return exponent - 1 ;
}
/*
* FROM: steve@tangled-web.compulink.co.uk
* This is the rather less portable version, which
* requires you to know how doubles are stored
* in memory, and the location and bias of the
* exponent for such numbers.
* This example is for doubles ( 64 bits )
* on Intel hardware - YMMV.
*/
/* CHANGED FROM DOUBLE TO FLOAT --
#define MP(x) ((long int *)&d_val)[x]
int tlog2( unsigned long value )
{
double d_val = (double)value ;
return (int)( MP(1) >> 20 & 0x7ff ) - 0x3ff ;
}
*/
#define MP(x) ((long int *)&d_val)[x]
int tlog2( unsigned long value )
{
float d_val = (float)value ;
return (int)( MP(0) >> 23 & 0xff ) - 0x7f ;
}
/*
From: Robert E. Minsk[SMTP:egbert@spimageworks.com]
Sent: Saturday, April 12, 1997 9:44 PM
To: Dann Corbit
Subject: Is there a faster way to find the highest bit set in a 32 bit
integer? [Includes C code listing]
I did not see the original post but why don't you build a table of the
highest bit set in a byte and then check each byte. For example.
*/
static unsigned char hiBitSetTab[] = {
0, 1, 2, 2, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7
};
/* On my machine unsigned int is 32-bits, big ended */
int ulog2(unsigned long val)
{
unsigned long tmp;
tmp = val >> 24;
if (tmp) {
return hiBitSetTab[tmp] + 23;
}
tmp = (val >> 16) & 0xff;
if (tmp) {
return hiBitSetTab[tmp] + 15;
}
tmp = (val >> 8) & 0xff;
if (tmp) {
return hiBitSetTab[tmp] + 7;
}
return hiBitSetTab[val & 0xff]-1;
}
/*
or even:
*/
typedef union {
unsigned long i;
unsigned char c[4];
} u32bitType;
/* On my machine unsigned int is 32-bits, big ended */
int vlog2(long l)
{
u32bitType val;
val.i = l;
if (val.c[3]) {
return hiBitSetTab[val.c[3]] + 23;
}
if (val.c[2]) {
return hiBitSetTab[val.c[2]] + 15;
}
if (val.c[1]) {
return hiBitSetTab[val.c[1]] + 7;
}
return hiBitSetTab[val.c[0]]-1;
}
#ifdef TEST
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{
unsigned long l;
unsigned long m;
unsigned long limit = 1000000;
for (l = 0; l < limit; l++)
{
m = l*rand();
m = qlog2(m), klog2(m), slog2(m), tlog2(m), ulog2(m), vlog2(m);
}
for (l = 0; l < limit / 100; l += 100) {
printf("l=%lu, klog2=%lu, qlog2=%lu, slog2 = %lu, tlog2 = %lu, ulog2 =
%lu, vlog2 = %lu, log2=%f\n",
l, klog2(l), qlog2(l), slog2(l), tlog2(l), ulog2(l), vlog2(l),
log((double) l) / log(2.));
}
return 0;
}
#endif
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.