0PricingLogin▼
Competitive Programming Academy · Lesson

Count Bits and Lowest Set Bit

Use popcount and the n & -n trick.

Counting the Ones

Many problems ask how many bits are set in a number, called its popcount. It shows up in subset sizes, parity checks, and scoring. 🔢

Python's Built-in Count

The fastest way to count set bits is the integer method bit_count(). No loop, no fuss, just the number of ones.

print((13).bit_count())  # 0b1101 has 3 ones

All lessons in this course

  1. AND, OR, XOR & Shifts
  2. Set, Clear & Toggle a Bit
  3. Count Bits and Lowest Set Bit
  4. Bitmasks as Tiny Sets
← Back to Competitive Programming Academy