201. Bitwise AND of Numbers Range - Leetcode

 201. Bitwise AND of Numbers Range - Leetcode, Medium

প্রবলেম টা একবার পড়লেই বোঝা যাবে, দুইটা নাম্বার দেয়া থাকবে A এবং B।
A থেকে B এর মধ্যে যত গুলা নাম্বার আছে সবার AND(&) করে তাদের রেজাল্ট রিটার্ন করতে হবে।
ধরি A = 2, B  = 10
সুতরাং Ans = 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 = 0

আমরা চাইলেই কিন্তু এইভাবে A থেকে B পর্যন্ত লুপ চালিয়ে এন্সার বের করতে পারি, কিন্তু এক্ষেত্রে সম্ভব না, কারন আমাদের রেঞ্জ হইতে 2*10^9 পর্যন্ত। যেটা অনেক বড় একটা সংখ্যা।


এখন আসি কিভাবে আমরা এই প্রবলেম টা খুব সহজে বিট ম্যানিপুলেশন দিয়ে করে ফেলতে পারি।

পাশের ছবিটার দিকে তাকাই, ১-২০ পর্যন্ত সব গুলা সংখ্যার বাইনারি রিপ্রেজেন্টেশন দেয়া আছে। আপাতত ধরি আমাদের রেঞ্জ [১২,১৫], এদের বাইনারি - 
12 = 1100
13 = 1101
14 = 1110
15 = 1111
আমরা বাইনারি AND(&) এর ক্ষেত্রে জানি, যদি দুইটা বিট ই 1 হয়, তাহলে তাদের AND(&) হবে 1, অন্যসব ক্ষেত্রে 0. এখন ১২ থেকে ১৫ পর্যন্ত আমরা যদি সব গুলা বিট এক এক করে AND(&) করতে থাকি ডান দিক থেকে তাহলে প্রথম পজিশনের রেজাল্ট হবে 0, তারপর 0, তারপর বাকি দুইটা হবে 1.



আরো সুন্দর মত দেখি,
12 = 1100
13 = 1101
14 = 1110
15 = 1111
------------
(&)= 1100

যদি কোনোভাবে যেকোনো কলামে আমরা দুইটা আলাদা বিট ই (০ এবং ১) পাই তাহলে বাকি সব গুলা কলামের রেজাল্ট হবে শুন্য(০),
কারন ০&১ = ০.

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

১১ থেকে ১৫ এর বাম দিকে দুইটা করে দিট বাদ দিলে বাকি দুইটা করে বিট গুলা সবই সেইম, তাইনা ? তাহলে কিন্তু আমাদেরকে আর একটা রেঞ্জের সব গুলা নাম্বার নিয়ে কাজ করা লাগবে না, শুধুমাত্র প্রথম এবং শেষ নাম্বার নিয়ে কাজ করলেই হচ্ছে।

তাহলে, আমরা একটা লুপ চালাবো যতক্ষন না প্রথম এবং শেষ[A and B] সেইম না হয়, এবং একই সাথে তাদের ডান দিক থেকে বিট বাদ দিতে থাকবো। বাদ দেয়া বিট গুলা AND(&) করলে আমরা শুন্য পাবো, কারন তারা সবাই ভিন্ন ভিন্ন বিট।

বাদ দেয়ার কাজ টা আমরা Right Shift দিয়ে করতে পারি । কোড দেখলে খুব সহজেই বোঝা যাবে।

এখানে লাস্টে আবার কেনো diff_bit দিয়ে Left_shift করলাম ? কারন আমাদেরকে ভিন্ন বিট গুলার জন্য যে কইটা ভিন্ন বিট পাইলাম, সে কইটা শুন্য এড করা লাগবে।

Some Basic Bit Manipulation Problems with hints

 461. Hamming Distance  (Try to figure out XOR and set bit Count)
136. Single Number (Two same numbers XOR is 0, means a^a = 0)
268. Missing Number (Same as before, a^b^b = a. It can be also solved by using binary search, Think)
191. Number of 1 Bits (Count number of set bit(1))
231. Power of Two (Think using bit manipulation and without bit manipulation, solve using both cases)
342. Power of Four (Same as before, think about both cases)
78. Subsets (Each subset can be represented as a single bit)
1720. Decode XORed Array (Read the problem statement carefully)
1486. XOR Operation in an Array (Read the problem statement carefully)
1863. Sum of All Subset XOR Totals (Simple backtracking)
371. Sum of Two Integers (Think about carry of two values and sum with recursively)

Some advance operations of Bit Manipulation

