বিট ম্যানিপুলেশন#

বাইনারি সংখ্যা#

একটি বাইনারি সংখ্যা হলো ভিত্তি-২ সংখ্যা পদ্ধতি বা বাইনারি সংখ্যা পদ্ধতিতে প্রকাশিত একটি সংখ্যা, এটা গাণিতিক প্রকাশের একটি পদ্ধতি যা শুধুমাত্র দুটি প্রতীক ব্যবহার করে: সাধারণত “0” (শূন্য) এবং “1” (এক)।

আমরা বলি একটি নির্দিষ্ট বিট সেট আছে, যদি এটা এক হয়, এবং ক্লিয়ার যদি এটা শূন্য হয়।

বাইনারি সংখ্যা $(a_k a_{k-1} \dots a_1 a_0)_2$ নিচের সংখ্যাটা উপস্থাপন করে:

$$(a_k a_{k-1} \dots a_1 a_0)_2 = a_k \cdot 2^k + a_{k-1} \cdot 2^{k-1} + \dots + a_1 \cdot 2^1 + a_0 \cdot 2^0.$$

উদাহরণস্বরূপ, বাইনারি সংখ্যা $1101_2$ সংখ্যা $13$ উপস্থাপন করে:

$$\begin{align} 1101_2 &= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \\ &= 1\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 13 \end{align}$$

কম্পিউটার পূর্ণসংখ্যাগুলোকে বাইনারি সংখ্যা হিসেবে উপস্থাপন করে। ধনাত্মক পূর্ণসংখ্যাগুলো (সাইনড এবং আনসাইনড উভয়) কেবল তাদের বাইনারি ডিজিট দিয়ে উপস্থাপিত হয়, এবং ঋণাত্মক সাইনড সংখ্যাগুলো (যেগুলো ধনাত্মক এবং ঋণাত্মক হতে পারে) সাধারণত টু’জ কম্প্লিমেন্ট দিয়ে উপস্থাপিত হয়।

unsigned int unsigned_number = 13;
assert(unsigned_number == 0b1101);

int positive_signed_number = 13;
assert(positive_signed_number == 0b1101);

