বিট-ওয়াইজ নিয়ে খেলা! (Playing with Bitwise!)

Aug 5, 2013

আগের পর্বঃ বিট-ওয়াইজ অপারেটর

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

এই লেখায় যে বিট প্যাটার্নগুলো দেখানো হবে সবক্ষেত্রে সবার ডানের বিটটি হল Least Significant Bit (LSB), অর্থাৎ ডান দিকের বিট থেকে নাম্বারিং শুরু হবে। 1 হবে 0000 0001, 2 হবে 0000 0010, 3 হবে 0000 0011 এরকম। আর বেশিরভাগ ক্ষেত্রেই আমরা unsigned ডাটা টাইপ নিয়ে কাজ করব। কারণ signed টাইপের ডাটার মধ্যে সবার বামের বিটটিতে (যদি ডানের বিট LSB হয়) চিহ্ন নির্দেশ করার জন্য একটি বিট বরাদ্দ থাকে।

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

কোন একটি সংখ্যা জোড় নাকি বিজোড় সেটি নির্ণয় করার জন্য আমরা সাধারণত তাকে 2 দিয়ে mod করি, বা 2 দিয়ে ভাগ করলে ভাগশেষ কত হয় সেটি বের করি। যদি সেটি 0 হয় তাহলে বলি নাম্বারটি জোড়, না হলে বিজোড়। কিন্তু কম্পিউটারের জন্য এই কাজটি বেশ সময়সাপেক্ষ। আমরা বিট-ওয়াইজ অপারেটরের মাধ্যমে সহজেই অনেক দ্রুত কাজটি করতে পারি।

যেকোন নাম্বার কম্পিউটারে বাইনারিতে থাকে। কোন একটি নাম্বারকে যদি আমরা বাইনারিতে রূপান্তর করি তাহলে লক্ষ করলে দেখা যাবে, নাম্বারটি যদি জোড় হয় তাহলে তার একেবারে ডানের বিটটি 0 হয়। আর যদি বিজোড় হয় তাহলে সেটি 1 হয়। এটি যেকোন নাম্বারের ক্ষেত্রেই প্রযোজ্য। যেমন,

 59 = 0011 1011
 46 = 0010 1110
113 = 0111 0001
 28 = 0001 1100

এখন আমরা যদি একটি নাম্বারকে 1 দিয়ে AND করি তাহলে নাম্বারটির একেবারে ডানের বিটে যদি 1 থাকে তাহলে AND হয়ে 1 আসবে, আর যদি ডানের বিটে 0 থাকে তাহলে AND হয়ে 0 আসবে। এখান থেকে আমরা সহজেই বলে দিতে পারি নাম্বারটি জোড় নাকি বিজোড়।

59 = 0011 1011           46 = 0010 1110
 1 = 0000 0001            1 = 0000 0001
 & -----------            & -----------
   = 0000 0001              = 0000 0000

কোড লিখলে হবে এরকমঃ

int x;
scanf( "%d", &x );
if( x & 1 ) puts( "Odd." );
else puts( "Even." );

2^n দ্বারা গুণ/ভাগ

কোন একটা নাম্বারকে যদি আমরা 2^n দিয়ে গুণ বা ভাগ করতে চাই তাহলে সহজ উপায় হল সরাসরি গুণ বা ভাগ করে দেওয়া। কিন্তু এখন আমাদের উদ্দেশ্যই হল কাজটি দ্রুত এবং এফিসিয়েন্টভাবে করা। গুণ-ভাগ অত্যন্ত সময় সাপেক্ষ প্রক্রিয়া। তাই আমরা বিট-ওয়াইজ অপারেটর ব্যবহার করে এটি করব।

ধরা যাক আমাদের কাছে একটা নাম্বার  x আছে। এখন যদি এই নাম্বারটিকে 2^n দিয়ে গুণ করতে বলা হয়, অথবা 2 দিয়ে n সংখ্যকবার গুণ করতে বলা হয় তাহলে আমরা যেটা করতাম তা হল, 2^n দেওয়া থাকলে সরাসরি গুণ করতাম, আর যদি n দেওয়া থাকে তাহলে একটা লুপ চালিয়ে n সংখ্যকবার 2 দিয়ে গুণ করতাম। একইভাবে ভাগের কাজটিও করতাম। কিন্তু এই একই কাজ করা যায় LEFT SHIFT এবং RIGHT SHIFT অপারেটরের মাধ্যমে।

আমরা যদি 2^n দিয়ে x কে গুণ করতে চাই তাহলে লিখব, x « n আর যদি ভাগ করতে চাই তাহলে x » n । এতোটাই সহজ! ধরা যাক x = 5 এবং 2^n = 8 বা n = 3 । তাহলে,

