058 — Count Set Bits¶

এখন আসছে bit-জগতের সবচেয়ে বিখ্যাত trick — n & (n - 1)। প্রশ্নটা সরল: একটা সংখ্যার binary-তে কতগুলো 1 আছে? naive ভাবে প্রতিটা bit গুনতে পারো, কিন্তু একটা জাদুকরি লাইন আছে যেটা শুধু জ্বলা bit-গুলোর সমান বার ঘোরে। এটাকে বলে popcount (population count)। interview-তে "Number of 1 Bits" নামে খুব common। চলো বুঝি।

Source¶

Original source: LeetCode — Number of 1 Bits
Platform: LeetCode — https://leetcode.com/problems/number-of-1-bits/ (related: Counting Bits — https://leetcode.com/problems/counting-bits/)
Topic: Math-based programming fundamentals → Level 4: Bit Manipulation → popcount
Difficulty: Easy
Pattern: n & (n - 1) loop (lowest set bit বারবার মুছে গোনা)
Basic idea inherited from: 054 — Check ith Bit (bit পড়া; এখানে গোনা)

1. Problem in simple words¶

একটা non-negative integer n দেওয়া আছে। বলতে হবে এর binary রূপে মোট কতগুলো 1 আছে (set bit-এর সংখ্যা)।

যেমন:

13 = 1101 → তিনটা 1 → উত্তর 3
7 = 111 → তিনটা 1 → 3
8 = 1000 → একটা 1 → 1
0 = 0 → শূন্যটা 1 → 0

এই গোনাটাকেই বলে popcount বা Hamming weight।

2. What is the math idea?¶

দুটো idea আছে। সহজটা: প্রতিটা bit পড়ো (054-এর check), 1 হলে গোনো — মোট log n ধাপ।

চালাকটা: n & (n - 1) এক ঝটকায় সবচেয়ে নিচের জ্বলা bit মুছে ফেলে। কারণ n - 1 করলে lowest set bit-টা 0 হয় আর তার ডানের সব 0-গুলো 1 হয়ে যায়; তারপর AND করলে ওই অংশ সাফ, বাকি অক্ষত। তাই বারবার n &= n - 1 করলে প্রতিবার ঠিক একটা জ্বলা bit মুছি — যতবার মুছতে পারলাম, ততগুলোই 1 ছিল।

এটার সুবিধা: loop ঘোরে শুধু জ্বলা bit-এর সমান বার, মোট bit-এর সমান নয়।

3. Which basic idea does this inherit from?¶

দাঁড়িয়ে আছে 054 (Check ith Bit)-এর উপর। 054-এ একটা bit জ্বলা কিনা পড়তে শিখেছ; এখানে সব জ্বলা bit গুনছ। naive version তো সরাসরি 054-এর check-ই বারবার চালায়।

আর n & (n - 1) trick-টা এই 058 থেকেই আসে, যেটা পরে 059 (Power of Two)-এর সরাসরি ভিত্তি — power of two মানে ঠিক একটা set bit, তাই একবার n & (n - 1) করলেই 0।

4. Real-life analogy¶

ভাবো একটা ঘরে কয়েকটা মোমবাতি জ্বলছে, বাকি নেভানো। তুমি জানতে চাও কতগুলো জ্বলছে।

naive way: প্রতিটা মোমবাতির সামনে গিয়ে দেখো জ্বলছে কিনা — সব ক'টা ঘুরতে হয়, এমনকি নেভানোগুলোও।
চালাক way: প্রতিবার শুধু "সবচেয়ে কাছের জ্বলন্ত মোমবাতি" নিভিয়ে দাও আর গুনে রাখো — যতবার নেভাতে পারলে, ততগুলোই জ্বলছিল। নেভানো মোমবাতির দিকে তাকাতেই হলো না।

সেই "সবচেয়ে কাছের জ্বলন্ত নিভিয়ে দেওয়া"-ই হলো n & (n - 1)।

5. Visual explanation¶

দেখো n & (n - 1) কীভাবে lowest set bit মোছে (n = 12 = 1100):

n     = 1 1 0 0      lowest set bit ★ এই ঘরে
            ★
n - 1 = 1 0 1 1      ★ ঘর 0, তার ডানের সব 1
        --- --- --- ---
