Number of 1 Bits

Easy

The problem

Write n in binary (base 2) and return how many of its digits are 1.

Example 1
Input: n = 11
Output: 3
11 is 1011 in binary, which has three 1s.
Example 2
Input: n = 128
Output: 1
128 is 10000000 in binary.

Limits

0 ≤ n < 2^32 (fits in 32 bits)

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

What does n & (n − 1) do to the lowest set bit?

The idea

Repeat n &= n−1 and count how many times until n is 0.

Target: O(number of set bits)

Go function shape

func hammingWeight(n int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// HammingWeight: n & (n-1) clears the lowest set bit, so the loop runs once per 1-bit.
func HammingWeight(n uint32) int {
	count := 0
	for n != 0 {
		n &= n - 1
		count++
	}
	return count
}

// CountBits: bits of i = bits of i/2 (shift right) plus its last bit.
func CountBits(n int) []int {
	bits := make([]int, n+1)
	for i := 1; i <= n; i++ {
		bits[i] = bits[i>>1] + i&1
	}
	return bits
}

Read the lesson: Bit Manipulation & Math