x  = 5 = 0000 0101
x << 3 = 0010 1000 = 40 = 5 * 8 = 5 * 2^3

আবার ধরা যাক, x = 96 এবং 2^n = 8 বা n = 3 । তাহলে,

x = 96 = 0110 0000
x >> 3 = 0000 1100 = 12 = 96 / 8 = 96 / 2^3

2^n কিনা?

একটি নাম্বার কি 2 এর পাওয়ার কিনা সেটি যদি বের করতে হয় তাহলে আমরা কিভাবে করব? সহজ উপায় হল একটা লুপ চালানো। 2 দিয়ে বারবার ভাগ করতে থাকব। যদি কখনও ভাগশেষ 0 বাদে অন্যকিছু আসে তার মানে সেটি 2 এর পাওয়ার না। অন্যথায় যদি ভাগ করতে করতে আমরা একসময় 2 পাই তাহলে বুঝব নাম্বারটি 2 এর পাওয়ার।

আরেকভাবেও করা যায়, আমরা একটি ভেরিয়েবলে 2 নিয়ে লুপ চালাবো এবং বার বার 2 দিয়ে গুণ করতে থাকব। যতক্ষণ পর্যন্ত নাম্বারটি প্রদত্ত নাম্বার থেকে ছোট থাকবে ততক্ষণ পর্যন্ত গুণ করতে থাকব। যদি কোন একসময় প্রদত্ত নাম্বারের সমান হয়ে যায় তাহলেই বুঝব নাম্বারটি 2 পাওয়ার। আর যদি সমান না হয়, প্রদত্ত নাম্বারের চেয়ে বড় হয়ে যায় তাহলে লুপ break করে দিব এবং নাম্বারটি যে 2 এর পাওয়ার না সেটি পেয়ে যাব। এরকম আরও অনেকভাবে করা যায়। তবে বিট-ওয়াইজ অপারেটরের সাহায্যে আমরা কোন লুপ না চালিয়ে একটা স্টেটমেন্ট দিয়েই এটি বের করতে পারি।

যেকোন নাম্বার যদি 2 এর পাওয়ার হয় তাহলে তার বিট প্যাটার্ন হবে, 1 এবং তার ডানে, 2 এর পাওয়ার যত ততগুলো 0। কিছু নাম্বার দেখা যাক,

 4 = 2^2 = 0000 0100
 8 = 2^3 = 0000 1000
16 = 2^4 = 0001 0000
32 = 2^5 = 0010 0000

এই নাম্বারগুলো, অর্থাৎ 2 এর পাওয়ার যেগুলো তাদের থেকে যদি 1 বিয়োগ করি তাহলে যে নাম্বারটি পাওয়া যাবে তার বিট প্যাটার্ন হবে যত পাওয়ারের নাম্বার থেকে 1 বিয়োগ করা হয়েছে, ততগুলো 1। যেমন,

 3 = 2^2 - 1 = 0000 0011
 7 = 2^3 - 1 = 0000 0111
15 = 2^4 - 1 = 0000 1111
31 = 2^5 - 1 = 0001 1111

এই প্যাটার্ন দেখে পরিষ্কার হওয়া উচিত যে আমরা যদি x এর সাথে x-1 এর AND করি, তাহলে x যদি 2 এর কোন পাওয়ার হয় সেক্ষেত্রে আমরা 0 পাব। অন্যথায় 0 ব্যতীত অন্য কোন নাম্বার পাব।

8 = 2^3     = 0000 1000
7 = 2^3 - 1 = 0000 0111
-----------------------
8 & ( 8-1 ) = 0000 0000

10 = 0000 1010
 9 = 0000 1001
& ------------
   = 0000 1000 ( 0 নয় )

অতএব কোড লিখলে দাঁড়াবেঃ

unsigned int x;
scanf( "%u", &x );
if( x & (x-1) ) puts( "Not a power of 2." );
else puts( "Power of 2." );

2^n - 1 কিনা?

আগের অংশটুকু বুঝলে এটি খুবই সহজ। আগেরবার আমরা x এবং x-1 এর মধ্যে AND করেছি। এবার x এবং x+1 এর মধ্যে AND করব। তাহলেই যদি ফলাফল 0 আসে, নাম্বারটি 2^n - 1 টাইপ, অন্যথায় হবে না। কিভাবে হয় তার ব্যাখ্যা উপরের মতই। বাকিটুকু নিজে থেকে চিন্তা করার দায়িত্ব রইল। এবার কোড দেখা যাকঃ

