Count Set Bits
by Isai Damier

#======================================================================
# Author: Isai Damier
# Title: Count Bits
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#   Count the number of 1s in the given bit sequence.
#
# Sample Input: integer representation of bit sequence 1000110010
# Sample Output: 4
#
# Technical Details: Numerous techniques have been devised to
#    count the number of bits in a bit sequence. The simplest way
#    to internalize why a given technique works is to take a
#    pencil and run though a few examples.
#
#    The presented approach runs through a loop and clears the
#    lowest set bit of n during each iteration. When no set bit
#    is left (i.e. n==0) the number of iterations is returned.
#
#    0] Set count to 0
#    1] while n > 0:
#     -- clear the least significant bit in n: n &= (n-1)
#     -- increment count by 1: count+=1
#    2] return count.
#
#  Alternate Algorithm: e.g. n = n & ~(n & ~(n-1));
#====================================================================== 
 def countBits( n ):
  count = 0
  while ( 0 != n ):
    n &= ( n - 1 )
    count += 1

  return count
import unittest
from algorithms import bitwise as bits

class Test( unittest.TestCase ):

    def testCountBits( self ):
      A = ["0000000000", "0000001000", "0001010000", "1100001000",
           "1000110010", "0101110001", "1100101101", "1101110101",
           "1101111011", "1111101111", "1111111111"]

      for i in range( len( A ) ):
        self.assertEqual( i, bits.countBits( int( A[i], 2 ) ) )