[easy]Most Significant Bit

[Jason Menard]

This is rather trivial, but I'm curious to see whether or not anyone has any interesting approaches to this. I also thought I would throw in an actual programming diversion for a change as well.
The problem: give an input long integer (let's assume positive, but I'd also be interested in discussing the ramifications if any of considering negatives), return the position of the long's most significant bit (MSB).
For ease, I guess we can keep the count zero-based. Therefore, if we want the MSB of 7, the answer would be 2.

    3210
    ----
7 = 0111

The leftmost one bit, the MSB, is in the 2^2 position, so the MSB of 7 is 2.

[Carl Trusiak]

How's this for quick and dirty.

        long i = 7;
        System.out.println(Long.toBinaryString(i).length() -1);

[ August 26, 2003: Message edited by: Carl Trusiak ]

[Jason Menard]

Not too shabby.
For a more general solution, although probably not the best, here's what I came up with.

public static long getMSB(long val) {
    long msb = 0;
    while ((1 << msb) <= val)
        msb++;
    if (msb > 0)
        msb--;
    return msb;
}

[Carl Trusiak]

Not bad, however for negitive numbers your routine returns 0 (OK, he did say may include negatives) However for large numbers such as Integer.MAX_VALUE it goes into an infinite loop.
Hows' this:

    public static long getRightShiftMSB(long val){
        long count = -1;
        while(val > 0)
        {
            val >>>= 1;
            count++;
        }
        return count;
    }

Now for 0 it returns -1 Where the String version returns 0 but, he did specify what that should return so, I guess both answers are correct
As the saying goes, no Specification, no Bug!

[Jason Menard]

Pretty good. I've got a special place in my heart for bit operations.
I guess there's something to be said for actually testing code, eh?