056 — Clear ith Bit

Set-এর উল্টোটা: আজ শিখব একটা bit নেভাতে (clear, 0 বানানো)। এখানে একটা নতুন মোচড় আছে — ~ (NOT) দিয়ে mask-টা উল্টে নিতে হয়, তারপর &। পাঁচ primitive-এর তৃতীয় ভাই। ~-এর ব্যাপারে Python-এ একটা ছোট চমক আছে, সেটাও এই note-এ পরিষ্কার করে দেব। ধীরে পড়ো।

Source

• 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 দিয়ে &)

1. Problem in simple words

একটা integer n আর index i দেওয়া আছে। তোমাকে n-এর i-তম bit নিভিয়ে (0 বানিয়ে) নতুন সংখ্যা ফেরত দিতে হবে।

• bit আগে থেকে 1 হলে → 0 হয়ে যাবে, সংখ্যা কমবে
• bit আগে থেকে 0 হলে → কিছু বদলাবে না

যেমন n = 13 = 1101, i = 0:

1101  ->  ঘর 0 নেভাও  ->  1100 = 12

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 → অপরিবর্তিত।

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 উল্টাতে হয় — কারণ "নেভাতে" চাই উল্টানো প্যাটার্ন।

4. Real-life analogy

সুইচবোর্ডে আবার সেই magic switch। কিন্তু এবার তুমি চাও শুধু i নম্বর light off করতে, বাকি সব যেমন আছে তেমন।

ভাবো তোমার হাতে একটা মুখোশ (mask) — যেটায় target ঘর ছাড়া বাকি সব জায়গা খোলা (1), শুধু target ঘরটা ঢাকা (0)। সেই মুখোশের ভেতর দিয়ে দেখলে target light জোর করে নিভে যায় (ঢাকা = 0), বাকি সব light যেমন ছিল তেমন (খোলা = অপরিবর্তিত)। এই "শুধু একটা ঘর ঢাকা মুখোশ" হলো ~(1 << i)।

5. Visual explanation

n = 13, i = 0 — clear:

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) — কিছু বদলায় না:

n         = 1 1 0 1
~(1 << 1) = 1 1 0 1     (ঘর 1 ঢাকা)
          --- --- --- ---
n & ~mask = 1 1 0 1     (13)   ঘর 1 আগেই 0 ছিল -> অপরিবর্তিত

লক্ষ করো — & কখনো bit জ্বালায় না, শুধু নেভাতে পারে (বা একই রাখে)।

6. Example input and output

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"।

7. Brute force thinking

mask না জানলে, binary list বানিয়ে (053-এর মতো) ওই index-এ জোর করে 0 বসিয়ে আবার সংখ্যায় ফেরা মাথায় আসে:

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)। অথচ দরকার ছিল একটা ~ আর একটা &।

brute : list ভাঙো -> index-এ 0 -> আবার সংখ্যা গড়ো  (O(log n))
smart : n & ~(1 << i)                              (O(1))

এক bit নেভাতে পুরো সংখ্যা ভাঙা-গড়া অপচয়।

9. Better thinking

mask উল্টে এক ধাপে AND করো:

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।)

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।

12. Python solution

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

return n & ~(1 << i)

এটাই হৃদয়। 1 << i বানায় mask (শুধু target-এ 1)। ~ সেটা উল্টায় → শুধু target-এ 0, বাকি সব 1। n & ~mask: target ঘরে & 0 → force-0 (clear), বাকি ঘরে & 1 → অপরিবর্তিত। তাই ঠিক একটা ঘর নেভে।

return (n & (1 << i)) != 0

054-এর check — যাচাইয়ের জন্য, যাতে test-এ "clear করার পর সত্যিই নেভানো" নিশ্চিত হয়।

assert লাইন আর nested for loop নিজেরা যাচাই করছে: clear-এর পর bit সবসময় নেভানো, আর সংখ্যা হয় অপরিবর্তিত (আগেই নেভানো থাকলে) নয়তো ঠিক 1 << i কমে। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

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

12
13
0
সব test pass!

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

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 জ্বলা থাকলে নেভায়, নেভানো থাকলে জ্বালায়।

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 (https://leetcode.com/problems/power-of-two/) — n & (n - 1) দিয়ে একটাই set bit আছে কিনা যাচাই।
• LeetCode — Number of 1 Bits (https://leetcode.com/problems/number-of-1-bits/) — বারবার lowest bit clear করে গোনা।

19. Pattern learned

Clear bit with & ~mask — n & ~(1 << i)। বড় শিক্ষা: নেভাতে হলে mask উল্টাও (~): শুধু target-এ 0, বাকি 1; & force-0 করে, বাকি ঘর অক্ষত। set-এর সরাসরি mask আর clear-এর উল্টানো mask — এই বৈপরীত্যটাই মনে রাখার চাবি।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "i-তম bit নেভাতে n & ~(1 << i); mask উল্টে নাও যাতে শুধু target-এ 0। Python-এ ~ negative দেখায়, কিন্তু &-এর ফল ঠিক। clear vs toggle গুলিয়ো না।"

পরের ধাপ → 057 — Toggle ith Bit (এবার ^ দিয়ে bit উল্টাব — set/clear দুটোরই সাধারণীকরণ)। সম্পর্কিত → 054 — Check ith Bit · 055 — Set ith Bit।

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

---

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