AND   = 1 0 0 0      ★ আর তার ডান সব সাফ -> একটা bit গেল

এবার পুরো popcount loop (n = 13 = 1101):

ধাপ 1: n = 1101  ->  n & (n-1) = 1100   count = 1
ধাপ 2: n = 1100  ->  n & (n-1) = 1000   count = 2
ধাপ 3: n = 1000  ->  n & (n-1) = 0000   count = 3
        n = 0 -> থামো
উত্তর: 3 (তিনবার মুছলাম = তিনটা 1 ছিল) ✓

লক্ষ করো — মাত্র 3 বার ঘুরল, যদিও 13 চার-bit। জ্বলা bit যতগুলো, ততবারই।

6. Example input and output¶

n     ->  output (কতগুলো 1)
---------------------------
13    ->  3        (1101)
7     ->  3        (111)
8     ->  1        (1000)
0     ->  0        (কোনো 1 নেই)
255   ->  8        (11111111, সব জ্বলা)
1023  ->  10       (দশটা 1)
1     ->  1        (1)

edge case: n = 0 → loop একবারও চলবে না → 0। আর "সব bit জ্বলা" সংখ্যায় (255, 1023) loop পুরো bit-সংখ্যার সমান বার ঘোরে।

7. Brute force thinking¶

সবচেয়ে সরল — প্রতিটা bit পড়ো (054-এর & 1), 1 হলে গোনো, তারপর >> 1 দিয়ে পরের bit-এ যাও:

def count_set_bits_brute(n):
    count = 0
    while n > 0:
        count += n & 1      # last bit 1 হলে গোনো
        n >>= 1             # পরের bit-এ সরো
    return count

কাজ করে — একদম সোজা, প্রতিটা bit একবার করে দেখি। কিন্তু এটা সব bit ঘোরে, এমনকি নেভানো bit-ও।

8. Why brute force may be slow¶

brute force loop ঘোরে সংখ্যার মোট bit-সংখ্যার সমান বার — যেমন 32-bit সংখ্যায় 32 বার, যদিও হয়তো মাত্র 2টা bit জ্বলা।

n = 1000...000 (32-bit, শুধু সবচেয়ে উপরে একটা 1):
  brute      : 32 বার ঘোরে (সব bit দেখে)
  n & (n-1)  : মাত্র 1 বার (একটাই জ্বলা bit)

মূল অপচয়: নেভানো bit-গুলোও ঘুরে দেখা, যদিও তারা গোনায় কিছু যোগ করে না। n & (n - 1) সেগুলো এড়িয়ে যায়।

9. Better thinking¶

n & (n - 1) দিয়ে প্রতিবার ঠিক একটা জ্বলা bit মুছি, যতবার মুছলাম গুনি:

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1          # lowest set bit মুছে দাও
        count += 1
    return count

