Bit manipulation problems are always interesting with surprisingly short yet hard-to-understand solutions.
Today, we consider this problem: Given an integer n, find the position (0-based) of its most significant bit efficiently in terms of time/space complexity.
In other word, we want to find the biggest integer k such that $2^k \leq n$.

1. First solution: GCC built-ins

One acceptable solution given that we use gcc is to use its built-in function, __builtin_clz (or __builtin_clzll for long long n). Note that, if $n = 0$, then for $\forall k \in \mathbb{Z}$, $2^k > n$, thus in this case the answer is $-\infty$. Simple C++ code is given below.

1
2
3
4
5
6
7
8
9
10
11
12
13

#include<iostream>
#include<limits>
using namespace std;
typedef unsigned long long ull;

// n = 0, then for any i \in Z, 2^i >= n. In this case, answer is -INF
int msb_v1(int n){
    return n ? sizeof(n)*8 - __builtin_clz(n) - 1 : numeric_limits<int>::min();
}

int msb_ull(unsigned long long n){
    return n ? sizeof(n)*8 - __builtin_clzll(n) - 1 : numeric_limits<ull>::min();
}

Find out more about gcc builtins

2. Cool solution: IEEE 754 double-precision binary floating-point format binary64

The IEEE 754 standard specifies a binary64 format of a 64-bit double number as:
+ Sign bit: 1 bit
+ Exponent part: 11 bits
+ Fraction part: 52 bits
Check out, e.g., Wikipedia for more details.
Now, our problem is reduced to extract the exponent part of a given number n in double format. One way is to first convert n to double and then extract the 11-bit exponent part from its binary representation. The C++ code is given below.

1
2
3
4
5
6
7
8
9
10
11
12

#include<iostream>
using namespace std;

int msb(unsigned x){
    union {
        double v;
        int b[2];
    };

    v = x; // store x as double (8 bytes = 64 bits) in v
    return (b[1] >> 20) - 1023; // obtain the exponent part
}

3. Other solutions

In Java, Integer.highestOneBit(int n) method does the trick. For more details on bitwise operations in Java, see e.g., this.
We can also precalculate values and achieve O(1) time complexity solution at the expense of additional memory. I will update this post whenever I find any new and good solution.