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

Duplicate & missing number

Q: In an unsorted array of first N natural numbers which has a duplicate number and a missing number, find the duplicate and missing numbers.

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Sum of N^2 numbers = n(n+1)(2n+1)/6

3. Since there are 2 unknowns we can create 2 equations using the above formulae to solve them

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Multiplication of N numbers / n! = Duplicate/Missing

3. Again we can solve for the 2 unknowns using the above formulae

Both the above approach assumes that N^2 or N! can be held in an int/double etc without overflow. In Java we can make use of BigInteger but there is another approach to solve the problem using bit operators.

Soln approach:

Let Ai be the ith element of the array, 0 <= i < n

Let Bi be i+1

1. Find Duplicate XOR Missing = X

    - XOR all Ai and Bi

2. Find which rightmost bit is 1 in X = Y

    - X & ~(X - 1)

3. Partition A and B such that A1 and B1 has Y set and A2 and B2 does not have Y set

    - Iterate and use & operator over Y and elements of A and B

4. XOR elements of A1 and B1 = VALUE1

5. XOR elements of A2 and B2 = VALUE2

6. If A1.length > B1.length then VALUE1 = Duplicate and VALUE2 = Missing

    else VALUE2 = Duplicate and VALUE1 = Missing