loop ঘোরে শুধু জ্বলা bit-এর সমান বার (Kernighan's algorithm)। নেভানো bit-গুলোয় হাতই দিতে হয় না।

10. Thinking tweak¶

আসল "আহা!" — n - 1 মানে সবচেয়ে ডানের 1-টা "ভাঙানো" (100 টাকার নোট ভাঙানোর মতো); ভাঙা অংশের সাথে AND করলে ঠিক সেই একটা bit মুছে যায়।

n - 1 করলে lowest set bit 0 হয়, আর তার ডানের সব 0 হয়ে যায় 1। সেই pattern-এর সাথে & করলে lowest set bit আর তার ডান — সব সাফ, বাকি সব অক্ষত। তাই প্রতিবার ঠিক একটা bit যায়, আর loop নেভানো bit এড়িয়ে শুধু জ্বলা bit গোনে। এই "ভাঙানো + AND = একটা bit মোছা" ছবিটাই 059-এর power-check-এর চাবিও।

11. Step-by-step dry run¶

n = 13 (Kernighan):

step	n (শুরুতে, binary)	n & (n-1)	count
1	1101	1100	1
2	1100	1000	2
3	1000	0000	3
—	0 → থামল	—	3

উত্তর: 3। মিলিয়ে দেখো 1101-এ সত্যিই তিনটা 1। মাত্র 3 ধাপ, যদিও 4-bit সংখ্যা।

12. Python solution¶

def count_set_bits(n):
    """n-এর binary-তে কতগুলো 1 আছে (popcount), Kernighan's trick।"""
    count = 0
    while n:
        n &= n - 1          # সবচেয়ে নিচের জ্বলা bit মুছে দাও
        count += 1
    return count


def count_set_bits_naive(n):
    """একই উত্তর, প্রতিটা bit পড়ে গোনা (যাচাইয়ের জন্য)।"""
    count = 0
    while n > 0:
        count += n & 1
        n >>= 1
    return count


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_set_bits(13) == 3        # 1101
assert count_set_bits(7) == 3         # 111
assert count_set_bits(8) == 1         # 1000
assert count_set_bits(0) == 0         # কোনো 1 নেই
assert count_set_bits(255) == 8       # 11111111
assert count_set_bits(1023) == 10
assert count_set_bits(1) == 1

# দুই method একই উত্তর দেয়, আর Python-এর bin().count('1')-এর সাথে মেলে
for k in range(0, 1025):
    expected = bin(k).count("1")
    assert count_set_bits(k) == expected
    assert count_set_bits_naive(k) == expected

print(count_set_bits(13))    # 3
print(count_set_bits(8))     # 1
print(count_set_bits(255))   # 8
print("সব test pass!")

13. Line-by-line explanation¶

while n:
    n &= n - 1
    count += 1

এটাই হৃদয়। n &= n - 1 প্রতিবার সবচেয়ে নিচের জ্বলা bit মুছে দেয় (নোট-ভাঙানো + AND)। প্রতিবার মোছার সাথে count এক বাড়াই। n 0 হলে (সব bit মোছা শেষ) loop থামে। তাই count = মোট জ্বলা bit।

count += n & 1
n >>= 1

naive version: n & 1 last bit (0/1) সরাসরি count-এ যোগ করে, তারপর n >>= 1 দিয়ে পরের bit-এ সরি। যাচাইয়ের জন্য রাখা।

assert লাইন আর for loop দুই method-কে আর Python-এর bin(k).count("1")-কে 0 থেকে 1024 পর্যন্ত মিলিয়ে নিচ্ছে। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough¶

চালালে যা ছাপবে:

3
1
8
সব test pass!

প্রথম তিন লাইন তিনটা print থেকে: 13→3, 8→1, 255→8। সব assert (cross-check loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity¶

O(set bits) — Kernighan loop ঘোরে ঠিক যতগুলো 1 আছে ততবার (worst case সব bit জ্বলা হলে O(log n))। naive version সবসময় O(log n) — মোট bit-সংখ্যার সমান।

16. Space complexity¶

O(1) — শুধু count আর n variable; কোনো list/array নেই।

17. Common mistakes¶

n & (n - 1)-এ n = 0 ভুলে যাওয়া — while n শর্ত 0-তে এমনিই থামে, কিন্তু খেয়াল রেখো 0-এর উত্তর 0।
&= ভুলে = লেখা — n = n - 1 ভুল (শুধু এক কমায়, bit মোছে না); চাই n &= n - 1।
naive-এ >> 1 ভুলে infinite loop — last bit গোনার পর n >>= 1 না দিলে n কখনো 0 হবে না।
n & 1 == 0 precedence ফাঁদ — == আগে চলে, তাই (n & 1) bracket দাও।
negative ধরে নেওয়া — এই version non-negative-এর জন্য; Python-এ negative-এর bit unbounded।

18. Harder problems that inherit this idea¶

059 — Power of Two (এই repo) — একটাই set bit মানে n & (n - 1) == 0।
LeetCode — Counting Bits (https://leetcode.com/problems/counting-bits/) — 0 থেকে n সবার popcount একসাথে (DP দিয়ে আরও দ্রুত)।
LeetCode — Number of 1 Bits (https://leetcode.com/problems/number-of-1-bits/) — এই problem-এরই মূল রূপ।
LeetCode — Hamming Distance (https://leetcode.com/problems/hamming-distance/) — popcount(a ^ b), দুই trick একসাথে।

19. Pattern learned¶

Popcount via n & (n - 1) — প্রতিবার lowest set bit মুছে গোনা (Kernighan's algorithm)। বড় শিক্ষা: n - 1 সবচেয়ে ডানের 1 "ভাঙায়", AND সেই bit মোছে; তাই loop শুধু জ্বলা bit গোনে, নেভানো এড়িয়ে যায়। এই trick power-of-two check-এও সরাসরি কাজে লাগে।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "set bit গোনা = while n: n &= n - 1; count += 1। n & (n - 1) প্রতিবার একটা জ্বলা bit মোছে, তাই loop শুধু জ্বলা bit-এর সমান বার ঘোরে। এই trick থেকেই power-of-two check।"

পরের ধাপ → 059 — Power of Two (এই n & (n - 1) দিয়েই power-of-two চিনব এক লাইনে)। সম্পর্কিত → 054 — Check ith Bit।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)¶

JS-এ bitwise & 32-bit signed-এ কাজ করে, কিন্তু non-negative 32-bit-এর মধ্যে এই Kernighan trick নিখুঁত।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function countSetBits(n) {
  let count = 0;
  while (n) {                  // n !== 0 যতক্ষণ
    n &= n - 1;                // সবচেয়ে নিচের জ্বলা bit মুছে দাও
    count++;
  }
  return count;
}

// naive — প্রতিটা bit পড়ে গোনা (যাচাইয়ের জন্য)
function countNaive(n) {
  let count = 0;
  while (n > 0) { count += n & 1; n >>>= 1; }  // >>> unsigned shift
  return count;
}

// ---- test cases (file-এর example + edge case) ----
assert(countSetBits(13) === 3, "1101");
assert(countSetBits(7) === 3, "111");
assert(countSetBits(8) === 1, "1000");
assert(countSetBits(0) === 0, "কোনো 1 নেই");
assert(countSetBits(255) === 8, "11111111");
assert(countSetBits(1023) === 10, "1023");
assert(countSetBits(1) === 1, "1");
// দুই method + reference (toString(2)) — 0..1024 জুড়ে মিল
for (let k = 0; k <= 1024; k++) {
  const ref = k.toString(2).split("").filter((c) => c === "1").length;
  assert(countSetBits(k) === ref, "kern " + k);
  assert(countNaive(k) === ref, "naive " + k);
}
console.log("সব JS test pass!");

JS টীকা: bitwise op 32-bit signed-এ চলে — তাই top bit সেট হলে সংখ্যা negative দেখাতে পারে; non-negative shift-এ >>> 1 (unsigned) ব্যবহার করো, >> 1 নয়। 32-bit-এর বেশি bit গুনতে হলে BigInt লাগে (যেখানে >> 1n)।

22. TypeScript solution (with test cases)¶

function countSetBits(n: number): number {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;          // lowest set bit মোছা
    count++;
  }
  return count;
}

function expect(actual: number, expected: number, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [number, number]> = [
  [13, 3], [7, 3], [8, 1], [0, 0], [255, 8], [1023, 10], [1, 1],
];
for (const [n, want] of cases) expect(countSetBits(n), want, `popcount(${n})`);
console.log("সব TS test pass!");

TS টীকা: parameter ও return number declare করায় ভুলে string বা boolean পাঠানো compile-time-এই আটকায় — bit-গোনায় ভুল ধরনের ইনপুট আগেই বাদ।

23. কোথায় কাজে লাগে (real-world use)¶

Bitset / feature flags: একাধিক on/off flag এক integer-এ packed; "কয়টা চালু" জানতে popcount।
Hamming distance: দুই value কত bit-এ আলাদা = popcount(a ^ b) — error-correcting code, similarity, ML feature hashing-এ।
Sparse set cardinality: bitmask দিয়ে subset/visited-state রাখলে set-এর আকার এক popcount-এ (subset DP, graph state)।
Network / hardware: subnet mask-এ set bit গোনা (CIDR prefix length), parity/checksum হিসাব। মূল pattern — "n & (n-1) দিয়ে নেভানো bit এড়িয়ে শুধু জ্বলা bit-এ কাজ" — power-of-two check, lowest-set-bit isolation, Fenwick tree জুড়ে বড় ছবিতে ফেরে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নেই — বরং "common interview pattern" / "Google-style pattern"।