Clear Lowest Bit
by Isai Damier

#======================================================================
# Author: Isai Damier
# Title: Clear Lowest Bit
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#   Clear the least significant (set) bit in the given sequence of bits.
#
# Sample Input: integer representation of bit sequence 1111111110
# Sample Output: 1111111100 after clearing the lowest set bit
#
# Technical Details: When counting in binary, the difference
#    between two consecutive numbers (i.e. n and n-1) is twofold:
#     1] The least significant set bit in the greater number
#       is not set in the lesser number.
#     2] All bits to the left of said least significant set bit
#        are the same for both numbers.
#    (7) 0000_0111,  (6) 0000_0110,  (5) 0000_0101,  (4) 0000_0100,
#    (6) 0000_0110,  (5) 0000_0101,  (4) 0000_0100,  (3) 0000_0011.
#
#     Hence, taking the bitwise AND of n and n-1 is sufficient for
#     clearing the least significant bit.
#====================================================================== 
 def clearLowestBit( n ):
  return n & ( n - 1 )
import unittest
from algorithms import bitwise as bits

class Test( unittest.TestCase ):

    def testClearLowestBit( self ):

      A = ["1111111111", "1111111110", "1111111100", "1111111000",
             "1111110000", "1111100000", "1111000000", "1110000000",
             "1100000000", "1000000000", "000000000", "000000000"]

      for i in range( 1, len( A ) ):
        x = int( A[i - 1], 2 )
        y = int( A[i], 2 )
        self.assertEqual( y, bits.clearLowestBit( x ) )