Skip to content
Hello Python

Count Set Bits

Practice ExerciseIntermediateMediumArrayBit Manipulation

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement count_set_bits(value). value is a nonnegative integer. Return the number of 1 bits without using bin or int.bit_count.

Starter code

def count_set_bits(value):
    pass
Test cases

mixed-bits

{
  "args": [
    45
  ]
}

Expected: 4

power-of-two

{
  "args": [
    64
  ]
}

Expected: 1

Wizard outline
  1. Step 1: Define the zero state

    Return zero when no set bit exists. Zero is the loop terminal and establishes the count identity.

  2. Step 2: Clear the lowest set bit

    Recognize one set bit in a power of two. value & (value - 1) removes exactly the least significant one.

  3. Step 3: Repeat for every set bit

    Count arbitrary nonnegative bit patterns. Each transition removes one and only one set bit, so the number of transitions equals the answer.

Footguns and prerequisites
  • Right-shifting a negative Python integer never reaches zero.
  • Using value - 1 without parentheses can obscure precedence.
  • functions
  • lists and tuples
  • control flow
Reviewed references
Recommended approach and implementation

Repeatedly clear the least significant set bit and count transitions.

Why it works: For positive value, value & (value - 1) removes exactly one set bit. Repeating reaches zero after exactly the original number of set bits.

def count_set_bits(value):
    count = 0
    while value:
        value &= value - 1
        count += 1
    return count