/*

 *Given a sequence of numbers, every number is appeared twice,

 *only one number is present one time, find this unique number

 */

int unique_number(std::vector<int>&v){

int n = v.size();

int ans = 0;

for(int i = 0; i<n; i++){

ans^=v[i];

}

return ans;

}

/*

 *given a number , return its 2's complement [ if n = 5, return -5 in binary form]

 *

 * let, x = 5;

 * 5 = 00000101(binary)

 *

 *    11111010(flip all bits)

 *    +1(add 1)

 *----------------------

 *    11111011 (binary representation of -5)

 *

 */

// swap two number using XOR

void swap(int a, int b){

cout <<"Before swaping "<<a<<' '<<b<<endl;

a = a^b;

b = b^a;

cout << "after swaping ";

cout << (a^b) << ' '<<b << endl;

}

/*count number of set bit(1) in binary form of a number

 *__builtin_popcount = int

 *__builtin_popcountl = long int

 *__builtin_popcountll = long long

*/

//Counts the leading number of zeros of the integer(long/long long).

/*

Ex- int x=16;       // 00000000 00000000 00000000 00010000 (32 bits)

      cout<<__builtin_clz(x)<<endl;   //returns 27.

 */

ll LZ(ll x){

return __builtin_clz(x);

}

int CountSet(int n){

//return __builtin_popcount(n);

int ans = 0;

while(n>0){

ans+=(n&1);

n>>=1;

}

return ans;

}

/* Count different set bit

 *given two numbers, count its different bit in every position of their binary form

 * let, a = 11, b = 15

 * a=1011

 * b=1111

 * here differnt position is 1, so count is 1

 */

 int different_bit(int a, int b){

  int c = a^b;

  return __builtin_popcount(c);

 }

 /*Remove Last SetBit of a number 

  *Suppose, given a number 13 = 1101, after removing last bit,

  *it will be , => 1100

  */

int Remove_lastBit(int n){

int ans = n&(n-1);

return ans;

}

/*Check ith bit is set or not

 *Given a number, check the ith bit is 1 or not.

 * means ith position of binary representation is 1 or 0

 * 13 = 1101(3rd,2nd,1st,0th position)

 */

bool ithBit_SetOrNot(int N, int i){

if( N & (1 << i) )

        return true;

    else

        return false;

}

/*change ith bit of a number

 *let n = 13 = 1101

 * = 0010(mask of 1th bit (1<<1))

 *-------------------------------------

 * (xor)=1111 (result , after change 1st bit)

 */

 int changeithBit(int n, int i){

  return (n^(1<<i));

 }

 /* Given a number , check it is power of 2 or not

  * let n = 8, it is a power of two number, 

  * we can write, 8 = 2^3

  */

 bool PowerOfTwo(int n){

  return (n && !(n&(n-1)));

 }

/*n &-n returns the rightmost 1 bit in n.

 *(10000100) = 100

 *(10010) = 10

 *(1000) = 1000

 */

int rightmost(int n){

return n&-n;

}

 

Introduction to Bit Manipulation

আমরা নাম্বার সিস্টেস সম্পর্কে জানি, কোনো একটা নাম্বার কে আমরা চাইলে নির্দিষ্টএকটা বেইজে উপস্থাপন করতে পারি, এটা কিভাবে ? আর বেইজ টা'ই বা কি জিনিস?

আমরা হাটে বাজারে হিসাব নিকাশে যে অংক গুলা করে থাকি এইগুলা হচ্ছে ১০(দশ/টেন) বেইজ নাম্বার, কেনো ?
কারন এখানে ০-৯(শূন্য থেকে ৯) এর মধ্যে সংখ্যা গুলা নিয়েই কেবল আমরা কাজ করি।

সংখ্যা পদ্ধতিতে এমন কতকগুলা বেইজ নিয়ে আলোচনা করা আছে ।
যেমন আছে বাইনারি সংখ্যা, এর বেইজ ২(দুই), অর্থ্যাত এই পদ্ধতিতে শুধুমাত্র ০ এবং ১ নিয়ে কাজ করা হইছে। আবার আছে হেক্সা, অক্টা ইত্যাদি।

এই বিট ম্যানিপুলেশনে আমাদের প্রধান ফোকাস হচ্ছে বাইনারি এবং ডেসিমেল নাম্বার নিয়ে কাজ করা।

একটা ডেসিমেল(১০ বেইজ) নাম্বার কে বাইনারি(২ বেইজ) নাম্বারে কনভার্ট করা খুবই সোজ আবার এর উল্টাটা করাও অনেক সোজা, একটা ছোটো উদাহরন দিয়ে বুঝে ফেলি।

