Author: Robert Hyatt
Date: 20:37:25 08/19/99
Go up one level in this thread
On August 19, 1999 at 21:19:51, Dann Corbit wrote:
that is well-known. However, FirstOne() is used a lot, and without a
BSF/BSR (which is way faster than the code below) the table-lookup was
faster on every machine I tested it on. The 4 array probes generally
get cache hits on reasonable hardware...
When I first wrote crafty, I (and several others) tried all sorts of
approaches. Another interesting one is population count. I use a
simple loop as I only use this on very sparsely populated bitmaps. But
there are some amazingly clever approaches dealing with shift/add and a
divide at the end. But none (for crafty) are faster than the simple loop
I now use...
>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.01 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.