int negative_signed_number = -13;
assert(negative_signed_number == 0b1111'1111'1111'1111'1111'1111'1111'0011);

CPU গুলো নির্দিষ্ট অপারেশন দিয়ে এই বিটগুলো ম্যানিপুলেট করতে অত্যন্ত দ্রুত। কিছু সমস্যায় আমরা এই বাইনারি সংখ্যা রিপ্রেজেন্টেশনগুলো আমাদের সুবিধায় ব্যবহার করতে পারি, এবং এক্সিকিউশন টাইম দ্রুত করতে পারি। এবং কিছু সমস্যায় (সাধারণত কম্বিনেটরিক্স বা ডায়নামিক প্রোগ্রামিং-এ) যেখানে আমরা ট্র্যাক করতে চাই একটা দেওয়া অবজেক্টের সেট থেকে কোন অবজেক্টগুলো আমরা ইতিমধ্যে বেছে নিয়েছি, আমরা কেবল একটি যথেষ্ট বড় ইন্টিজার ব্যবহার করতে পারি যেখানে প্রতিটি ডিজিট একটি অবজেক্ট উপস্থাপন করে এবং আমরা অবজেক্টটি বেছে নিলে বা বাদ দিলে ডিজিটটি সেট বা ক্লিয়ার করি।

বিট অপারেটর#

এই সব প্রবর্তিত অপারেটর ফিক্সড-লেংথ ইন্টিজারের জন্য একটি CPU-তে তাৎক্ষণিক (যোগের সমান গতি)।

বিটওয়াইজ অপারেটর#

$\&$ : বিটওয়াইজ AND অপারেটর তার প্রথম অপারেন্ডের প্রতিটি বিটকে দ্বিতীয় অপারেন্ডের সংশ্লিষ্ট বিটের সাথে তুলনা করে। যদি উভয় বিট ১ হয়, সংশ্লিষ্ট ফলাফল বিট ১ সেট করা হয়। অন্যথায়, সংশ্লিষ্ট ফলাফল বিট ০ সেট করা হয়।
$|$ : বিটওয়াইজ ইনক্লুসিভ OR অপারেটর তার প্রথম অপারেন্ডের প্রতিটি বিটকে দ্বিতীয় অপারেন্ডের সংশ্লিষ্ট বিটের সাথে তুলনা করে। যদি দুটি বিটের মধ্যে একটি ১ হয়, সংশ্লিষ্ট ফলাফল বিট ১ সেট করা হয়। অন্যথায়, সংশ্লিষ্ট ফলাফল বিট ০ সেট করা হয়।
$\wedge$ : বিটওয়াইজ এক্সক্লুসিভ OR (XOR) অপারেটর তার প্রথম অপারেন্ডের প্রতিটি বিটকে দ্বিতীয় অপারেন্ডের সংশ্লিষ্ট বিটের সাথে তুলনা করে। যদি একটি বিট ০ হয় এবং অন্যটি ১ হয়, সংশ্লিষ্ট ফলাফল বিট ১ সেট করা হয়। অন্যথায়, সংশ্লিষ্ট ফলাফল বিট ০ সেট করা হয়।
$\sim$ : বিটওয়াইজ কম্প্লিমেন্ট (NOT) অপারেটর একটি সংখ্যার প্রতিটি বিট উল্টে দেয়, যদি একটি বিট সেট থাকে তাহলে অপারেটর এটা ক্লিয়ার করবে, যদি এটা ক্লিয়ার থাকে তাহলে অপারেটর এটা সেট করবে।

উদাহরণ:

n         = 01011000
n-1       = 01010111
--------------------
n & (n-1) = 01010000

n         = 01011000
n-1       = 01010111
--------------------
n | (n-1) = 01011111

n         = 01011000
n-1       = 01010111
--------------------
n ^ (n-1) = 00001111

n         = 01011000
--------------------
~n        = 10100111

শিফট অপারেটর#

বিট শিফট করার জন্য দুটি অপারেটর আছে।

$\gg$ সংখ্যার শেষ কয়েকটি বাইনারি ডিজিট সরিয়ে ডানদিকে শিফট করে। প্রতি একটি শিফট ২ দ্বারা ইন্টিজার ভাগের প্রতিনিধিত্ব করে, তাই $k$ দ্বারা রাইট শিফট $2^k$ দ্বারা ইন্টিজার ভাগের প্রতিনিধিত্ব করে।
যেমন $5 \gg 2 = 101_2 \gg 2 = 1_2 = 1$ যা $\frac{5}{2^2} = \frac{5}{4} = 1$-এর সমান। তবে একটি কম্পিউটারের জন্য কিছু বিট শিফট করা ভাগ করার চেয়ে অনেক দ্রুত।
$\ll$ শূন্য ডিজিট যোগ করে বাঁদিকে শিফট করে। $k$ দ্বারা রাইট শিফটের মতোই, $k$ দ্বারা লেফট শিফট $2^k$ দ্বারা গুণের প্রতিনিধিত্ব করে।
যেমন $5 \ll 3 = 101_2 \ll 3 = 101000_2 = 40$ যা $5 \cdot 2^3 = 5 \cdot 8 = 40$-এর সমান।
তবে লক্ষ্য করো যে ফিক্সড-লেংথ ইন্টিজারের জন্য এর মানে হলো সবচেয়ে বাঁদিকের ডিজিটগুলো বাদ পড়া, এবং তুমি অনেক বেশি শিফট করলে সংখ্যাটা $0$ হয়ে যায়।

উপকারী কৌশল#

একটি বিট সেট/ফ্লিপ/ক্লিয়ার করা#

বিটওয়াইজ শিফট এবং কিছু মৌলিক বিটওয়াইজ অপারেশন ব্যবহার করে আমরা সহজেই একটি বিট সেট, ফ্লিপ বা ক্লিয়ার করতে পারি। $1 \ll x$ হলো একটি সংখ্যা যেখানে শুধুমাত্র $x$-তম বিট সেট, আর $\sim(1 \ll x)$ হলো একটি সংখ্যা যেখানে $x$-তম বিট ছাড়া সব বিট সেট।

$n ~|~ (1 \ll x)$ সংখ্যা $n$-এ $x$-তম বিট সেট করে
$n ~\wedge~ (1 \ll x)$ সংখ্যা $n$-এ $x$-তম বিট ফ্লিপ করে
$n ~\&~ \sim(1 \ll x)$ সংখ্যা $n$-এ $x$-তম বিট ক্লিয়ার করে

একটি বিট সেট আছে কিনা পরীক্ষা করা#

$x$-তম বিটের মান পরীক্ষা করা যায় সংখ্যাটিকে $x$ পজিশন ডানে শিফট করে, যাতে $x$-তম বিটটি এককের স্থানে আসে, তারপর ১-এর সাথে বিটওয়াইজ & করে এটা বের করা যায়।

bool is_set(unsigned int number, int x) {
    return (number >> x) & 1;
}

সংখ্যাটি ২-এর ঘাত দ্বারা বিভাজ্য কিনা পরীক্ষা করা#

AND অপারেশন ব্যবহার করে, আমরা পরীক্ষা করতে পারি একটি সংখ্যা $n$ জোড় কিনা কারণ $n ~\&~ 1 = 0$ যদি $n$ জোড় হয়, এবং $n ~\&~ 1 = 1$ যদি $n$ বিজোড় হয়। আরও সাধারণভাবে, $n$ ঠিক তখনই $2^{k}$ দ্বারা বিভাজ্য যখন $n ~\&~ (2^{k} − 1) = 0$।

bool isDivisibleByPowerOf2(int n, int k) {
    int powerOf2 = 1 << k;
    return (n & (powerOf2 - 1)) == 0;
}

আমরা ১-কে $k$ পজিশন বাঁয়ে শিফট করে $2^{k}$ গণনা করতে পারি। কৌশলটি কাজ করে, কারণ $2^k - 1$ হলো এমন একটি সংখ্যা যেখানে ঠিক $k$ টি ওয়ান আছে। এবং $2^k$ দ্বারা বিভাজ্য একটি সংখ্যায় সেই স্থানগুলোতে শূন্য ডিজিট থাকতে হবে।

একটি পূর্ণসংখ্যা ২-এর ঘাত কিনা পরীক্ষা করা#

২-এর ঘাত এমন একটি সংখ্যা যেখানে শুধুমাত্র একটি বিট আছে (যেমন $32 = 0010~0000_2$), আর সেই সংখ্যার আগের সংখ্যায় সেই ডিজিটটি সেট নেই এবং এর পরের সব ডিজিট সেট ($31 = 0001~1111_2$)। তাই একটি সংখ্যা এবং এর আগের সংখ্যার বিটওয়াইজ AND সর্বদা ০ হবে, কারণ তাদের কোনো সাধারণ সেট ডিজিট নেই। তুমি সহজেই যাচাই করতে পারো যে এটা কেবল ২-এর ঘাত এবং $0$ সংখ্যার জন্যই ঘটে, যেখানে ইতিমধ্যে কোনো ডিজিট সেট নেই।

bool isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

সবচেয়ে ডানদিকের সেট বিট ক্লিয়ার করা#

এক্সপ্রেশন $n ~\&~ (n-1)$ একটি সংখ্যা $n$-এর সবচেয়ে ডানদিকের সেট বিট বন্ধ করতে ব্যবহার করা যায়। এটা কাজ করে কারণ এক্সপ্রেশন $n-1$ সংখ্যা $n$-এর সবচেয়ে ডানদিকের সেট বিটের পরে সব বিট ফ্লিপ করে, সেই সবচেয়ে ডানদিকের সেট বিট সহ। তাই সেই সব ডিজিট মূল সংখ্যা থেকে ভিন্ন, এবং বিটওয়াইজ AND করলে সেগুলো সব ০ হয়ে যায়, আপনাকে সবচেয়ে ডানদিকের সেট বিট ফ্লিপ করা মূল সংখ্যা $n$ দেয়।

উদাহরণস্বরূপ, $52 = 0011~0100_2$ সংখ্যাটা কনসিডার করো:

n         = 00110100
n-1       = 00110011
--------------------
n & (n-1) = 00110000

ব্রায়ান কার্নিঘানের অ্যালগরিদম#

উপরের এক্সপ্রেশন দিয়ে আমরা সেট বিটের সংখ্যা গণনা করতে পারি।

ধারণাটা হলো একটি ইন্টিজারের শুধুমাত্র সেট বিটগুলো কনসিডার করা, এর সবচেয়ে ডানদিকের সেট বিট বন্ধ করে (গণনার পর), যাতে লুপের পরবর্তী ইটারেশন পরবর্তী ডানদিকের বিট কনসিডার করে।

int countSetBits(int n)
{
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

$n$ পর্যন্ত সেট বিট গণনা#

$n$ (সহ) পর্যন্ত সকল সংখ্যার সেট বিটের সংখ্যা গণনা করতে, আমরা $n$ পর্যন্ত সকল সংখ্যায় ব্রায়ান কার্নিঘানের অ্যালগরিদম চালাতে পারি। তবে এটা প্রতিযোগিতায় “Time Limit Exceeded” দেবে।

আমরা এই তথ্যটা ব্যবহার করতে পারি যে $2^x$ পর্যন্ত সংখ্যাগুলোর জন্য (অর্থাৎ $1$ থেকে $2^x - 1$ পর্যন্ত) $x \cdot 2^{x-1}$ টি সেট বিট আছে। এটা এভাবে দেখানো যায়।

0 ->   0 0 0 0
1 ->   0 0 0 1
2 ->   0 0 1 0
3 ->   0 0 1 1
4 ->   0 1 0 0
5 ->   0 1 0 1
6 ->   0 1 1 0
7 ->   0 1 1 1
8 ->   1 0 0 0

আমরা দেখতে পাচ্ছি যে সবচেয়ে বাঁদিকেরটি ছাড়া সব কলামে $4$ (অর্থাৎ $2^2$) টি সেট বিট আছে, অর্থাৎ $2^3 - 1$ পর্যন্ত সংখ্যায়, সেট বিটের সংখ্যা হলো $3 \cdot 2^{3-1}$।

এই নতুন জ্ঞান নিয়ে আমরা নিচের অ্যালগরিদম তৈরি করতে পারি:

দেওয়া সংখ্যার চেয়ে ছোট বা সমান $2$-এর সর্বোচ্চ ঘাত খোঁজো। একে $x$ ধরি।
$1$ থেকে $2^x - 1$ পর্যন্ত সেট বিটের সংখ্যা $x \cdot 2^{x-1}$ সূত্র ব্যবহার করে গণনা করো।
$2^x$ থেকে $n$ পর্যন্ত সবচেয়ে তাৎপর্যপূর্ণ বিটে সেট বিটের সংখ্যা গণনা করে যোগ করো।
$n$ থেকে $2^x$ বিয়োগ করো এবং নতুন $n$ ব্যবহার করে উপরের ধাপগুলো রিপিট করো।

int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            int x = std::bit_width(n) - 1;
            count += x << (x - 1);
            n -= 1 << x;
            count += n + 1;
        }
        return count;
}

