high bit revisited
Dann Corbit
integers. I have a bunch of different ways below of which some are portable
and some are not (in fact, half of these are no better than using assembly,
since they are completely non-portable). Since the bit counting experiment
was so fruitful, I was hoping that some better ways of finding the highest
bit might be found. Matthew Hendry and Chris Torek might know of some
better ways to do it (for instance).
/***********************************************/
/* Locate the position 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$ca61...@DCorbit.solutionsiq.com>
** Organization: TDS Telecom - Madison, WI
** Message-ID: <01bc405b$2c1c8740$ca61...@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" <dco...@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: st...@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: st...@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:egb...@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),
#ifdef SLOW_ONES_ALSO
slog2(m),
#endif
tlog2(m), ulog2(m), vlog2(m);
}
for (l = 0; l < limit / 100; l += 100) {
#ifdef SLOW_ONES_ALSO
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.));
#else
printf("l=%lu, klog2=%lu, qlog2=%lu, tlog2 = %lu, ulog2 = %lu, vlog2
= %lu, log2=%f\n",
l, klog2(l), qlog2(l), tlog2(l), ulog2(l), vlog2(l),
log((double) l) / log(2.));
#endif
}
return 0;
}
#endif
/*
Profile: Function timing, sorted by time
Date: Thu Dec 30 12:25:45 1999
Program Statistics
------------------
Command line at 1999 Dec 30 12:23: "D:\c\log2\Release\LOG2"
Total time: 7481.331 millisecond
Time outside of functions: 33.115 millisecond
Call depth: 2
Total functions: 7
Total hits: 5000501
Function coverage: 85.7%
Overhead Calculated 6
Overhead Average 6
Module Statistics for log2.exe
------------------------------
Time in module: 7448.216 millisecond
Percent of time in module: 100.0%
Functions in module: 7
Hits in module: 5000501
Module function coverage: 85.7%
Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
3345.705 44.9 7448.216 100.0 1 _main (log2.obj)
908.733 12.2 908.733 12.2 1000100 @vlog2@4 (log2.obj)
829.133 11.1 829.133 11.1 1000100 @qlog2@4 (log2.obj)
811.069 10.9 811.069 10.9 1000100 @tlog2@4 (log2.obj)
795.309 10.7 795.309 10.7 1000100 @klog2@4 (log2.obj)
758.267 10.2 758.267 10.2 1000100 @ulog2@4 (log2.obj)
*/
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
Mathew Hendry
wrote:
>I am trying to find fast and portable ways to detect the high bit of
>integers. I have a bunch of different ways below of which some are portable
>and some are not (in fact, half of these are no better than using assembly,
>since they are completely non-portable). Since the bit counting experiment
>was so fruitful, I was hoping that some better ways of finding the highest
>bit might be found.
Here are a few of the more interesting ones I have came across (I think I sent
you my full "collection" a while ago... very few of them are portable). All
return -1 for all-bits-zero.
/* exhaustive binary search (you won't get much faster without a lookup
table) */
int
hi_bit20(unsigned long n){
return n&65535<<16?n&255<<24?n&15<<28?n&12<<28?n&8<<28?31:30:n&2<<28?29:28
:n&12<<24?n&8<<24?27:26:n&2<<24?25:24:n&15<<20?n&12<<20?n&8<<20?23:
22:n&2<<20?21:20:n&12<<16?n&8<<16?19:18:n&2<<16?17:16:n&255<<8?n&15
<<12?n&12<<12?n&8<<12?15:14:n&2<<12? 13:12:n&12<<8?n&8<<8?11:10:n&2
<<8?9:8:n&240?n&192?n&128?7:6:n&32?5:4:n&12?n&8?3:2:n&2?1:n&1?0:-1;
}
/* bytewise binary search, lookup table */
int
hi_bit21(unsigned long n){
static const int *t=tab_8;
return n>>16?n>>24?24+t[n>>24]:16+t[n>>16]:n>>8?8+t[n>>8]:t[n];
}
/* frexp */
int
hi_bit22(unsigned long n){
int h;
frexp((double)n,&h);
return h-1;
}
/* magical :) but slow :( */
int
hi_bit23(unsigned long n){
static const int *t=tab_m37_ff;
return t[(n|=n>>1,n|=n>>2,n|=n>>4,n|=n>>8,n|=n>>16)%37];
}
/* bytewise linear search, with a small comparison-avoiding twist */
hi_bit24(unsigned long n){
static const int *t = tab_8;
return n>=1<<23?24+t[n>>24]:n>=1<<15?16+t[n>>16]:n>=1<<8?8+t[n>>8]:t[n];
}
/* bytewise binary search, with the same twist, even though there's no reason it
should work here (always two comparisons anyway) */
int
hi_bit25(unsigned long n){
static const int *t = tab_8;
return n>=1<<15?n>=1<<23?24+t[n>>24]:16+t[n>>16]:n>=1<<8?8+t[n>>8]:t[n];
}
/* log() - found to be non-portable due to vague log() accuracy */
int
hi_bit32(unsigned long n){
return n?(int)floor(log((double)n)/log(2.)):-1;
}
/* IEEE trick */
int
hi_bit47(unsigned long n){
if ( n ) {
float f = n;
return ((*(unsigned long*)&f)>>23)-127;
} else {
return -1;
}
}
/* the tables needed by some of the above */
const int tab_m37_ff[] = {
-1,0,25,1,22,26,31,2,15,23,29,27,10,-1,12,3,6,16,
-1,24,21,30,14,28,9,11,5,-1,20,13,8,4,19,7,18,17
};
const int tab_8[]={
-1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,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,
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,
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
};
-- Mat.