Number of 1 Bits

NeetCode: Number of 1 Bits · LeetCode: 191. Number of 1 Bits · Difficulty: Easy

Given an unsigned 32-bit integer n, passed as a Java int that holds the same 32 bits, return the number of 1 bits in its binary representation (its Hamming weight).

Example

Text

Input:  n = 11            Output: 3     (1011)
Input:  n = 128           Output: 1     (10000000)
Input:  n = 2147483645    Output: 30

Brute force: test every bit

Java has no unsigned int. A value above 2^31 - 1 arrives as a negative int with the same 32 bits (for example -1 is all ones). Shift n right with >>>, which fills with zeros (the plain >> copies the sign bit), and look at the lowest bit with n & 1. That always takes 32 steps, however few bits are set.

Java

public class Main {
    static class Solution {
        public int hammingWeight(int n) {
            int count = 0;
            for (int i = 0; i < 32; i++) {
                count += n & 1;
                n >>>= 1; // unsigned shift: zeros enter from the left
            }
            return count;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.hammingWeight(11));
        System.out.println(s.hammingWeight(128));
        System.out.println(s.hammingWeight(2147483645));
        System.out.println(s.hammingWeight(0));
        System.out.println(s.hammingWeight(-1)); // all 32 bits set
    }
}

Output

Time: O(32), i.e. O(1) for a fixed width (O(w) for w bits). Space: O(1).

Optimal: clear the lowest set bit (Kernighan)

n & (n - 1) removes the lowest set bit of n: subtracting 1 flips that bit to 0 and turns all the zeros below it into 1s, so the AND wipes exactly that bit. Repeat until n is 0; the number of repeats is the number of set bits. The test is n != 0, not n > 0, because a value with the top bit set is a negative int. For Integer.MIN_VALUE (only the top bit set), n - 1 wraps to Integer.MAX_VALUE, and the AND still clears the lowest set bit.

n	n - 1	n & (n - 1)
`1011`	`1010`	`1010`
`1010`	`1001`	`1000`
`1000`	`0111`	`0000`

Java

public class Main {
    static class Solution {
        public int hammingWeight(int n) {
            int count = 0;
            while (n != 0) {
                n &= n - 1;
                count++;
            }
            return count;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.hammingWeight(11));
        System.out.println(s.hammingWeight(128));
        System.out.println(s.hammingWeight(2147483645));
        System.out.println(s.hammingWeight(0));
        System.out.println(s.hammingWeight(-1)); // all 32 bits set
    }
}

Output

Time: O(k) where k is the number of set bits (at most 32). Space: O(1). The standard library provides Integer.bitCount(n).