অতিরিক্ত কৌশল#

$n ~\&~ (n + 1)$ সকল ট্রেইলিং ওয়ান ক্লিয়ার করে: $0011~0111_2 \rightarrow 0011~0000_2$।
$n ~|~ (n + 1)$ শেষ ক্লিয়ার বিট সেট করে: $0011~0101_2 \rightarrow 0011~0111_2$।
$n ~\&~ -n$ শেষ সেট বিট এক্সট্র্যাক্ট করে: $0011~0100_2 \rightarrow 0000~0100_2$।

আরও অনেক কৌশল Hacker’s Delight বইতে পাওয়া যায়।

ল্যাঙ্গুয়েজ এবং কম্পাইলার সাপোর্ট#

C++ এর কিছু অপারেশন C++20 থেকে bit স্ট্যান্ডার্ড লাইব্রেরির মাধ্যমে সাপোর্ট করে:

has_single_bit: সংখ্যাটি ২-এর ঘাত কিনা পরীক্ষা করে
bit_ceil / bit_floor: পরবর্তী ২-এর ঘাতে রাউন্ড আপ/ডাউন করে
rotl / rotr: সংখ্যার বিটগুলো রোটেট করে
countl_zero / countr_zero / countl_one / countr_one: লিডিং/ট্রেইলিং জিরো/ওয়ান গণনা করে
popcount: সেট বিটের সংখ্যা গণনা করে

