Computing the floor of log₂(x) using only bitwise operators in C

Assumes a 32-bit unsigned int :

unsigned int ulog2 (unsigned int u)
{
    unsigned int s, t;

    t = (u > 0xffff) << 4; u >>= t;
    s = (u > 0xff  ) << 3; u >>= s, t |= s;
    s = (u > 0xf   ) << 2; u >>= s, t |= s;
    s = (u > 0x3   ) << 1; u >>= s, t |= s;

    return (t | (u >> 1));
}

---

Since I assumed >, I thought I'd find a way to get rid of it.

(u > 0xffff) is equivalent to: ((u >> 16) != 0). If subtract borrows:
((u >> 16) - 1) will set the msb, iff (u <= 0xffff). Replace -1 with +(~0) (allowed).

So the condition: (u > 0xffff) is replaced with: (~((u >> 16) + ~0U)) >> 31

---

unsigned int ulog2 (unsigned int u)
{
    unsigned int r = 0, t;

    t = ((~((u >> 16) + ~0U)) >> 27) & 0x10;
    r |= t, u >>= t;
    t = ((~((u >>  8) + ~0U)) >> 28) &  0x8;
    r |= t, u >>= t;
    t = ((~((u >>  4) + ~0U)) >> 29) &  0x4;
    r |= t, u >>= t;
    t = ((~((u >>  2) + ~0U)) >> 30) &  0x2;
    r |= t, u >>= t;

    return (r | (u >> 1));
}

Your result is simply the rank of the highest non-null bit.

int log2_floor (int x)
{
    int res = -1;
    while (x) { res++ ; x = x >> 1; }
    return res;
}

One possible solution is to take this method:

It is based on the additivity of logarithms:
log₂(2ⁿx) = log₂(x) + n

Let x₀ be a number of 2n bits (for instance, n=16 for 32 bits).

if x₀ > 2ⁿ, we can define x₁ so that x₀ = 2ⁿx₁ and we can say that E(log₂(x₀)) = n + E(log₂(x₁))
We can compute x₁ with a binary shift: x₁ = x₀ >> n

Otherwise we can simply set X₁ = X₀

We are now facing the same problem with the remaining upper or lower half of x₀

By splitting x in half at each step, we can eventually compute E(log₂(x)):

int log2_floor (unsigned x)
{
    #define MSB_HIGHER_THAN(n) (x &(~((1<<n)-1)))
    int res = 0;
    if MSB_HIGHER_THAN(16) {res+= 16; $x >>= 16;}
    if MSB_HIGHER_THAN( 8) {res+=  8; $x >>=  8;}
    if MSB_HIGHER_THAN( 4) {res+=  4; $x >>=  4;}
    if MSB_HIGHER_THAN( 2) {res+=  2; $x >>=  2;}
    if MSB_HIGHER_THAN( 1) {res+=  1;}
    return res;
}

Since your sadistic teacher said you can't use loops, we can hack our way around by computing a value that will be n in case of positive test and 0 otherwise, thus having no effect on addition or shift:

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0(n) (((-(x>>n))>>n)&n)

If the - operator is also forbidden by your psychopatic teacher (which is stupid since processors are able to handle 2's complements just as well as bitwise operations), you can use -x = ~x+1 in the above formula

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0_WITH_NO_MINUS(n) (((~(x>>n)+1)>>n)&n)

that we will shorten to NIMHTNOE0WNM for readability.

Also we will use | instead of + since we know they will be no carry.

Here the example is for 32 bits integers, but you could make it work on 64, 128, 256, 512 or 1024 bits integers if you managed to find a language that supports that big an integer value.

int log2_floor (unsigned x)
{
    #define NIMHTNOE0WNM(n) (((~(x>>n)+1)>>n)&n)

    int res, n;

    n = NIMHTNOE0WNM(16); res  = n; x >>= n;
    n = NIMHTNOE0WNM( 8); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 4); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 2); res |= n; x >>= n;
    n = NIMHTNOE0WNM( 1); res |= n;
    return res;
}

Ah, but maybe you were forbidden to use #define too? In that case, I cannot do much more for you, except advise you to flog your teacher to death with an old edition of the K&R.

This leads to useless, obfuscated code that gives off a strong smell of unwashed 70's hackers.

Most if not all processors implement specific "count leading zeroes" instructions (for instance, clz on ARM, bsr on x86 or cntlz on PowerPC) that can do the trick without all this fuss .

If you're allowed to use & then can you use &&? With that you can do conditionals without the need of if

if (cond)
    doSomething();

can be done with

cond && doSomething();

Otherwise if you want to assign value conditionally like value = cond ? a : b; then you may do it with &

mask = -(cond != 0); // assuming int is a 2's complement 32-bit type
// or mask = (cond != 0) << 31) >> 31;
value = (mask & a) | (~mask & b);

---

There are many other ways in the bithacks page:

int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

or

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);

another way

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];