Sum of bits set

Q: Given a positive integer N calculate the sum of bits set for all the numbers from 0 to N.

I will be using divide and conquer for this. 

Fact: The sum of all set bits from 0 to (2 ^ n) - 1 is (2 ^ n-1) * n
This can be proved by induction or construction.

Approach:

1) Get the MSB location of the integer N, i.e. the left most bit which is set as 1, lets say it is X

2) Get the sum of all the bits till (2 ^ X) - 1 using the fact given above, lets say it is Sum

3) Now, add 1 for number (2 ^ X) to Sum

4) We are now left to calculate from (2 ^ X) + 1 to N. All these will have Xth bit set.
5) So add N - (2 ^ X) to Sum
6) Now we can solve for a smaller sub-problem using recursion. The numbers left are (2 ^ X) + 1 ..... N, with the Xth bit now turned off since we have already considered the Xth bit in step 5. This is equivalent to finding the sum of bits till N XOR (2 ^ X)

Code:

	/**
	* Author: Varun
	* Date: May 31, 2012
	*/
	public class SumOfBitsSet {
	// this method returns the MSB location counting starts with 0 from right
	public int getMSBLocation(int n) {
	int SLICES[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
	int SLICEDBITS[] = {1, 2, 4, 8, 16};
	int msbLocation = 0;
	for(int i = SLICES.length - 1; i >= 0; i--) {
	if((n & SLICES[i]) != 0) {
	n = n >> SLICEDBITS[i];
	msbLocation = msbLocation | SLICEDBITS[i];
	}
	}
	return msbLocation;
	}
	public int getSumOfSetBitsBeforePowerOfTwo(int power) {
	return (1 << (power - 1)) * power;
	}
	public int getSumOfSetBits(int n) {
	if(n <= 0) {
	return 0;
	}
	int msbLocation = getMSBLocation(n);
	return getSumOfSetBitsBeforePowerOfTwo(msbLocation) +
	1 + // for the power of 2
	(n - (1 << msbLocation)) +
	getSumOfSetBits(n ^ (1 << msbLocation));
	}
	public static void main(String[] args) {
	int n = 35;
	SumOfBitsSet bitSumCalculator = new SumOfBitsSet();
	System.out.println(bitSumCalculator.getSumOfSetBits(n));
	}
	}

view raw SumOfBitsSet.java hosted with ❤ by GitHub

To get the MSB location we can again use divide and conquer to reduce the no. of steps.
http://graphics.stanford.edu/~seander/bithacks.html

Ideas taken from:
http://tech-queries.blogspot.in/2010/12/number-of-set-bits-till-n.html
http://code.rishibaldawa.com/count-all-set-bits-from-0-till-n-for-each-number