৫ একটা ডেসিমেল নাম্বার, এটাকে যদি আমরা ২ দিয়ে ভাগ করতে থাকি, এবং পরিশেষে তার রেজাল্ট গুলা উলটা দিক থেকে নিই, থাহলে সেটা হয়ে যাবে বাইনারি রিপ্রেজেন্টেশন।

এখানে কিভাবে ডেসিমেল থেকে বাইনারি, আর বাইনারি থেকে ডেসিমেল কনভার্ট করা যায় সেটা দেখানো হইছে, এটা আসলে খুবই সহজ জিনিস, না পারলে কয়েকটা প্র্যাক্টিস করলেই পারা যাবে।

ডেসিমেল থেকে বাইনারি তে নিতে হইলে বারবার ২ দিয়ে ভাগ করতে হবে, ভাগফল শূন্য(০) না হওয়া পর্যন্ত ভাগ করতে থাকতে হবে, পরিশেষে ভাগশেষ গুলা শেষ থেকে কালেক্ট করতে হবে।
 

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


এখন আসি কিভাবে আমরা বাইনারি ডিজিট নিয়ে কাজ করতে পারি, কেনো দরকার কিংবা কি ধরনের ওপারেশন এখানে করা যেতে পারে । বাইনারি নাম্বার সিস্টেমে প্রত্যেকটা নাম্বার কে বিট বলা হয়ে থাকে।

সাধারণ ৬(ছয়) ধরনের বিটওয়াইজ ওপারেটরস বেশি ব্যবহার করা হয়ে থাকে, একে একে সবগুলার সাথে আমরা পরিচয় হবো।

AND(&)
যদি দুইটা বাইনারি নাম্বার কে আমরা AND(&) ওপেরেশন করি তাহলে যদি দুইটা বিট ই 1 হয় তাহলে রেজাল্ট 1 হবে নতুবা 0 হবে। উদাহরন সহ দেখি,
           101010
           110011
           --------
(AND) 100010

OR(||)
এক্ষেত্রে যেকোনো একটা বিট 1 হইলেই রেজাল্ট 1 হবে, নতুবা 0 হবে।
           101010
           110011
           --------
  (OR)  111010
 

XOR(^)
এক্ষেত্রে যেকোনো দুইটা বিট 1 হইলে রেজাল্ট শুন্য হবে, অর্থ্যাত দুইটা বিট সেইম হইলে রেজাল্ট (0)শুন্য নতুবা রেজাল্ট হবে 1
           101010
           110011
           --------
(XOR)  011001

NOT(~)
এক্ষেত্রে ইনপুট জিরো(0) দিলে আউটপুট আসবে ওয়ান(1) এবং  ওয়ান(1) দিলে জিরো(0) আসবে অর্থ্যাত বিট পরিবর্তন হয়ে বিপরিত বিট আসবে।
~0 = 1
~1 =  0
~10101 = 01010

Right Shift(>>)
দুইটা খুবই ইন্টারেস্টিং বিটওয়াইজ ওপেরেটরের একটা এটি, আরেকটা নিয়ে এর পরে আলাপ হইছে।
কিভাবে লেখা হয় ?
N >> a, অর্থাৎ N একটা ডেসিমেল নাম্বার এবং এর বাইনারি রিপ্রেজেন্টেশনের ডান দিক থেকে 'a' টা বিট মুছে ফেলা হয়েছে একইসাথে বাম দিকে 'a' টা 0(zero) বিট এড করে দেয়া হয়েছে।

উদাহরন সহ দেখি,

এখানে N এর মান ২২আমরা একে ২ বার রাইট সিফট করেছি, এতে ২২ এর ডান দিকের দুইটা বিট মুছে গেছে ।
অর্থাৎ ২২>>২ = ৫

এইটা আরো একভাবে চিন্তা করা যায়,
22 >> 2 = 22/2^2 = 22/4 = 5
অর্থাৎ N কে a দ্বারা Right Shift করা মানে N কে 2^a দ্বারা ভাগ করা।

Left Shift(<<)

N << a, অর্থাৎ এক্ষেত্রে বাম দিক থেকে a টা বিট মুছে যাবে , আর ডান দিক থেকে a টা (শুন্য 0) বিট যুক্ত হবে।

আগের টার মত এটাকেও চিন্তা করা যায়।
N << a মানে হচ্ছে N কে 2^a দ্বারা গূণ করা।

3 << 2 = 3*2^2 = 12