Skip to content

Instantly share code, notes, and snippets.

@syedsouban
Last active March 14, 2022 22:19
Show Gist options
  • Save syedsouban/3f5d500a132916d0d1c6d85eda50e29a to your computer and use it in GitHub Desktop.
Save syedsouban/3f5d500a132916d0d1c6d85eda50e29a to your computer and use it in GitHub Desktop.
Using bitmasking to store Subsets efficiently
//this technique provides a way to efficiently store subsets of a set of natural numbers upto N.
//When N should be the number of bits any type can store
//for example a 32-bit integer will be able to store subsets for a set of natural numbers upto N
//Reference: https://www.youtube.com/watch?v=685x-rzOIlY&list=PLb3g_Z8nEv1icFNrtZqByO1CrWVHLlO5g&index=3
//One thing to note is that this piece of code handles the edge cases of trying to add an element which already exists
// or trying to remove an element which does not exist
#include<iostream>
using namespace std;
class Subset {
public:
unsigned int bin;
unsigned int limit;
Subset(unsigned int bin, unsigned int limit) {
this->bin = bin;
this->limit = limit;
}
void add(int element) {
if((1<<element) & this->bin) {
}
else {
this->bin = (1<<element) ^ (this->bin);
}
}
void remove(int element) {
if((1<<element) & this->bin) {
this->bin = (1<<element) ^ (this->bin);
}
}
void display() {
for(int i=1;i<=this->limit;i++) {
if((1<<i) & (this->bin)) {
cout<<i<<" ";
}
}
}
};
int main() {
Subset s = Subset(0, 15);
s.add(1);
s.add(5);
s.add(5);
s.remove(1);
s.add(7);
s.add(11);
s.add(12);
s.remove(11);
s.display();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment