Question

Count Set Bit in Binary Number.

3 = 00000011 => 2

128 = 10000000 => 1

Solution

Bits counting algorithm (Brian Kernighan). Basic idea is clear 1 bit at a time.

This algorithm goes through as many iterations as there are set bits. In the worst case, it will pass once per bit. An integer n has log(n) bits, hence the worst case is O(log(n)).

Code

public int countSetBit(String binary) {
	int num = Integer.parseInt(binary, 2);
	int count = 0;
	while (num != 0) {
		num &= num - 1;
		count++;
	}
	return count;
}