[Code Interview] Count number of ones

Problem

Counting the number of 1 bits in the binary representation of a given integer.  

Analysis

Method 1: 

• shift the number right by one bit each time, and check whether the right-most bit is 1
• If yes, count++

Method 2:

• if n is not 0, count++
• assign n = n & (n-1), repeat until n is 0

Time complexity

• method 1: theta(n)
• method 2: O(n)

Code

	// method 1
	int countNumOfOnes(int n){
	int count = 0;
	while(n){
	count += (n & 1);
	n >> 1;
	}
	return count;
	}
	// method 2
	int countNumOfOnes(int n){
	int count = 0;
	while(n){
	n &= (n-1);
	count++;
	}
	return count;
	}

view raw count-number-of-one.java hosted with ❤ by GitHub

Reference

[1] http://www.geeksforgeeks.org/count-set-bits-in-an-integer/