Problem

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Examples

Example 1:

1
2
3
4

Input: n = 11
Output:
 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

1
2
3
4

Input: n = 128
Output:
 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

1
2
3

Input:n = 2147483645
Output: 30
Explanation: The input binary number 1111111111111111111111111111101 has a total of thirty '1' bits.

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Using Modulus and Divide by 2

The basic approach to evaluate the binary form of a number is to traverse on it and count the number of ones.

As to get a number in its binary form, we have to divide it by 2, until it gets 0, which will take logN of time.

Example

1
2
3
4
5
6

Input = 5
Number     Remainder     Number          
5 / 2          1           2
2 / 2          0           1               
1 / 2          1           0                          
Count = 2

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int hammingWeight(int n) {
	int count = 0, rem;

	while (n > 0) {
		rem = n % 2;
		count += rem;
		n /= 2;
	}

	return count;
}

Complexity

  • ⏰ Time complexity: $O(log_2n)$. Given it is a 32 bit integer, O (log (2^32)) = O(32) = O(1)
  • 🧺 Space complexity: O(1)

Method 2 - Using Right Shift Instead of Division

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int hammingWeight(int n) {
	int count = 0;

	while (n > 0) {
		count += n % 2;
		n = n >> 1; // same as n = n /2
	}

	return count;
}

Complexity

  • ⏰ Time complexity: $O(log_2n)$. Given it is a 32 bit integer, O (log (2^32)) = O(32) = O(1)
  • 🧺 Space complexity: O(1)

Method 3 - Using Right Shift and & Operator

We can also use & operator to do the count in previous method, rather than mod. Here we are checking if after right shift, we have 1 at the rightmost position using mask = 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int hammingWeight(int n) {
	int count = 0;
	while(n>0){
		if((n & 1) != 0) {
			count++;
		}
		n = n >> 1;
	}
	return count;
}

Complexity

  • ⏰ Time complexity: $O(log_2n)$. Given it is a 32 bit integer, O (log (2^32)) = O(32) = O(1)
  • 🧺 Space complexity: O(1)

Method 4 - Brian Kernighan’s Algorithm Using & Operator OR Hamming Distance Method 🥇

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

1
2
3
4
5
6
7
8

public int hammingWeight(int n) {
	int count = 0;
	while(n>0){
		n = n&(n-1);
		count++;
	}
	return count;
}

Complexity

  • ⏰ Time complexity: O(K), where where K is the number of ones present in the binary form of the given number. Given it is a 32 bit integer, O (log (2^32)) = O(32) = O(1)
  • 🧺 Space complexity: O(1)

Why this works?

Read here - x&(x-1) Explained.

So as in x-1, the rightmost 1 and bits right to it are flipped, then by performing x&(x-1), and storing it in x, will reduce x to a number containing number of ones(in its binary form) less than the previous state of x, thus increasing the value of count in each iteration.

Dry Run

Suppose, n = 23 = 0b10111

  • Initial State:
    • n = 23 (10111 in binary).
    • count = 0 (to store the number of set bits).
  • Iterative Steps:
    1. n = 23 = 10111, n - 1 = 22 = 10110. n & (n - 1) = 10111 & 10110 = 10110 = 22.
    2. n = 22 = 10110, n - 1 = 21 = 10101. n & (n - 1) = 10110 & 10101 = 10100 = 20.
    3. n = 20 = 10100, n - 1 = 19 = 10011. n & (n - 1) = 10100 & 10011 = 100000 = 16.
    4. n = 16 = 100000, n - 1 = 19 = 01111. n & (n - 1) = 100000 & 01111 = 00000 = 0.

As, now, n = 0, we return 4 as we count the bits each time, n & (n - 1) changes bits.

Method 4 - Using Bitwise And Operator and Left Shift

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int hammingWeight(int n) {

	int count = 0;
	for (int i = 1; i<33; i++) {
		if (getBit(n, i) == true) {
			count++;
		}
	}
	return count;

}

private boolean getBit(int n, int i) {
	return (n & (1<< i)) != 0;
}

Method 5 - Using Lookup Table

This method gains efficiency by leveraging a pre-computed lookup table. The table stores the number of set bits for every integer from 0 to 255, eliminating the need for runtime calculation.

For example:

1
2
3
4
5

0 - 0 Bit(s) set.
1 - 1 Bit(s) set.
2 - 1 Bit(s) set.
3 - 2 Bit(s) set.
...

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

const unsigned char LookupTable[] = { 0, 1, 1, 2, 1, 2, 2,
3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

unsigned int num;
unsigned int ctr; // Number of bits set.

ctr = LookupTable[num & 0xff] +
LookupTable[(num >> 8) & 0xff] +
LookupTable[(num >> 16) & 0xff] +
LoopupTable[num >> 24];

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(256) = O(1)

Please see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable for details.

Method 6 -From Hacker’s Delight, p. 66, Figure 5-2

Code

1
2
3
4
5
6
7
8
9

int hammingWeight(unsigned x)
{
 x = x - ((x >> 1) & 0x55555555);
 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 x = (x + (x >> 4)) & 0x0F0F0F0F;
 x = x + (x >> 8);
 x = x + (x >> 16);
 return x & 0x0000003F;
}
1
2


[Hacker's Delight](http://books.google.com/books?id=iBNKMspIlqEC) is delightful! Highly recommended.

Method 7 - Divide and Conquer

This algorithm is based on Divide and Conquer Algorithm. Suppose there is a 8bit integer 213(11010101 in binary), the algorithm works like this(each time merge two neighbor blocks):

1
2
3
4
5
6
7


+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+

Code

1
2
3
4
5
6
7
8
9

unsigned int hammingWeight(unsigned int x)
{
 x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
 x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
 x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
 return x;
}

Method 8 - XOR the number and -negative of number, till number becomes 0

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int myBitCount(long L) {
	int count = 0;

	while (L != 0) {
		count++;
		L ^= L & -L;
	}

	return count;
}

Method 9 - Converting number to string and counting 1s

Code

1
2
3

public int hammingWeight(int n) {
	return (int) Integer.toBinaryString(n).chars().filter(c -> c == '1').count();
}