এছাড়াও, কিছু কম্পাইলারে প্রিডিফাইনড ফাংশন আছে যা বিটের সাথে কাজ করতে সাহায্য করে। যেমন GCC Built-in Functions Provided by GCC-এ একটি তালিকা ডিফাইন করে যা C++-এর পুরানো ভার্সনেও কাজ করে:

__builtin_popcount(unsigned int) সেট বিটের সংখ্যা রিটার্ন করে (__builtin_popcount(0b0001'0010'1100) == 4)
__builtin_ffs(int) প্রথম (সবচেয়ে ডান) সেট বিটের ইনডেক্স খুঁজে বের করে (__builtin_ffs(0b0001'0010'1100) == 3)
__builtin_clz(unsigned int) লিডিং জিরোর সংখ্যা (__builtin_clz(0b0001'0010'1100) == 23)
__builtin_ctz(unsigned int) ট্রেইলিং জিরোর সংখ্যা (__builtin_ctz(0b0001'0010'1100) == 2)
__builtin_parity(x) বিট রিপ্রেজেন্টেশনে ওয়ানের সংখ্যার প্যারিটি (জোড় বা বিজোড়)

লক্ষ্য করো যে কিছু অপারেশন (C++20 ফাংশন এবং কম্পাইলার বিল্ট-ইন উভয়ই) GCC-তে বেশ ধীর হতে পারে যদি তুমি #pragma GCC target("popcnt") দিয়ে একটি নির্দিষ্ট কম্পাইলার টার্গেট সক্রিয় না করো।