ভুল করে বারবার বলি O’shit
একগাদা দ্বন্দ্ব মাথায় লাগায় গিট,
চারদিকের সরষে ফুলে চোখ পিটপিট
গুরু তুমি বেশ কাজের, তুমিই বিট ।
প্রোগ্রামিং করতে গিয়ে আমরা সব সময়ই নিত্য নতুন কিছু জিনিস দেখতে পাই । মূল কথা হল, জিনিসটা পুরোনো কিন্তু আমরা জানিনা বলে আমাদের কাছে নতুন মনে হয় । এরকম ই একদিন
Codeforces এ একজনের Code দেখছিলাম ।
Code এ দেখলাম
1 <<
x ;
number |= 1
<< x ;
আগডুম বাগডুম ......
এই টাইপের হাবিজাবি আরও কি যেন লিখা আছে । দেখেই প্রথম যে ব্যাপারটি অনুভব করলাম তা হল মাথার উপর কেউ একটা হাড়িভর্তি কোড বসিয়ে দিয়েছে এবং সেই কোডের প্রতিটি Statement ১০০ ডিগ্রি সেলসিয়াস (ধরে নিয়েছি) তাপমাত্রায় ফুটছে আর বাষ্প হয়ে উড়ে যাচ্ছে......
আরও বেশ কিছু Code দেখে মনে হল আমি বাংলা সাহিত্যের কোন রচনা পাঠ করছি । তবে প্রথমজনের Code টি আমার বেশ গোছানো লাগছিলো অর্থাৎ এক কথায় প্রকাশের মত । তাহলে উনি কি এমন করেছেন যে ওনার Code এর আকার ছোট ও গোছানো লাগছে । পরে উপলদ্ধি করলাম কোডের স্ফুটনাংকের যদি এমন ব্যবস্থা করি যে, তাপমাত্রা যেমনই হোক সেগুলো বাষ্প হয়ে উড়ে যাবেনা তাহলেইতো সমস্যার সমাধান । হাড়িভর্তি কোডের স্ফুটনাংকের একটা গতি করতে GOOGLE এর উপর শুরু করলাম অত্যাচারের এক ভয়াবহ মিশন “খোঁজ, দ্যা সার্চ”.........
মিশনের আদ্যোপান্ত :
বিটের ব্যবহার ডাটা সংকোচনে যেমন গুরুত্বপূর্ণ ভূমিকা রাখে সেই সাথে এটির ব্যবহার Time
Complexity অনেক কমিয়ে দেয় এবং এতে প্রোগ্রামের আকার ও অনেক ছোট হয়ে যায় । বাইনারি সংখ্যার কথা আমরা সবাই জানি । বিট Manipulation আসলে এই বাইনারি সংখ্যা নিয়ে কাজ করে । আগে আমরা দুটি সংখ্যার বাইনারি Representation দেখি ।
1) 14
=(1110)2
= 1*23+1*22+1*21+0*20
= 14
2) 20
=(10100)2
= 1*24+0*23+1*22+0*21+0*20
= 20
উপরের উদাহরণে 14 এর বাইনারি Representation এ (1,1,0,1) এগুলোর প্রত্যেকটি একেকটি বিট ।
এখন আমরা বিট Manipulation এ যে Operator গুলো সচরাচর ব্যবহৃত হয়ে থাকে যাদের Bitwise Operator নামে ডাকা হয় তাদের সাথে একটু কুশল বিনিময় করে আসি । এই Operator গুলোর কোনোটা Unary আবার কোনোটা Binary । অর্থাৎ Unary Operator গুলোতে একটা সংখ্যার বাইনারি নিয়ে Operation চালানো হয় কিন্তু Binary Operator দের Operation চালানোর জন্য দুইটা সংখ্যার বাইনারি লাগে ।
Bitwise Operators :
AND ( & ) : এটি একটি Binary
Operator । Same position এর দুটি বিট 1 হলেই কেবল result বিটটি 1 হয় নতুবা 0 হয় ।
যেমন : 5 এর বাইনারি =
(1 0 1)2
3 এর বাইনারি = (1 0 1)2
(5 & 3
) = (101)2 & (011)2 = (0 0 1)2 =
1
OR ( | ) :
এটি একটি Binary
Operator । Same position এর দুটি বিট 0 হলেই কেবল result বিটটি 0 হয় নতুবা 1 হয় ।
যেমন : 5 এর বাইনারি =
(1 0 1)2
1 এর বাইনারি = (0 0 1)2
(5 |3 ) =
(101)2 | (011)2 = (1 0 1)2
= 5
XOR ( ^ ) : এটিও একটি Binary
Operator । Same position এর দুটি বিট 0 অথবা 1 হলেই কেবল result বিটটি 0 হয় নতুবা 1 হয় ।
যেমন : 11 এর বাইনারি
= (1 0 1 1)2
8 এর বাইনারি
= (1 0 0 0)2
(11 ^8 ) =
(1 0 1 1)2 ^ (1 0 0 0)2 = (0 0 1 1)2 =
3
NOT ( ~ ) : এটি একটি Unary Operator । (~ 5) এর মানে হল 5 এর বাইনারি Representation এর 1’s
complement । অর্থাৎ এই Operator টি 5 এর বাইনারির position’তম বিটটি 0 হলে তাকে 1 এবং 1 হলে 0 করে দেয় ।
5 এর বাইনারি
= (1 0 1)2
~ 5 = (1 0 1)2 -->2
 |
