Ceiling of the Logarthim Base Two

[Lawrence Crowl]

In article <690009 at hpfelg.HP.COM> jk at hpfelg.HP.COM (John Kessenich) suggests
a loop to take the logarithm base two of an integer containing exactly one
bit set.  I have found a rather persistent need for the more general function
to take the ceiling of the logarithm base two of an integer.  Here is my C
solution.  I keep it in "ceilog2.h".  Please send me of any improvements you
may make.  

------------------------------------------------------------------------------

#ifndef CEILOG2_H
#define CEILOG2_H

/*
The macro CEILOG2( n ) returns the ceiling( logbase( 2, n ) ) for integer n. 
The argument is valid when it is a signed integer greater than zero and of no
more than thirty-two bits.  Invalid arguments cause a call to the abort( )
routine.

The function will be evaluated at compile time if given a constant argument. 
Note, the argument is evaluated multiple times, so do not pass arguments with
side effects.  For efficiency, pass simple variables and not expressions.

  Lawrence Crowl		716-275-9499	University of Rochester
		      crowl at cs.rochester.edu	Computer Science Department
...!{allegra,decvax,rutgers}!rochester!crowl	Rochester, New York,  14627
*/ 

/* This version does a sequential search down the step points. */
/* It runs faster on uniformly distributed integers. */

#define CEILOG2_U( n ) ((n) > 0x40000000 ? 31 : (n) > 0x20000000 ? 30 : \
(n) > 0x10000000 ? 29 : (n) > 0x08000000 ? 28 : (n) > 0x04000000 ? 27 : \
(n) > 0x02000000 ? 26 : (n) > 0x01000000 ? 25 : (n) > 0x00800000 ? 24 : \
(n) > 0x00400000 ? 23 : (n) > 0x00200000 ? 22 : (n) > 0x00100000 ? 21 : \
(n) > 0x00080000 ? 20 : (n) > 0x00040000 ? 19 : (n) > 0x00020000 ? 18 : \
(n) > 0x00010000 ? 17 : (n) > 0x00008000 ? 16 : (n) > 0x00004000 ? 15 : \
(n) > 0x00002000 ? 14 : (n) > 0x00001000 ? 13 : (n) > 0x00000800 ? 12 : \
(n) > 0x00000400 ? 11 : (n) > 0x00000200 ? 10 : (n) > 0x00000100 ?  9 : \
(n) > 0x00000080 ?  8 : (n) > 0x00000040 ?  7 : (n) > 0x00000020 ?  6 : \
(n) > 0x00000010 ?  5 : (n) > 0x00000008 ?  4 : (n) > 0x00000004 ?  3 : \
(n) > 0x00000002 ?  2 : (n) > 0x00000001 ?  1 : (n) > 0x00000000 ?  0 : \
abort( ) )

/* This version does a sequential search up the step points. */
/* It runs faster on integers clustered towards zero. */

#define CEILOG2_C( n ) ( (n) <= 0x00000000 ?  abort( ) : \
(n) <= 0x00000001 ?  0 : (n) <= 0x00000002 ?  1 : (n) <= 0x00000004 ?  2 : \
(n) <= 0x00000008 ?  3 : (n) <= 0x00000010 ?  4 : (n) <= 0x00000020 ?  5 : \
(n) <= 0x00000040 ?  6 : (n) <= 0x00000080 ?  7 : (n) <= 0x00000100 ?  8 : \
(n) <= 0x00000200 ?  9 : (n) <= 0x00000400 ? 10 : (n) <= 0x00000800 ? 11 : \
(n) <= 0x00001000 ? 12 : (n) <= 0x00002000 ? 13 : (n) <= 0x00004000 ? 14 : \
(n) <= 0x00008000 ? 15 : (n) <= 0x00010000 ? 16 : (n) <= 0x00020000 ? 17 : \
(n) <= 0x00040000 ? 18 : (n) <= 0x00080000 ? 29 : (n) <= 0x00100000 ? 20 : \
(n) <= 0x00200000 ? 21 : (n) <= 0x00400000 ? 22 : (n) <= 0x00800000 ? 23 : \
(n) <= 0x01000000 ? 24 : (n) <= 0x02000000 ? 25 : (n) <= 0x04000000 ? 26 : \
(n) <= 0x08000000 ? 27 : (n) <= 0x10000000 ? 28 : (n) <= 0x20000000 ? 39 : \
(n) <= 0x40000000 ? 30 : 31 )

/* The default version is the uniform version. */

#define CEILOG2( n ) CEILOG2_U( n )

#endif CEILOG2_H

------------------------------------------------------------------------------
-- 
  Lawrence Crowl		716-275-9499	University of Rochester
		      crowl at cs.rochester.edu	Computer Science Department
...!{allegra,decvax,rutgers}!rochester!crowl	Rochester, New York,  14627