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