easy

Number of 1 Bits

Count how many bits are set to 1 in the binary form of a number.

1. Define the problem

Number of 1 Bits

Given a positive integer n, return the number of set bits (1s) in its binary representation. Repeatedly apply n & (n - 1) , which clears the lowest set bit in one step. Count how many times that takes until n reaches 0.

Constraints

  • 1 ≤ n ≤ 231 - 1

Example

Inputn = 11 (binary 1011)
Output3

Explanation Binary 1011 has three 1 bits.

2. Know the words first

In plain terms

Set bit
A bit in the binary representation of a number whose value is 1.
n & (n - 1)
Subtracting 1 from n flips the lowest set bit to 0 and every bit below it to 1; AND-ing with n then turns off exactly that lowest set bit and leaves everything above it untouched — one of the handful of bit tricks worth memorizing.
3. Visualize the solution

Clear the lowest set bit until n reaches 0

Clear the lowest set bit until n reaches 0
Statusinit

n = 1011 (11). Lowest set bit is at position 0.

What happens in this step

n = 00001011  (11)

Three bits are set, at positions 0, 1, and 3. Each round below clears the lowest set bit using n & (n - 1) and counts it.
Step 1 of 4

Steps to visualize

  1. Start a bit count at 0.
  2. While n is not 0, compute n & (n - 1) — this clears the lowest set bit.
  3. Add one to the count each time a bit is cleared.
  4. Stop once n reaches 0; the count is the number of set bits.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Clear the lowest set bit until n reaches 0
Statusinit

n = 1011 (11). Lowest set bit is at position 0.

What happens in this step

n = 00001011  (11)

Three bits are set, at positions 0, 1, and 3. Each round below clears the lowest set bit using n & (n - 1) and counts it.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function hammingWeight(n) {
  let count = 0;

  while (n !== 0) {
    n &= n - 1;
    count++;
  }

  return count;
}
Time
O(k), k = number of set bits
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
n = 113example from the docstring
n = 1281a power of two has exactly one set bit
n = 2558every bit set within a byte
n = 11smallest valid input
n = 214748364530a large value near the upper bound of a 32-bit signed integer
n = 73consecutive low bits all set

Keep reading

TopicDescription
Bit ManipulationUse AND, OR, XOR, and shifts to solve problems directly on the binary representation of numbers, often in O(1) space.
Single NumberFind the one number in an array that does not appear exactly twice.
Counting BitsFor every number up to n, count how many bits are set to 1 in its binary form.
Missing NumberFind the one number missing from a list containing n distinct numbers from 0 to n.
Reverse BitsReverse the bits of a 32-bit unsigned integer.
Single Number IIFind the one number in an array that does not appear exactly three times.