## Problem

Counting the number of 1 bits in the binary representation of a given integer.

## Analysis

### Method 1:

- shift the number right by one bit each time, and check whether the right-most bit is 1
- If yes, count++

### Method 2:

- if n is not 0, count++
- assign n = n & (n-1), repeat until n is 0

Time complexity

- method 1: theta(n)
- method 2: O(n)

## Code

Reference