#======================================================================
# 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 ) )
