Most Significant Set Bit (MSB)
by Isai Damier, Android Engineer @ Google

/*********************************************************************
 * Author: Isai Damier
 * Title: Most Significant Set Bit (MSB)
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a bit sequence, indicate the index of the most significant
 *   set bit, where the index of the least significant bit is zero.
 *
 * Sample Input:  00110101
 * Sample Output: 5
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(lg n).
 *
 * Technical Details:
 *   The MSB algorithm is as simple as algorithms comes. Basically,
 *   you continually shift the sequence of bit to the right until
 *   you reach the last set bit. Let's run through the above example:
 *
 *   0] 00110101  Given
 *   1]  0011010  After dropping the 0th right-most bit
 *   2]   001101  After dropping the 1st right-most bit
 *   3]    00110  After dropping the 2nd right-most bit
 *   4]     0011  After dropping the 3rd right-most bit
 *   5]      001  After dropping the 4th right-most bit
 *
 *   At step 5] we are at the 5th and last set bit.
 * 
 *   As it turns out MSB(n) is the integer portion of log2(n). So
 *   to find the log base two of n, just shift right until one bit is
 *   left.
 *
 ********************************************************************/ 
 public int MSB(int n) {
  int ndx = 0;
  while (1 < n) {
    n = (n >> 1);
    ndx++;
  }
  return ndx;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BitwiseTest {

  /**
   * Test of MSB method, of class Bitwise.
   */
  @Test
  public void testMSB() {
    System.out.println("MSB");
    Bitwise mostSignificantBit = new Bitwise();
    assertEquals(4, mostSignificantBit.MSB(17));
    assertEquals(4, mostSignificantBit.MSB(31));
    assertEquals(5, mostSignificantBit.MSB(32));
    assertEquals(7, mostSignificantBit.MSB(128));
    assertEquals(7, mostSignificantBit.MSB(255));
    assertEquals(8, mostSignificantBit.MSB(256));
  }
}