একটি পজিটিভ সংখ্যার বাইনারি রিপ্রেজেন্টেশনে নির্দিত রেঞ্জ (L থেকে R) এ কতটি সেট বিট (১) আছে তা বের করার দুটি পদ্ধতি।
১. bin() ও স্লাইসিং ব্যবহার
bin(n)দিয়ে বাইনারি স্ট্রিং বানান।[2:]দিয়ে '0b' বাদ দিন।- স্ট্রিং রিভার্স করুন (LSB প্রথমে আসার জন্য)।
- ইনডেক্স
l-1থেকেr-1পর্যন্ত '১' গণনা করুন।
উদাহরণ
def SetBits_cnt(n, l, r):
bin_val = bin(n)[2:]
bin_val = bin_val[::-1]
print(len([bin_val[i] for i in range(l-1, r) if bin_val[i] == '1']))
SetBits_cnt(83, 1, 6)
# Output: 3
২. বিটওয়াইজ অপারেটর ব্যবহার
bit_num = ((1 << r) - 1) ^ ((1 << (l-1)) - 1)দিয়ে রেঞ্জের মাস্ক বানান।n & bit_numদিয়ে রেঞ্জের বিটগুলো আলাদা করুন।- ব্রায়ান কের্নিঘ্যানের অ্যালগরিদম দিয়ে সেট বিট গণনা করুন।
উদাহরণ
def trackBitsInRange(n, l, r):
bit_num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1)
return trackSetBits(n & bit_num)
def trackSetBits(n):
count = 0
while n:
n &= (n - 1)
count += 1
return count
print(trackBitsInRange(83, 1, 6)) # Output: 3
