Ceiling of the Logarthim Base Two

[Leo de Wit]

In article <10978 at sol.ARPA> crowl at cs.rochester.edu (Lawrence Crowl) writes:
  [introducory stuff for exponent calculating macro deleted]....

>#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( ) )

  [second symmetric solution for search up deleted]...

Let's take for granted (as the author does) that n is at most a simple
expression (an optimizer could keep it in a register for instance),
otherwise simply shifting should be preferred.

This macro is easily adapted for a binary search (in fact the 32 bit
integers scream for it 8-); note I used a somewhat different layout to
make things clearer for this macro (b.t.w. the 1<<xx will evaluate to a
constant at compile time).


#define CEILOG2_U( n ) (\
(n) > 1<<15 ? (n) > 1<<23 ? (n) > 1<<27 ? (n) > 1<<29 ? (n) > 1<<30 ? 31 : 30\
                                                      : (n) > 1<<28 ? 29 : 28\
                                        : (n) > 1<<25 ? (n) > 1<<26 ? 27 : 26\
                                                      : (n) > 1<<24 ? 25 : 24\
                          : (n) > 1<<19 ? (n) > 1<<21 ? (n) > 1<<22 ? 23 : 22\
                                                      : (n) > 1<<20 ? 21 : 20\
                                        : (n) > 1<<17 ? (n) > 1<<18 ? 19 : 18\
                                                      : (n) > 1<<16 ? 17 : 16\
            : (n) > 1<<7  ? (n) > 1<<11 ? (n) > 1<<13 ? (n) > 1<<14 ? 15 : 14\
                                                      : (n) > 1<<12 ? 13 : 12\
                                        : (n) > 1<<9  ? (n) > 1<<10 ? 11 : 10\
                                                      : (n) > 1<<8  ?  9 :  8\
                          : (n) > 1<<3  ? (n) > 1<<5  ? (n) > 1<<6  ?  7 :  6\
                                                      : (n) > 1<<4  ?  5 :  4\
                                        : (n) > 1<<1  ? (n) > 1<<2  ?  3 :  2\
                                                      : (n) > 1<<0  ?  1 :  0)

The average search is 5 steps, while the linear search averages to 16 steps.
Another approach is to assign the value to a float (double) and use the
exponent. This could even prove faster. For example:

#include <math.h>

int expo;

      frexp((double)n,&expo);

If frexp is builtin this just could be faster. Otherwise the bits of 
(double)n can be manipulated (non-portable).

Enjoy!

       Leo.