unsigned int x;
scanf( "%u", &x );
if( x & (x+1) ) puts( "Not 2^n - 1 type." );
else puts( "2^n - 1 type." );

2^n দ্বারা বিভাজ্য কিনা?

একটি নাম্বার যদি দেওয়া থাকে তাহলে সেটি কি 2 এর কোন পাওয়ার দ্বারা নিঃশেষে বিভাজ্য কিনা তা আমরা কিভাবে বের করব? সহজ উত্তর হল আবারও সেই mod (%) ব্যবহার করা। কিন্তু আবারও একই কথা, এই অপারেটরটির কাজ অনেক সময়সাপেক্ষ। এই জন্য আমরা বিট-ওয়াইজ অপারেটরের মাধ্যমে কাজটি করব।

কোন একটি নাম্বার x দেওয়া আছে। আরেকটি নাম্বার দেওয়া আছে d যাকে দিয়ে আমরা x কে ভাগ করে দেখবো ভাগশেষ 0 হয় কিনা। এখন d কে যদি আমরা 2^n আকারে লিখতে পারি, অর্থাৎ d যদি 2 এর কোন পাওয়ার হয় তাহলে, x % d = x & ( d - 1 ) হবে। এখানে d কে অবশ্যই 2^n টাইপের একটি নাম্বার হতে হবে, অন্যথায় সমীকরণটি ঠিক হবে না।

নাম্বারগুলোর বিট প্যাটার্ন দিয়ে পরীক্ষা করে দেখা যাক। x = 74, d = 8, x % d = 6 ।

x     = 74 = 1010 1110
d - 1 =  7 = 0000 0111
& --------------------
        6  = 0000 0110

আবার, x = 96, d = 8, x % d = 0 ।

x     = 96 = 0110 0000
d - 1 =  7 = 0000 0111
& --------------------
         0 = 0000 0000

অতএব কোডে আমরা লিখতে পারিঃ

unsigned int x, d = 8;
scanf( "%u", &x );
if( x & ( d - 1 ) ) puts( "x is not divisible by d." )
else puts( "x is divisible by d." );

2^n দ্বারা mod

আগের অংশটুকু থেকেই আসলে এটা বলা হয়ে গেছে। d কে যদি আমরা 2^n আকারে লিখতে পারি, অর্থাৎ d যদি 2 এর কোন পাওয়ার হয় তাহলে, x % d = x & ( d - 1 ) হবে। এখানে d কে অবশ্যই 2^n টাইপের একটি নাম্বার হতে হবে, অন্যথায় সমীকরণটি ঠিক হবে না। আগের অংশের উদাহরণ থেকেই এটা পরিষ্কার।

দুটি ভেরিয়েবলের মান পাল্টাপাল্টি (৩য় ভেরিয়েবল ছাড়া)

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

unsigned int x = 21;
unsigned int y = 13;
// যোগ-বিয়োগের মাধ্যমে
x = x + y; // x = 21 + 13 = 34
y = x - y; // y = 34 - 13 = 21
x = x - y; // x = 34 - 21 = 13
// গুণ-ভাগের মাধ্যমে
x = x * y; // x = 21 * 13 = 651
y = x / y; // y = 351 / 13 = 21
x = x / y; // x = 351 / 21 = 13

কিন্তু আবারও কথা একই, সময় বেশি লাগবে! সময় কমানোর জন্য এখন আমরা একই কাজ বিট-ওয়াইজ অপারেটর XOR এর মাধ্যমে করব।

x = x ^ y;
y = x ^ y;
x = x ^ y;

কিভাবে হল সেটার জন্য বিট প্যাটার্ন দেখা যাক।

x =    21 = 0001 0101
y =    13 = 0000 1101
x = x ^ y = 0001 1000
y = x ^ y = 0001 0101 = 21
x = x ^ y = 0000 1101 = 13

এভাবে বিট-ওয়াইজ অপারেটরসমূহকে নানাভাবে কাজে লাগিয়ে বিভিন্ন গাণিতিক সমস্যার সমাধান করা যায়। যদিও কাজগুলো সাধারণ অপারেটরগুলো দিয়েও করা যায়, বিট-ওয়াইজ অপারেটর ব্যবহারের মূল উদ্দেশ্য হল প্রোগ্রামের গতি বৃদ্ধি করা। অনেকসময় এই সাধারণ কিছু পরিবর্তন প্রোগ্রামিং কনটেস্টে TLE এবং AC এর মধ্যে পার্থক্য সৃষ্টি করে দিতে পারে!