| AND,OR,XOR,NOT Operation |
Left Shift (<<) : এটি একটি Unary
Operator । একে লিখা হয় (number<<
position) এভাবে । এই Operator টি বাম পাশের নাম্বার এর বাইনারি বিট গুলো position সংখ্যক ঘর বামে shift করে দেয় ।
1<<1 =
2
1 এর বাইনারি হল 1 , এখন তাকে এক ঘর বামে সরতে বলা হয়েছে । তাই বিটটি বামে এক ঘর সরে আসে এবং যেই ঘর থেকে সে আসে সেই ঘরে একটি শূন্য বসিয়ে দেয় । তাহলে এক ঘর সরে আসার পর (10)2 এরকম হয় যেটি 2 এর বাইনারি । তাই 1<<1 = 2 ।
1<<2 =
4
1 এর বাইনারি 1
বিটটি 2 ঘর বামে সরলে (100)2 যা 4 এর বাইনারি ।
এভাবে 3 << 2 = 12
1 <<
4 = 16
আমরা যদি একটু ভালভাবে লক্ষ্য করি তাহলে একটা মজার বিষয় দেখতে পাবো ।
0 এর জন্য বাইনারি বিট লাগে ১ টি (0)2
2 এর জন্য বাইনারি বিট লাগে ২ টি (10)2
3 এর জন্য বাইনারি বিট লাগে ২ টি (11)2
4 এর জন্য বাইনারি বিট লাগে ৩ টি (100)2
এভাবে 7 পর্যন্ত ৩ টি করে বিট লাগে । আবার যখন 8 (eight) এর বাইনারি লিখতে যাই তখন আরও একটি অতিরিক্ত বিট যোগ করতে হয় : (1000)2 ।
অর্থাৎ আমাদের একটি বিট বাড়া মানে হল সংখ্যাটিকে একবার ২ দিয়ে গুণ করা ।
তাহলে 1<<4 এর ক্ষেত্রে
(1 )2
(10)2 2 এর বাইনারি(1*2)
(100)2
4 এর বাইনারি (2*2)
(1000)2
8 এর বাইনারি (4*2)
(10000)2
16 এর বাইনারি (8*2)
Right Shift ( >> ) : এটিও একটি Unary
Operator । একে লিখা হয়
(number>>position)এভাবে । এই Operator টি বাম পাশের নাম্বার এর বাইনারি বিট গুলো position সংখ্যক ঘর ডানে shift করে দেয় ।
4
>> 1 = 2
4 এর বাইনারি (100)2,
এর বিট গুলোকে এক ঘর ডানে সরতে বলা হয়েছে । এক্ষেত্রে এক ঘর ডানে সরা মানে বর্তমান বিটগুলোর সর্বডানের একটি বিট কেটে দেওয়া । তাহলে অবশিষ্ট বিট থাকে (10)2 যেটি 2 এর বাইনারি ।
তাই 4 >> 1 = 2
6 >> 1 = 3
5 >> 1 = 2
16 >> 4 = 1
এখানে যেহেতু প্রতিবার একটি করে বিট কমছে সেহেতু প্রতিবার বামের সংখ্যাটিকে আমরা ২ দিয়ে ভাগ দিচ্ছি । অর্থাৎ 16 >> 4 মানে 16 কে 4 বার দুই দিয়ে ভাগ দিচ্ছি (Left Shift এর ঠিক উল্টোটা)
 |
| Left Shift এবং Right Shift Operation |
বিট এর এই ব্যাপার গুলো অনুভব করে বেশ আনন্দ পেয়েছি তাই বিষয়টি সবার সাথে share করার লোভ সামলাতে পারলাম না । বিশেষ করে কিছু সমস্যা বিট দিয়ে সমাধানের বিষয় রিতিমত আমাকে মুগ্ধ করেছে । পরের পর্বে মজার কিছু সমস্যা বিটের মাধ্যমে সমাধানের চেষ্টা করবো ইনশাল্লাহ ।
0 comments: (+add yours?)
Post a Comment