এই লেখা পড়া শুরু করার আগে বিটওয়াইজ অপারেটরগুলো নিয়ে খুব ভাল আইডিয়া থাকতে হবে। সেজন্য পড়ে আসতে হবে বিটওয়াইজ অপারেটরগুলো নিয়ে লেখাটি।

আমরা এ পর্বে মূলত unsigned ডাটা টাইপ নিয়ে কাজ করবো। কারণ signed ডাটা টাইপের সবচেয়ে বামের বিটটি সাইনের জন্য বরাদ্দ থাকে। আর এ পর্বের শুরুতে আমরা জেনে রাখবো যে, বিট প্যাটার্নের সবচেয়ে ডানের বিটটিকে বলা হয় LSB (Least Significant Bit), এবং সবচেয়ে বামের বিটটি হল MSB (Most Significant Bit)।

তো শুরু করা যাক। আমরা এ পর্বে যে সকল বিষয় নিয়ে আলোচনা করবো তা হল বিটওয়াইজ অপারেটর দিয়ে –

  • জোড়-বিজোড় নির্ণয়
  • কোনো সংখ্যা 2n কিনা চেক করা
  • কোনো সংখ্যা 2n – 1 কিনা চেক করা
  • কোনো সংখ্যাকে 2n দিয়ে গুণ কিংবা ভাগ করা
  • কোনো সংখ্যাকে 2n দিয়ে ভাগ করলে যে ভাগশেষ থাকে তা বের করা
  • কোনো সংখ্যা 2n দিয়ে বিভাজ্য কিনা দেখা
  • দু’টি ভ্যারিয়েবলের মান swap করা

জোড়-বিজোড় নির্ণয়

1 = 0000 0001

2 = 0000 0010

3 = 0000 0011

4 = 0000 0100

আমরা দেখতে পাচ্ছি, জোড় সংখ্যা হলে লিস্ট সিগনিফিক্যান্ট বীটটা সবসময় 0 থাকে। এখন আমরা যদি কোনো সংখ্যাকে 1 দিয়ে AND করে দি, তাহলে 1 আসবে যদি শেষ বীটটা 1 থাকে, না হলে আসবে 0!

যেমন,

15 = 0000 1111

    & 0000 0001

___________

        0000 0001

আবার,

42 = 0010 1010

    & 0000 0001

___________

       0000 0000

অর্থাৎ আমরা দেখতে পাচ্ছি জোড় হলে 1 দিয়ে AND করলে ফলাফল আসছে 0, আর বিজোড় হলে 1 দিয়ে AND করার ফলাফল আসছে 1। তাহলে আমরা কোডটা লিখে ফেলি জোড়-বিজোড় নির্ণয়ের!

#include <stdio.h>

int ifEven(int n) {
    if (n&1) return 0;
    else return 1;
}

int main() {
    int num;
    scanf("%d", &num);
    if (ifEven(num)) printf("Even\n");
    else printf("Odd\n");
    return 0;
}

কোনো সংখ্যা 2n কি না চেক করা

2 = 21 = 0000 0010

2 – 1 =     0000 0001 (তাহলে আমরা 2 আর (2-1) কে AND করলে পাব 0)

4 = 22 = 0000 1000

4 – 1 =     0000 0111 (তাহলে আমরা 4 এবং (4-1) কে AND করলে পাব 0)

8 = 23 = 0010 0000

8 – 1 =     0001 1111 (তাহলে আমরা 8 এবং (8-1) কে AND করলে পাব 0)

আমরা দেখতে পাচ্ছি, 2-এর যেসব পাওয়ার x আছে, প্রতি ক্ষেত্রেই x এবং (x-1) কে AND করলে 0 আসছে। তাহলে আমরা আমাদের ফাংশনটি লিখে ফেলি!

int ifPower(int n) {
    if (n&(n-1)) return 0;
    else return 1;
}

কোনো সংখ্যা 2n – 1 কিনা চেক করা

আমরা এবার উল্টোভাবে চিন্তা করি। 2n -এর সাথে 2n – 1 এর AND করে আমরা পেয়েছিলাম 0। এখন আমাদেরকে যদি ইনপুট হিসেবে 2n – 1 (=x) দেওয়া হয়, তাহলে আমরা তাকে কীসের সাথে AND করবো? অবশ্যই 2n (= x  + 1)- এর সাথে, এবং আমরা ফলাফল পাব 0। আগেরটা বুঝলে এটাও বুঝার কথা। তাই উদাহারণ না দিয়ে সরাসরি কোড লিখে দিচ্ছি।

int ifPowerMinusOne(int n) {
    if (n&(n+1)) return 0;
    else return 1;
}

কোনো সংখ্যাকে 2n দিয়ে গুণ-ভাগ করা

ধরা যাক, আমার কাছে একটি সংখ্যা আছে 2। এর বাইনারি রিপ্রেজেন্টেশন হল 0000 0010।

এখন আমরা একে একবার লেফট শিফট করলে পাব 0000 0100, অর্থাৎ 4।

দুইবার লেফট শিফট করলে পাব 0000 1000, অর্থাৎ 8।

তিনবার লেফট শিফট করলে পাব, 0001 0000, অর্থাৎ 16।

