Bitset

মনে কর, তোমাকে একটা অ্যারে a[n] দেয়া আছে যেখানে n<=1e5 এবং a[i]<=1e7।  এরপর তোমাকে q<=1e5 টা কুয়েরী এন্সার করতে হবে। প্রতি কুয়েরী তে একটি সংখ্যা x দিবে। তোমাকে বলতে হবে এই সংখ্যাটি অ্যারে তে আছে কি না? 

এখন এই সমস্যাটির একটি O(n) কমপ্লেক্সিটির সমাধান করতে বলা হলে তুমি কিভাবে করবে? 

	#include<bits/stdc++.h>
	using namespace std;
	bool vis[10000009];
	int main()
	{
	int i,j,k,n,x,q;
	cin>>n;
	for(i=1 ; i<=n ; i++){
	cin>>x;
	vis[x] = 1;
	}
	cin>>q;
	for(i=1 ; i<=q ; i++){
	cin>>x;
	if(vis[x])
	cout<<"Exist\n";
	else
	cout<<"Not exist\n";
	}
	return 0;
	}

view raw bitset-1.cpp hosted with ❤ by GitHub

এখন, প্রব্লেমের সবকিছু ঠিক রেখে যদি a[i]<=1e9 করে দেয়া হয় তাহলে কী হবে? তোমার সলুশ্যনের মেমোরি কমপ্লেক্সিটি অনেক বেশি হয়ে যাবে। কারণ, প্রতিটি সংখ্যার জন্য তুমি ২বাইট = ১৬ বিট করে মেমোরি নিচ্ছো। 

এখন, এরকম একটা বুলিয়ান অ্যারের পরিবর্তে আমরা বিটসেট ব্যাবহার করতে পারি। আসলে বিটসেটও একটি বুলিয়ান অ্যারে ই। কিন্তু সে প্রতিটি পজিশনের জন্য ১৬ বিট ব্যাবহার না করে মাত্র ১ বিট ব্যাবহার করবে!!! 

তার মানে তোমার উপরোক্ত কোড এর মেমোরি কমপ্লেক্সিটি ১৬ গুণ কমানো সম্ভব!!! 

বিটসেট ব্যাবহার করলে কোড টি নিচের কোডের মতোই হবে। 

	#include<bits/stdc++.h>
	using namespace std;
	const int sz = 1e9+7;
	bitset<sz>bset; ///Initially all position is equal to 0
	int main()
	{
	int i,j,k,n,x,q;
	cin>>n;
	for(i=1 ; i<=n ; i++){
	cin>>x;
	bset[x] = 1;
	}
	cin>>q;
	for(i=1 ; i<=q ; i++){
	cin>>x;
	if(bset[x])
	cout<<"Exist\n";
	else
	cout<<"Not exist\n";
	}
	return 0;
	}

view raw bitset-2.cpp hosted with ❤ by GitHub

এই ছিলো বিটসেটের পরিচয় পর্ব। 

এখন দেখবো বিটসেটের কিছু এপ্লিকেশন।

	#include<bits/stdc++.h>
	using namespace std;
	int main()
	{
	const int sz = 10;
	bitset<sz>bset1; ///Initializes with all bits = 0
	bitset<sz>bset2(15); ///Initializes with binary representation of 15
	bitset<sz>bset3(string("11001")); ///Leftmost 5 bits = specified string & other bits = 0
	cout<<"bset1 = "<<bset1<<endl; ///Print: 0000000000
	cout<<"bset2 = "<<bset2<<endl; ///Print: 0000001111
	cout<<"bset3 = "<<bset3<<endl; ///Print: 0000011001
	bset2[9] = 1; ///We can access it like an array
	cout<<"bset2 = "<<bset2<<endl;
	cout<<"9th bit of bset2 = "<<bset2[9]<<endl;
	cout<<"Number of 1 in bset1 = "<<bset1.count()<<endl;
	cout<<"Number of 1 in bset2 = "<<bset2.count()<<endl;
	cout<<"Number of 0 in bset3 = "<<bset3.size()-bset3.count()<<endl;
	if(bset1.any())
	cout<<"bset1 have at least one set bit\n";
	else
	cout<<"bset1 haven't any set bit\n";
	bset2.set(); ///Set all bit of bset2
	cout<<"bset2 = "<<bset2<<endl;
	bset2.set(2 , 0); ///Reset 2nd bit of bset2
	cout<<"bset2 = "<<bset2<<endl;
	bset2.set(2); ///Set 2nd bit of bset2
	cout<<"bset2 = "<<bset2<<endl;
	bset3.flip(); ///Flip all the bits of bset3
	cout<<"bset3 = "<<bset3<<endl;
	bset3.flip(9);
	cout<<"bset3 = "<<bset3<<endl;
	return 0;
	}

view raw bitset-3.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং😊