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

Question

For homework, using C, I'm supposed to make a program that finds the log base 2 of a number greater than 0 using only the operators ! ~ & ^ | + << >>. I know that I'm supposed to shift right a number of times, but I don't know how to keep track of the number of times without having any loops or ifs. I've been stuck on this question for days, so any help is appreciated.

int ilog2(int x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
}

This is what I have so far. I pass the most significant bit to the end.

Answer 1

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));
}

Answer 2

This gets the floor of logbase2 of a number.

int ilog2(int x) {

    int i, j, k, l, m;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

    // i = 0x55555555 
    i = 0x55 | (0x55 << 8); 
    i = i | (i << 16);

    // j = 0x33333333 
    j = 0x33 | (0x33 << 8);
    j = j | (j << 16);

    // k = 0x0f0f0f0f 
    k = 0x0f | (0x0f << 8);
    k = k | (k << 16);

    // l = 0x00ff00ff 
    l = 0xff | (0xff << 16);

    // m = 0x0000ffff 
    m = 0xff | (0xff << 8);

    x = (x & i) + ((x >> 1) & i);
    x = (x & j) + ((x >> 2) & j);
    x = (x & k) + ((x >> 4) & k);
    x = (x & l) + ((x >> 8) & l);
    x = (x & m) + ((x >> 16) & m);
    x = x + ~0;
    return x; 
}

Answer 3

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 .