### 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;
}
```