Bit Manipulation Tutorial
Difference between en3 and en4, changed 211 character(s)
Hello , ↵

lets start from a basic question that can be solved using Binary number's Knowledge.↵

[LeetCode Poor Pig](https://leetcode.com/problems/poor-pigs/)
 ||| [Video Solution of Poor Pig](https://youtu.be/4U1ZZYPuXr4)

Basically in above question you are given n number of poison bottle, and t number of trial you can do ,how many minimum pig you need to find the bottle with poison.↵

<spoiler summary="Solution using Binary number knowledge">↵
let say number Bottle is 2 and one trial then how many pig we need ? ↵

1 because we are going to feed first bottle to pig 1 if dies then there there is poison in bottle 1 otherwise there is poison in bottle 2.↵

We can generalize above idea for in binary number.How?↵

Lets name all bottle from 1 to N .↵

if in poison bottle I want to know whether in its binary representation first digit is 0 or 1 to do that I will feed pig 1 all bottle in which first digit is one (like 1,3,5,..) if Pig 1 dies then first digit (in binary representation ) is one otherwise 0.↵

similairy process can be done for other digits ↵

If we have more number of trial than 1 then (lets say 2) we instead of binary number number we can use ternary number.↵

so this way we will get answer as ceil(log(t+1)(n)); log base t+1 (n) ↵
</spoiler>↵

Trick 1↵
==================↵

We can Hash any string to bit mask .↵

Lets start with simple example :- ↵

Count number of different char in string ↵

<spoiler summary="Using set">↵
We can use set or bool array to count character↵

~~~~~↵
int count(string & s) {↵
set<char>st;↵
for (char i : s) {↵
st.insert(i);↵
}↵
return st.size();↵
}↵
~~~~~↵

</spoiler>↵


<spoiler summary="Using BitMask">↵
~~~~~↵
int count(string & s) {↵
int mask = 0;↵
for (char i : s) {↵
mask |= (1 << (i - 'a'));↵
}↵
return __builtin_popcount(mask);↵
}↵
~~~~~↵
</spoiler>↵


We can use this trick to reduce the constant factor of 26 in many different kind of problem.↵

lets take a example↵

[Leetcode Maximum Product of Word Lengths](
httphttps://leetcode.com/problems/maximum-product-of-word-lengths/)↵

[Video Editorial](https://youtu.be/CaqzLFT1A0w)↵

If you will try to solve this question using boolean array the time complexity will be O(n*n*26) that will lead to tle but you can improve time complexty to O(n*n) just by using bitmask↵

<spoiler summary="Soution Using BitMask">↵

~~~~~↵
class Solution {↵
public:↵
    int maxProduct(vector<string>& words) {↵
        vector<int> a(words.size() , 0);↵
        for(int i = 0;i < words.size();i++){↵
            for(int j = 0;j < words[i].size();j++){↵
                a[i] |= 1 << (words[i][j] - 'a');↵
            }↵
        }↵
        int res = 0;↵
        for(int i = 0;i < words.size();i++){↵
            for(int j = i + 1;j < words.size();j++){↵
                if((a[i] & a[j]) == 0){↵
                    if(words[i].size() * words[j].size() > res){↵
                        res = words[i].size() * words[j].size();↵
                    }↵
                }↵
            }↵
        }↵
        return res;↵
    }↵
};↵
~~~~~↵


</spoiler>↵

Trick 2↵
==================↵

Printing all subset of K↵

What do I mean by subset↵

let say we have number whose binary representation is 1011 then we keep 0 as it is and we can make 1 to 0 or can keep 1.↵


Subsets of 1011 are 0011 , 1010 , 1011 and so on . 1100 is not subset because we will keep zero at place of zero.↵


so how many total number of subset will be there for any number↵

<spoiler summary="Answer">↵
2^count(number of set bits)↵
</spoiler>↵

 ↵

Now First question is How to generate all possible subset↵


~~~~~↵
void generate(int k) {↵
int num = k;↵
while (k) {↵
cout << k << " ";↵
k--;↵
k = k & num;↵
}↵
cout << 0 << '\n';↵
}↵
~~~~~↵

There are Many Question you can solve using this trick . SOS dp also uses this trick [Sos Dp](https://codeforces.net/blog/entry/45223).↵

Lets see some Question:-↵


[Leetcode  Number of Valid Words for Each Puzzle](https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/)↵

<spoiler summary="My Solution of above Question">↵

~~~~~↵
class Solution {↵
public:↵
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {↵
        vector<unordered_map<int,int>>mp(26);↵
        for(string & i: words){↵
            int p=0;↵
            for(char j:i){↵
                p |= (1<< (j-'a'));↵
            }↵
            int vis=0;↵
            for(char j:i){↵
                if(!(vis & (1 << (j-'a'))))mp[j-'a'][p]++;↵
                vis |= (1 << (j-'a'));↵
            }↵
        }↵
        vector<int>ans;↵
        for(string &i:puzzles){↵
            int p=0;↵
            for(char j:i){↵
                p |= (1<<(j-'a'));↵
            }↵
            int k=p;↵
            int res=0;↵
            int r=0;↵
            while(k){↵
                r++;↵
                if(mp[i[0]-'a'].count(k))res+=mp[i[0]-'a'][k];↵
                k=(k-1)&p;↵
            }↵
            assert(r==127);↵
            ans.push_back(res);↵
        }↵
        return ans;↵
    }↵
};↵
~~~~~↵


</spoiler>↵

Some Questions To Practice :↵

[CodeChef Chef and Deque](https://www.codechef.com/problems/CHEFDQE)↵


Trick 3↵
==================↵

Reducing Time Complexy By factor of B (Depend on your system) Using bitset↵

Errichto has video on same topic you can watch that↵

[Errichto Video](https://www.youtube.com/watch?v=jqJ5s077OKo)↵

Practice Question↵

[Codechef Functional Array](https://www.codechef.com/problems/FUNARR)↵


Ok now discuss some of Important things related to Bits↵

--> Gray Code , normaly gray codes are used to check error while sending signals from one place to other place . Gray Code has special property that every consecutive number has atmost one digit different.↵

<spoiler summary="Binary Number to gray Code">↵

~~~~~↵
int g (int n) {↵
    return n ^ (n >> 1);↵
}↵

~~~~~↵


</spoiler>↵

<spoiler summary="Gray Code to Binary Number">↵

~~~~~↵
int rev_g (int g) {↵
  int n = 0;↵
  for (; g; g >>= 1)↵
    n ^= g;↵
  return n;↵
}↵
~~~~~↵


</spoiler>↵




--> We can find Minimum XOR of two element in array Just by sorting the array and taking minimum of xor of neighbouring element.↵



--> To find Maximum XOR of two element We can use trie data structre.↵


--> We can use Bit mask to solve problems related to "The Inclusion-Exclusion Principle" [CP Algorithm Turorial](https://cp-algorithms.com/combinatorics/inclusion-exclusion.html)↵

--> Few Equations Related To Bit Manipulation [link](https://codeforces.net/blog/entry/94447)↵

My YouTube Channel :- [YouTube](https://www.youtube.com/channel/UCHCGL-xmIy_Hm7fjfG697Bg)↵
 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English __LOOSER__ 2022-07-28 01:29:26 211 Tiny change: 'gths](httphttps://le' -> 'gths](https://le' (published)
en3 English __LOOSER__ 2022-07-27 23:11:33 1394 Tiny change: 'oiler>\n\n2. We ' -> 'oiler>\n\n\n\n\n2. We '
en2 English __LOOSER__ 2022-07-27 20:39:08 3825 Tiny change: 'stant fact of 26 in ' -> 'stant factor of 26 in '
en1 English __LOOSER__ 2022-07-26 22:06:52 1293 Initial revision (saved to drafts)