Most Significant Set Bit (MSB)
by Isai Damier

#======================================================================
# 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 eger portion of log2(n). So
#   to find the log base two of n, just shift right until one bit is
#   left.
#====================================================================== 
 def MSB( n ):
  ndx = 0
  while ( 1 < n ):
    n = ( n >> 1 )
    ndx += 1

  return ndx
import unittest
from algorithms import bitwise as bits

class Test( unittest.TestCase ):

    def testMSB( self ):
        self.assertEquals( 4, bits.MSB( 17 ) )
        self.assertEquals( 4, bits.MSB( 31 ) )
        self.assertEquals( 5, bits.MSB( 32 ) )
        self.assertEquals( 7, bits.MSB( 128 ) )
        self.assertEquals( 7, bits.MSB( 255 ) )
        self.assertEquals( 8, bits.MSB( 256 ) )