Bit Manipulation Tutorial

Revision en2, by __LOOSER__, 2022-07-27 20:39:08

Hello ,

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

LeetCode Poor Pig

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.

Solution using Binary number knowledge

Trick 1

We can Hash any string to bit mask .

Lets start with simple example :-

Count number of different char in string

Using set
Using BitMask

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

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

Soution Using BitMask

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

Answer

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.

Lets see some Question:-

Leetcode Number of Valid Words for Each Puzzle

My Solution of above Question

Some Questions To Practice :

CodeChef Chef and Deque

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)