Problem link ও উৎস
- **Original source:** LeetCode — Number of 1 Bits
- **Platform:** LeetCode —
(related: 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 পড়া; এখানে গোনা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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**।
### Input ও output {#6-example-input-and-output}
```text
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-সংখ্যার সমান বার ঘোরে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ঘরে কয়েকটা মোমবাতি জ্বলছে, বাকি নেভানো। তুমি জানতে চাও কতগুলো জ্বলছে।
- **naive way:** প্রতিটা মোমবাতির সামনে গিয়ে দেখো জ্বলছে কিনা — সব ক'টা ঘুরতে হয়, এমনকি নেভানোগুলোও।
- **চালাক way:** প্রতিবার শুধু "সবচেয়ে কাছের জ্বলন্ত মোমবাতি" নিভিয়ে দাও আর গুনে রাখো — যতবার নেভাতে পারলে, ততগুলোই জ্বলছিল। নেভানো মোমবাতির দিকে তাকাতেই হলো না।
সেই "সবচেয়ে কাছের জ্বলন্ত নিভিয়ে দেওয়া"-ই হলো `n & (n - 1)`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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।
### ভেতরের অঙ্ক {#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-এর সমান নয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল — প্রতিটা bit পড়ো (054-এর `& 1`), 1 হলে গোনো, তারপর `>> 1` দিয়ে পরের bit-এ যাও:
```python
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 জ্বলা।
```text
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 মুছি, যতবার মুছলাম গুনি:
```python
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-এর চাবিও।
### ছবিতে বোঝা {#5-visual-explanation}
দেখো `n & (n - 1)` কীভাবে lowest set bit মোছে (`n = 12 = 1100`):
```text
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`):
```text
ধাপ 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 যতগুলো, ততবারই।
### ছোট input-এ ধাপে ধাপে {#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 সংখ্যা।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
while n:
n &= n - 1
count += 1
```
এটাই হৃদয়। `n &= n - 1` প্রতিবার সবচেয়ে নিচের জ্বলা bit মুছে দেয় (নোট-ভাঙানো + AND)। প্রতিবার মোছার সাথে `count` এক বাড়াই। `n` 0 হলে (সব bit মোছা শেষ) loop থামে। তাই `count` = মোট জ্বলা bit।
```text
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
3
1
8
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: 13→3, 8→1, 255→8। সব `assert` (cross-check loop সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এ bitwise `&` 32-bit signed-এ কাজ করে, কিন্তু non-negative 32-bit-এর মধ্যে এই Kernighan trick নিখুঁত।
```javascript
// 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`)।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
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