খেয়াল কর, একবার লেফট শিফট করে আমরা পেয়েছি 4 = 2 * 21। দুইবার লেফট শিফট করে পেয়েছি 8 = 2 * 22। তিনবার লেফট শিফট করে পেয়েছি 16 = 2 * 23। অর্থাৎ n বার লেফট শিফট করার অর্থ হচ্ছে 2n দিয়ে গুণ করা!

একইভাবে অন্য একটি সংখ্যা দিয়েও আমরা চেক করে দেখতে পারিঃ

#include <stdio.h>
int main() {
    int x = 7;
    printf("7 * 2^1 = %d\n", 7<<1); // 1 bar left shift korlam, ashar kotha 14
    printf("7 * 2^2 = %d\n", 7<<2); // 2 bar korlam, ashar kotha 28
    printf("7 * 2^3 = %d\n", 7<<3); // 3 bar korlam, ashar kotha 56
    return 0;
}

কোডটা রান করে দেখ, 14 28 56-ই আসছে!

একইভাবে আমরা যদি একটা সংখ্যাকে right shift করি, তাহলে দেখতে পাব গুণের বদলে ভাগ হয়ে যাচ্ছে! :p

যেমন 16 কে একবার রাইট শিফট করলে আমরা পেতাম 8। 8 কে রাইট শিফট করলে পেতাম 4!

#include <stdio.h>
int main() {
    int x = 7;
    printf("100/2^1 = %d\n", 100>>1); // 1 bar left shift korlam, ashar kotha 50
    printf("100/2^2 = %d\n", 100>>2); // 2 bar korlam, ashar kotha 25
    printf("100/2^3 = %d\n", 100>>3); // 3 bar korlam, ashar kotha 12
    return 0;
}

2n দিয়ে ভাগ করে ভাগশেষ

আমরা 42 কে 2n দিয়ে ভাগ করলে কী ভাগশেষ থাকে তা খুব সহজেই % অপারেটর ব্যবহার করে বের করতে পারি। কিন্তু সেটা যথেষ্ট সময়সাপেক্ষ। তাই আমরা এক্ষেত্রেও বিটওয়াইজ অপারেটর ব্যবহার করে সমাধানের চেষ্টা করি।

আমরা 42 কে 23 দিয়ে ভাগ করলে ভাগশেষ কত থাকে, সেটা বের করবো। এজন্য আমরা 42 কে AND করে দিব 23 – 1 দিয়ে। (উত্তর আসার কথা 2)

42 = 0010 1010

8-1 =  7 =  0000 0111


&     0000 0010 (=2)

হয়ে গেল! অর্থাৎ আমরা কোনো সংখ্যা x%y যদি বের করতে যায়, আমরা ফাংশন থেকে রিটার্ন করে দিব x%(y-1)। শর্ত হল y অবশ্যই 2n হতে হবে। তাহলে আমরা ফাংশনটি লিখে ফেলি!

#include <stdio.h>
int mod(int x, int y) {
    return x & (y-1);
}
int main() {
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%d %% %d = %d\n", x, y, mod(x,y));main();
    return 0;
}

আবারও বলছি y অবশ্যই 2n হতে হবে।

কোনো সংখ্যা 2n দিয়ে বিভাজ্য কি না

কাজটা খুবই সোজা। ভাগশেষ বের করার জন্য যে ফাংশনটা লিখলাম সেটা 0 রিটার্ন করলেই বিভাজ্য!

দু’টি ভ্যারিয়েবল swap করা

আমরা সাধারণত দু’টি ভ্যারিয়েবল swap করি তৃতীয় একটি ভ্যারিয়েবলের সাহায্যে। যেমনঃ

#include <stdio.h>
int main() {
    int x =  7, y = 8;
    printf("Before swapping: x = %d y = %d\n", x,y);
    int temp = x;
    x = y;
    y = temp;
    printf("After swapping: x = %d y = %d\n", x,y);
    return 0;
}

আমরা এ কাজটি বিটওয়াইজ অপারেটর ব্যবহার করে তৃতীয় ভ্যারিয়েবলের সাহায্য ছাড়াও করতে পারি।

এজন্য আমাদের যা করতে হবেঃ

x = x ^ y;
y = x ^ y;
x = x ^ y;
আমরা একটি উদাহারণের সাহায্যে এটি বুঝার চেষ্টা করি।
ধরা যাক, x = 7 = 0000 0111 এবং
               y = 8 = 0000 1000
তাহলে,  x = x^y= 0000 1111
            y = x^y = 0000 0111
            x = x^y = 0000 1000
খেয়াল কর, কাজ শেষে, x = 0000 1000 = 8
আর, y = 0000 0111 = 7
অর্থাৎ হয়ে গেল আমাদের swap করার কাজ!
#include <stdio.h>
int main() {
    int x =  7, y = 8;
    printf("Before swapping: x = %d y = %d\n", x,y);
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
    printf("After swapping: x = %d y = %d\n", x,y);
    return 0;
}
Muntasir Wahed

Muntasir Wahed

System Administrator at স্বশিক্ষা.com
Jack of all trades, master of none.
Muntasir Wahed
Muntasir Wahed