Count Bits and Lowest Set Bit
Use popcount and the n & -n trick.
Count Bits and Lowest Set Bit is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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 onesCount with bin and count
If you forget bit_count, turn the number into binary text and tally the ones. It is slower but clear and easy to remember.
print(bin(13).count('1')) # 3The Lowest Set Bit
The lowest set bit is the rightmost 1 in a number. Isolating it is a key move for Fenwick trees and subset tricks later on.
Isolate It with n and -n
The famous trick n & -n keeps only the lowest set bit. Negatives in two's complement make this work like magic.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Why n and -n Works
Negating flips all bits and adds 1, so everything below the lowest 1 inverts. ANDing leaves just that single bit standing.
Drop the Lowest Set Bit
Subtracting 1 borrows through the trailing zeros, so n & (n - 1) erases the lowest set bit. Repeat it to peel ones off one by one.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Brian Kernighan's Count
Loop while the number is nonzero, clearing the lowest bit each time. The loop runs once per set bit, so it is fast for sparse popcount.
c = 0
while n:
n &= n - 1
c += 1Check a Power of Two
A positive power of two has exactly one set bit, so n & (n - 1) equals 0. One AND tells you instantly.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Parity from Bit Count
The parity of a number is just its popcount modulo 2. It answers odd-or-even-many-ones questions in a single step.
parity = (13).bit_count() & 1 # 1Pick the Fastest Tool
For raw speed use bit_count; to walk set bits use the n & (n-1) loop. Choosing the right tool keeps tight time limits happy. ⚡
Quick Check
Test the lowest-set-bit trick.
Recap: Counting Bits
You can count ones with bit_count, isolate the lowest bit via n & -n, and strip it with n & (n-1). Powerful one-liners. 🎉
Frequently asked questions
Is the “Count Bits and Lowest Set Bit” lesson free?
Yes — the full text of “Count Bits and Lowest Set Bit” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Count Bits and Lowest Set Bit”?
Use popcount and the n & -n trick. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Count Bits and Lowest Set Bit” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- AND, OR, XOR & Shifts
- Set, Clear & Toggle a Bit
- Count Bits and Lowest Set Bit
- Bitmasks as Tiny Sets