## Problem

Find the number of set bits in a given Integer N.

## Solution

At the first look the problem looks like a simple AND `&` operation query. Check for each bit whether it is set or not, and then return the value back. For an 2-byte value, it would take 16 operations, and for a 4-byte value 32-operations to find the number of set bits. In other words for any given Integer N, the operation will be O(constant) in terms of time-complexity. Can this time complexity be reduced further?

The answer is YES. The bitwise boolean operations help us in checking if a certain bit is on or not. Say for a given binary number `0010` stored as `n`, we do `n & (-n)`, it would return us a value of `2` indicating that the current least most bit that is set represents 2 in decimal. For a number like `0110`, the first operation will bring us a value of 2. If we subtract 2 from the original number, we get `0100` and now running the same operation results in a value of 4 (the next least set bit).

We can use the same principle along with recursion to find out the number of set bits in a given number. Keep finding the least set bit, subtract from the original number (reducing it every time) and keep counting. This way if a 4-byte number has only 1 bit set, we take only 1 operation to find the same, rather than 32, reducing our time complexity drastically.

``````/**
* Copyright (C) 2011, Sandeep Gupta
* http://www.sangupta.com
*
* (the "License"); you may not use this file except in compliance with
* the License.  You may obtain a copy of the License at
*
*
* Unless required by applicable law or agreed to in writing, software
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*
* See the License for the specific language governing permissions and
*
*/

public class Bits {

public static void main(String[] args) {
System.out.println(bits(15));
}

private static int bits(int n) {
if(n == 0) {
return 0;
}

int sub = n & -n;
return 1 + bits(n - sub);
}

}
``````

Hope this helps.