Showing posts with label বিট নিয়ে খেলা. Show all posts
Showing posts with label বিট নিয়ে খেলা. Show all posts

পর্ব - ২ ( সমস্যা - ৩ )

পাবন 2 comments

বিট Manipulation এর প্রথম পর্বটি এখানে ।

একটি সেটের সম্ভাব্য সকল সাবসেট Generate করতে হবে ।

ধরা যাক , {a , b , c} একটি সেট ।

তাহলে এর সম্ভাব্য সাবসেটগুলো হবে ঃ
{ } , {a} , {b} , {c} , {a,b} , {b,c} , {c,a} , {a,b,c} ।

অর্থাৎ সেটটিতে যদি element সংখ্যা N হয় তাহলে সেটটির Total Subset হবে টি 2N টি ।
লুপ চালিয়ে যদিও এটি করা যায় তবুও এক্ষেত্রে বিট Manipulation এর প্রয়োগটি শিখে আমার খুবই ভালো লেগেছে এবং ব্যাপারটি খুবই মজার ।
এখানে যেহেতু element সংখ্যা ৩ টি তাই আমাদের ৩ টি বিট লাগবে প্রতিটি element এর জন্য একটি করে । একটি specific বিট 1 হলে বুঝবো যে , সেই element টি সাবসেট এ আছে । নিচের Table টি লক্ষ্য করলেই ব্যাপারটি বোঝা যাবে । 

সাবসেট নাম্বার
a
b
c
সাবসেট
0
0
0
0
{ }
1
0
0
1
{ c }
2
0
1
0
{ b }
3
0
1
1
{ b , c }
4
1
0
0
{ a }
5
1
0
1
{ a , c }
6
1
1
0
{ a , b }
7
1
1
1
{ a , b , c }

প্রোগ্রামে আমরা 0 থেকে less than (1<<N) পর্যন্ত প্রতিটি Number এর জন্য দেখবো Number টির 0 থেকে N-1 (কারণ আমাদের Total element N টি) তম বিটটি 1 কিনা এবং 0 থেকে N-1 তম প্রতিটি বিট 1 পাওয়া মানেই হল element টি সাবসেট এ আছে । কিভাবে i'তম বিট 1 হয় তা আমরা পূর্বের সমস্যায় দেখেছি । কোন বিট টি কাকে Represent করছে সেটা Table এ আমরা বলে দিয়েছি । এখন আমরা Code Implementation টি দেখবো ।

কোড ইমপ্লিমেন্টেশন ঃ



সমাধানের জন্য মজার একটি সমস্যা ঃ
হ্যাপি কোডিং 

পর্ব - ২ ( সমস্যা - ২ )

পাবন 0 comments

একটি Number এর বাইনারি Representation এর i'তম বিটটি 0 না 1 ?

N & ( 1 << i ) এই Operation এর মাধ্যমেই আমরা আমাদের Answer পেয়ে যাবো ।

এখন প্রশ্ন হল , এই Operation টি কেন কাজ করছে ?

ভালো করে খেয়াল করলেই আমরা এর উত্তর পেয়ে যাবো । আমরা জানি যে , বাইনারি Representation এ ডান থেকে বামে প্রতি বিট ধরে যাওয়া মানেই হল প্রতি ঘরে 2 এর Power 1 করে বাড়া ।

এখন ধরা যাক , N এর মান 10 ( {1010}2 ) । এর 2nd বিটটি আমরা বের করতে চাই ।
এক্ষেত্রে Operation টি হবে N & ( 1 << 2 ) । ( 1 << 2 ) মানে 1 কে 2 ঘর বামে shift করছি । তাহলে ( 1 << 2 ) এর মান হবে {100}2 অর্থাৎ 4 ।
  • তারপর N এর সাথে একে & করলে ঃ  {1010}2 & {0100}2 = 0 ।
