Problem link ও উৎস
- **Original source:** Classic exercise (bit primitive — check)
- **Platform:** Classic exercise / — (specific judge নেই)
- **Topic:** Math-based programming fundamentals → Level 4: Bit Manipulation → bit primitives
- **Difficulty:** Easy
- **Pattern:** mask & (AND দিয়ে নির্দিষ্ট bit পড়া)
- **Basic idea inherited from:** 053 — Binary Representation (binary পড়তে পারা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer `n` আর একটা index `i` দেওয়া আছে। বলতে হবে — `n`-এর binary রূপে ডান দিক থেকে `i`-তম bit (0 থেকে গোনা) **জ্বলছে** (1) নাকি **নেভানো** (0)।
যেমন `n = 13 = 1101`:
- bit 0 → 1 (জ্বলছে)
- bit 1 → 0 (নেভানো)
- bit 2 → 1 (জ্বলছে)
- bit 3 → 1 (জ্বলছে)
ডান থেকে গোনা, একদম ডানের ঘর index 0। এটুকুই।
### Input ও output {#6-example-input-and-output}
```text
n, i -> output (True = জ্বলছে)
---------------------------------
13, 0 -> True (1101-এর ঘর 0 = 1)
13, 1 -> False (ঘর 1 = 0)
13, 2 -> True (ঘর 2 = 1)
13, 3 -> True (ঘর 3 = 1)
13, 4 -> False (ঘর 4 নেই -> 0)
0, 0 -> False (শূন্যের কোনো bit জ্বলা নেই)
8, 3 -> True (8 = 1000, শুধু ঘর 3)
```
মজার edge case: `i` যদি সংখ্যার bit-সংখ্যার চেয়ে বড় হয় (যেমন 13, i=4) — সেই উঁচু ঘর এমনিতেই 0, তাই `False`। কোনো error নয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা লম্বা সুইচবোর্ড — সারি সারি অনেকগুলো light switch। তুমি জানতে চাও বাঁ দিক থেকে নয়, ডান দিক থেকে `i` নম্বর switch-টা on আছে নাকি off।
হাতে একটা টর্চলাইট (mask) নাও যেটা **শুধু** ওই একটা switch-এর উপর আলো ফেলে — বাকি সব অন্ধকার। এখন তাকিয়ে দেখো: ওই switch-এ আলো পড়ে কিছু দেখা গেল (1, on) নাকি কিছুই নেই (0, off)। সেই টর্চলাইটই হলো `1 << i`, আর "তাকিয়ে দেখা" হলো `&`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **053 (Binary Representation)**-এর উপর। 053-এ তুমি পুরো সংখ্যাকে bit-এর সারি হিসেবে দেখতে শিখেছিলে — "13 মানে 1101"। সেই চোখ না থাকলে "i-তম bit" কথাটারই কোনো মানে হয় না।
এখন 053-এর সাথে পার্থক্য: 053-এ পুরো binary বের করতে loop চালাতে হতো; এখানে শুধু **একটা** bit চাই, তাই O(1)-এ সরাসরি পড়া যায়। আর এই 054 হলো পরের তিন ভাইয়ের জনক:
- **055 (Set)** — bit জ্বালানো
- **056 (Clear)** — bit নেভানো
- **057 (Toggle)** — bit উল্টানো
তিনটাই একই `mask = 1 << i` ব্যবহার করে, শুধু operator বদলায়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **masking with AND**। `&` operator-এর স্বভাব: `bit & 1 = bit` (যা আছে তাই দেখায়), আর `bit & 0 = 0` (সব মুছে দেয়)।
তাই যদি একটা সংখ্যা বানাই যার **শুধু** `i`-তম ঘরে 1 (বাকি সব 0), সেটা দিয়ে AND করলে শুধু সেই একটা ঘরের bit-ই টিকে থাকবে, বাকি সব 0 হয়ে যাবে। সেই বিশেষ সংখ্যাটা হলো **mask = `1 << i`** — "1-কে i ঘর বাঁয়ে ঠেলা"।
আরেকভাবে: আগে `n`-কে `i` ঘর ডানে সরাও (`n >> i`), যাতে target bit একদম ডানে চলে আসে, তারপর `& 1` দিয়ে শুধু সেটা পড়ো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
mask না জানলে, প্রথমে মাথায় আসে — পুরো binary বের করে (053-এর মতো) তারপর i-তম জায়গাটা দেখা:
```python
def check_bit_brute(n, i):
bits = []
while n > 0:
bits.append(n % 2) # last bit আগে
n //= 2
if i >= len(bits):
return False # ওই ঘর নেই -> 0
return bits[i] == 1 # bits[0] = last bit, তাই index সরাসরি মেলে
```
এটা ঠিক কাজ করে — পুরো সারি বানিয়ে নির্দিষ্ট ঘরটা দেখি। কিন্তু একটা bit-এর জন্য পুরো সারি বানানো বাড়াবাড়ি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
brute force-এ আমরা **সব** bit বের করছি, যদিও দরকার মাত্র **একটা**। `n` যদি বিশাল হয় (যেমন 10⁹, প্রায় 30টা bit), আর আমরা শুধু bit 2 জানতে চাই — তবু পুরো 30টা bit বানিয়ে loop চালাচ্ছি।
```text
brute : পুরো binary বানাও (O(log n)), তারপর index দেখো
smart : সরাসরি ওই একটা ঘরে টর্চ ফেলো (O(1))
```
মূল অপচয়: চাই একটা ঘরের খবর, কিন্তু খুঁড়ছি পুরো সারি।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
mask বানিয়ে এক ধাপে পড়ো — `n & (1 << i)` শূন্য কিনা দেখো। অথবা shift করে `(n >> i) & 1`:
```python
def check_bit(n, i):
return (n & (1 << i)) != 0
def check_bit_shift(n, i):
return (n >> i) & 1 == 1
```
কোনো loop নেই, পুরো সংখ্যা বানানো নেই — শুধু একটা shift আর একটা AND। তাই O(1), `n` যত বড়ই হোক।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **পুরো সংখ্যা না খুঁড়ে, একটা টর্চ (`1 << i`) দিয়ে শুধু target ঘরে আলো ফেলো।**
`1 << i` মানে এমন একটা সংখ্যা যার শুধু `i`-তম bit জ্বলা। `&`-এর স্বভাব হলো "যেখানে mask-এ 1, সেখানে original কী আছে দেখাও; যেখানে mask-এ 0, সব মুছে দাও"। তাই `n & (1 << i)` শুধু ওই একটা ঘরের সত্যিটা ফেরত দেয়। এই "mask = টর্চলাইট" ছবিটা গেঁথে নাও — পরের set/clear/toggle সবেতেই এই একই টর্চ ব্যবহার হবে।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 13`, `i = 2` — mask দিয়ে check:
```text
n = 1 1 0 1 (13)
i = 2 -> mask = 1 << 2
mask = 0 1 0 0 (শুধু ঘর 2 জ্বলা)
--- --- --- ---
n & mask= 0 1 0 0 ফল ≠ 0 -> bit 2 জ্বলছে ✓
```
এবার `i = 1` (যেখানে bit নেভানো):
```text
n = 1 1 0 1
mask = 0 0 1 0 (1 << 1)
--- --- --- ---
n & mask= 0 0 0 0 ফল = 0 -> bit 1 নেভানো
```
আর shift-method (target bit-কে ডানে এনে পড়া):
```text
n = 1 1 0 1
n >> 2 = 0 0 1 1 (ঘর 2 এখন একদম ডানে)
(n>>2)&1 = 1 -> bit 2 জ্বলছে ✓
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 13`, `i = 2` — mask method:
| step | কাজ | মান (4-bit) |
| --- | --- | --- |
| 1 | শুরু: n | 1101 |
| 2 | mask = 1 << 2 | 0100 |
| 3 | n & mask | 0100 |
| 4 | ফল != 0? | হ্যাঁ → bit জ্বলছে |
উত্তর: `True`। এখন `i = 1`:
| step | কাজ | মান (4-bit) |
| --- | --- | --- |
| 1 | n | 1101 |
| 2 | mask = 1 << 1 | 0010 |
| 3 | n & mask | 0000 |
| 4 | ফল != 0? | না → bit নেভানো |
উত্তর: `False`। মিলিয়ে দেখো 1101-এর ঘর 1 সত্যিই 0।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def check_bit(n, i):
"""n-এর i-তম bit (ডান থেকে, 0-indexed) জ্বলা হলে True।"""
return (n & (1 << i)) != 0
def check_bit_shift(n, i):
"""একই উত্তর, shift method: target bit-কে ডানে এনে পড়া।"""
return ((n >> i) & 1) == 1
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert check_bit(13, 0) is True # 1101 -> ঘর 0 = 1
assert check_bit(13, 1) is False # ঘর 1 = 0
assert check_bit(13, 2) is True # ঘর 2 = 1
assert check_bit(13, 3) is True # ঘর 3 = 1
assert check_bit(13, 4) is False # ঘর নেই -> 0
assert check_bit(0, 0) is False # শূন্যের bit জ্বলা নেই
assert check_bit(8, 3) is True # 1000
# দুই method একই উত্তর দেয় কিনা cross-check
for n in range(0, 64):
for i in range(0, 8):
assert check_bit(n, i) == check_bit_shift(n, i)
print(check_bit(13, 0)) # True
print(check_bit(13, 1)) # False
print(check_bit(13, 2)) # True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
return (n & (1 << i)) != 0
```
এটাই হৃদয়। `1 << i` বানায় mask — শুধু `i`-তম ঘরে 1। `n & mask` শুধু সেই ঘরের bit রাখে, বাকি সব 0। ফল 0 না হলে মানে ওই ঘরে 1 ছিল → `True`। (bracket গুরুত্বপূর্ণ — precedence ফাঁদ এড়াতে।)
```text
return ((n >> i) & 1) == 1
```
বিকল্প পথ: `n >> i` দিয়ে পুরো সংখ্যা `i` ঘর ডানে ঠেলি, ফলে target bit একদম ডানে আসে। তারপর `& 1` দিয়ে শুধু সেই last bit পড়ি। এটা 1 হলে bit জ্বলা।
`assert` লাইনগুলো নিজেদের যাচাই করছে, আর nested `for` loop দুই method-কে 64×8 ক্ষেত্রে মিলিয়ে নিচ্ছে। সব ঠিক থাকলে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
True
False
True
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: (13,0)→True, (13,1)→False, (13,2)→True। সব `assert` (cross-check loop সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — একটা shift আর একটা AND, ব্যস। `n` 13 হোক বা 10⁹, কাজ একই — পুরো সংখ্যা না দেখে শুধু target ঘরে আলো ফেলছি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — কোনো list, array কিছু লাগছে না; শুধু কয়েকটা int। mask-ও একটা সংখ্যা মাত্র।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`&` আর `and` গুলিয়ে ফেলা** — `n and (1 << i)` ভুল; bitwise কাজে সবসময় `&`। (README-র common mistake #1।)
2. **Precedence ফাঁদ** — `n & 1 << i == 0` মানে আসলে অন্য কিছু! `==` আর `<<`-এর precedence ভিন্ন। সবসময় bracket: `(n & (1 << i)) != 0`।
3. **`1 << i` ভুলে `i << 1` লেখা** — `1 << 3 = 8` (mask), কিন্তু `3 << 1 = 6` (double)। mask মানে "1-কে i ঘর বাঁয়ে"।
4. **ফল 1 আশা করা** — `n & (1 << i)` জ্বলা bit-এ ফেরত দেয় `1 << i` (যেমন 4), `1` নয়! তাই `== 1` নয়, `!= 0` লেখো। (shift method-এ অবশ্য `== 1` ঠিক, কারণ আগে ডানে এনেছি।)
5. **0-indexing ভুলে যাওয়া** — ডান থেকে প্রথম ঘর index 0, index 1 নয়।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **055 — Set ith Bit** (এই repo) — একই mask দিয়ে bit জ্বালানো।
- **056 — Clear ith Bit** / **057 — Toggle ith Bit** (এই repo) — mask দিয়ে নেভানো / উল্টানো।
- **058 — Count Set Bits** (এই repo) — প্রতিটা bit check করে 1 গোনা।
- **LeetCode — Single Number** (