054 — Check ith Bit

এই note থেকে শুরু হচ্ছে bit manipulation-এর "পাঁচটা primitive"-এর গল্প — check, set, clear, toggle আর lowest-bit-clear। আজ প্রথমটা: একটা সংখ্যার নির্দিষ্ট জায়গার bit জ্বলছে কিনা সেটা দেখা। মূল হাতিয়ার একটাই — mask = 1 << i। এই একটা idea একবার বুঝলে পরের তিন-চারটা problem এমনিই সহজ হয়ে যাবে। ধীরে পড়ো।

Source

• 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 পড়তে পারা)

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। এটুকুই।

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 দিয়ে শুধু সেটা পড়ো।

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 বদলায়।

4. Real-life analogy

ভাবো একটা লম্বা সুইচবোর্ড — সারি সারি অনেকগুলো light switch। তুমি জানতে চাও বাঁ দিক থেকে নয়, ডান দিক থেকে i নম্বর switch-টা on আছে নাকি off।

হাতে একটা টর্চলাইট (mask) নাও যেটা শুধু ওই একটা switch-এর উপর আলো ফেলে — বাকি সব অন্ধকার। এখন তাকিয়ে দেখো: ওই switch-এ আলো পড়ে কিছু দেখা গেল (1, on) নাকি কিছুই নেই (0, off)। সেই টর্চলাইটই হলো 1 << i, আর "তাকিয়ে দেখা" হলো &।

5. Visual explanation

n = 13, i = 2 — mask দিয়ে check:

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 নেভানো):

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-কে ডানে এনে পড়া):

n        = 1 1 0 1
n >> 2   = 0 0 1 1     (ঘর 2 এখন একদম ডানে)
(n>>2)&1 =       1     ->  bit 2 জ্বলছে ✓

6. Example input and output

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 নয়।

7. Brute force thinking

mask না জানলে, প্রথমে মাথায় আসে — পুরো binary বের করে (053-এর মতো) তারপর i-তম জায়গাটা দেখা:

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 চালাচ্ছি।

brute : পুরো binary বানাও (O(log n)), তারপর index দেখো
smart : সরাসরি ওই একটা ঘরে টর্চ ফেলো (O(1))

মূল অপচয়: চাই একটা ঘরের খবর, কিন্তু খুঁড়ছি পুরো সারি।

9. Better thinking

mask বানিয়ে এক ধাপে পড়ো — n & (1 << i) শূন্য কিনা দেখো। অথবা shift করে (n >> i) & 1:

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 সবেতেই এই একই টর্চ ব্যবহার হবে।

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।

12. Python solution

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

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

এটাই হৃদয়। 1 << i বানায় mask — শুধু i-তম ঘরে 1। n & mask শুধু সেই ঘরের bit রাখে, বাকি সব 0। ফল 0 না হলে মানে ওই ঘরে 1 ছিল → True। (bracket গুরুত্বপূর্ণ — precedence ফাঁদ এড়াতে।)

return ((n >> i) & 1) == 1

বিকল্প পথ: n >> i দিয়ে পুরো সংখ্যা i ঘর ডানে ঠেলি, ফলে target bit একদম ডানে আসে। তারপর & 1 দিয়ে শুধু সেই last bit পড়ি। এটা 1 হলে bit জ্বলা।

assert লাইনগুলো নিজেদের যাচাই করছে, আর nested for loop দুই method-কে 64×8 ক্ষেত্রে মিলিয়ে নিচ্ছে। সব ঠিক থাকলে সব test pass! ছাপে।

14. Output walkthrough

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

True
False
True
সব test pass!

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

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 নয়।

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 (https://leetcode.com/problems/single-number/) — bit-by-bit চিন্তা গভীরে নিয়ে যায়।

19. Pattern learned

Bit masking with 1 << i — n & (1 << i) দিয়ে নির্দিষ্ট bit পড়া, বা (n >> i) & 1। বড় শিক্ষা: পুরো সংখ্যা না খুঁড়ে, একটা টর্চ (mask) দিয়ে শুধু target ঘরে আলো ফেলা যায় — O(1)-এ। এই mask = টর্চ ছবিটাই পরের set/clear/toggle-এর ভিত্তি।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "i-তম bit check = n & (1 << i) শূন্য কিনা দেখা, বা (n >> i) & 1। mask হলো টর্চলাইট — শুধু এক ঘরে আলো; bracket দিতে ভুলো না।"

পরের ধাপ → 055 — Set ith Bit (একই mask দিয়ে এবার bit জ্বালাব)। সম্পর্কিত → 056 — Clear ith Bit · 057 — Toggle 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"।