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