যেহেতু Number টির সাথে আমরা 2 এর i'তম Power কে & করছি সেহেতু i'তম বিটটি 1 হলেই কেবল N & ( 1 << 2 ) এর মান 2i হবে অন্যথায় 0 হবে , কারণ ( 1 << i ) এর i'তম বিটটি ছাড়া ডানের সব বিটই 0 ।

এইধরনের আরো দুটি Operation রয়েছে ঃ
  1. একটি Number এর বাইনারি Representation এর i'তম বিটটি On করা অর্থাৎ 1 করা । ( N |= ( 1<< i )) ।
  2. একটি Number এর বাইনারি Representation এর i'তম বিটটি Off করা অর্থাৎ 0 করা । ( N &= ~(1<<i )) ।

কোড ইমপ্লিমেন্টেশন ঃ



পর্ব - ২ (সমস্যা - ১)

পাবন 0 comments

আমরা একটি ইনপুট নিবো , বলতে হবে ইনপুট নাম্বারটিকে 2 এর Power হিসেবে লিখা যায় কি যায় না ।

Naive Solution হতে পারে , নাম্বারটিকে 2 দিয়ে ভাগ করতে থাকবো যতক্ষণ 2 দিয়ে ভাগ যায় । এভাবে ভাগ করতে করতে যদি নাম্বারটিকে 1 বানানো  যায় তাহলে আমরা বলতে পারবো যে নাম্বারটিকে 2 এর Power হিসেবে লিখা যায়।

যেমন ঃ 16 = 24

 16/2 = 8

8/2 = 4

4/2 = 2

2/2 = 1

# Naive Solution



এই প্রোগ্রামের কমপ্লেক্সিটি  O(logN) ।

কিন্তু বিট Manipulation এর মাধ্যমে এটি Constant time অর্থাৎ O(1) কমপ্লেক্সিটিতে বের করা যায় ।
8 এর বাইনারি {1000}2 এবং 8 কে 2 এর Power হিসেবে লিখা যায় ( 23) । 7 এর বাইনারি {111}2 । তাহলে 7 ও 8 এর মধ্যে & Operation করলে {1000}2   & {0111}2 = 0 । অর্থাৎ শুধুমাত্র যেসব নাম্বার কে 2 এর Power হিসেবে লিখা যায় সেসব নাম্বার  এবং তার immediate আগের নাম্বারটির মধ্যে & Operation করলে Result সবসময় 0 - ই হবে কেননা 2 এর Power হিসেবে লিখা যায় এমন নাম্বার  এবং তার immediate আগের নাম্বারটির মধ্যকার সব বাইনারি বিট ভিন্ন বিধায় তাদের মধ্যে & Operation করলে Result 0 - ই হবে ।

# Solution with বিট Manipulation


# Code Analysis

 2 এর Power হিসেবে লিখা যায় এসব নাম্বারের ক্ষেত্রে (n & (n-1)) এর মান 0 , তাহলে !(n & (n-1)) এর মান 1 । এর সাথে n কে logical and (&&) দিয়ে যুক্ত করা হয়েছে , এটি শুধু n শূন্য ব্যতিত সব নাম্বারের ক্ষেত্রে সত্য অর্থাৎ 0 কে 2 এর Power হিসেবে লিখা যায় না দেখেই এভাবে !(n & (n-1)) এর সাথে n কে logical and দিয়ে যুক্ত করা হয়েছে ।

পর্ব - ১

পাবন 0 comments

                 ভুল করে বারবার বলি 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 করার লোভ সামলাতে পারলাম না । বিশেষ করে কিছু সমস্যা বিট দিয়ে সমাধানের বিষয় রিতিমত আমাকে মুগ্ধ করেছে । পরের পর্বে মজার কিছু সমস্যা বিটের মাধ্যমে সমাধানের চেষ্টা করবো ইনশাল্লাহ । 


রেফারেন্স:

Subscribe to: Posts (Atom)