Bit Manipulation Crash Course

hi guys good morning welcome back to the new crash course so this going to be a bit manipulation crash course in which we going to cover every concept you going to need for any problem from easy medium medium hard to hard so the contents which you going to cover in this video are okay all these contents you can pause and read if you want and also on top of it for every concept you read or you have studied or you can encounter in bit manipulation or bit masking these are problems easy medium and hard which I will give corresponding video links also in description below for you to practice and notes you can see on COD within.com again right now it is not uploaded but yeah we will have them soon in this website so in the very beginning starting with what actually is bit manipulation simply we not go into very deep because we are actually going into deep step by step but pit manipulation is the act of algorithmically manipulating bits for us basically we are talking about these bits which are nothing but zeros and ones binary numbers are these and we'll just use them or manipulate them the same way your X manipulates you that the same way we will manipulate these bits to get our value done to get our answer so first very basic thing is what are these binary numbers and how these are used in programming so you usually deal with the normal numbers which are 10 15 20 these are called as the decimal numbers so firstly we'll see okay if you want to even use those binary numbers how we will convert them so we have to convert these normal decimal numbers again these numbers which you see in daily life 10 15 30 45 all these are decimal numbers we will convert them into the binary number although we have usually seen in the fifth standard okay and decimal number five we can represent that as a binary number as 1 1 make sure binary numbers are written from right to left so this is the zeroth bit this is the first bit this is the second bit that is one thing you have to make sure forever in this course now we will firstly understand that this decimal number how we will convert it programmatically into this binary number we can easily see that this binary number is 101 five's binary representation is 101 101 so if I ask you pause a minute and if I have given you this binary number and I would have asked you convert it back so this is much easier for the people how because they know that this is the extreme rightmost bit has a contribution of 2^ 0 then the next bit which is the first bit have a contribution of 2^ 1 the next bit have a contribution of 2^ 2 and then the actual contribution will be 1 0 or one which means Zer saying do I take this contribution even in consideration or not one is saying do I take this contribution even in consideration or not so as soon as I multiply something by zero it will ultimately become a zero this will still remain as it which is 2^ 2 this will still remain as it which is 2^ 0 so the answer is 4 + 1 which is 5 so now you know that if any way I would have given you a binary representation of a number you can easily go on from right to left contribute for the zero bit 2^ 0 then the next bit 2^ 1 the next bit 2 power two and so on and so forth and you can just check the contribution and get the value programmatically we will also see later on but this is for you just get familiarize of how these binary numbers we can convert them back to decimal but this is not important because we always start the decimal number now the big question is how we convert this decimal number into the binary number so if you saw above I was actually multiplying by two to get my next value next value next value same way from decimal to Binary I will keep on dividing by two so if I have a number five I will divide by two I'll get a remainder as one and then whatever okay 2 2 are 4 right then okay remainder is one again two I divide then remainder is zero okay one I have got because 2 1's are two then two I divide like one by two I get the divisor as zero but remainder will be one now AR in how to write this write always backwards because you know things in this work from right to left so if things work from right to left and you have got this value which is one so you will have to write this one here which is this is the C this is the B and this is the a so ultimately like for us in human writing we write from right to left but these binary things or binary representations work from right to left we write from left to right but these work from right to left so it's the reason you have to make sure that this is the zeroth bit which you write then the the first bit then the second bit so the first number which you have got is the zeroth bit then the first bit then the second bit that is how you write it but Aran like you represent the AR like is it the array which you have represented um you can say but if I can say then I should also say that the arrays are actually represented from left to right so ideally this should be the zeroth index this should be the first Index this should be the second index yeah that is true that is the reason although I will show show you as in this representation which means I will show you an array in which the indexing I I will show you okay it is a zero index it is the first index but I will always write from right to left but in programming make sure this zero index actually comes in in the LIF it should be one it should be zero it should be one this is a prime portion of your binary numbers that is very confusing for people that oh how it is working right left or left right but we'll make sure in program also and I will Dy also for you that how this will work but just make sure one thing that what they actually are called this one is called as a set bit which means at this location the bit is set okay he set this zero say okay it is unset which means it is not yet set this is are the few terminology which you should be knowing so as to easily understand what the actual web will tell you now we realized we can easily convert our any integer decimal number to a binary number by simply keep on dividing that by two the remainder whatsoever I'm getting I will store that remainder in my actual Vector I can take a vector I can store in a vector and that will be actually my binary representation of a number so let's imagine I have take a binary Vector which will store the binary information of a specific number n and and then I have taken an index why index because I know that as soon as I will place an element at a specific index I I have to move my index I to the next location which is i++ now I have to keep on repeating this step until my this number which was N I gave in it becomes a zero I have to keep on repeating that you can easily see so I have simply written that while my n is more than zero I should keep keep on repeating my step what was the step I was repeating I was simply firstly getting the remainder of a number okay I will get N I will simply divide that number by two because this two is always fixed because I'm converted to a binary representation although there are many more octagonal hexagonal representation which but we will not go into them because they are never used in your programming only the binary one and it has a very high importance so coming on back that we know that this is the remainder so remainder is mod in programming terms remainder is this is 5 more 2 this is 2 more two this is 1 more two 1 more two so it is n mod 2 so I know that n mod 2 is the remainder which should be placed at a specific I index of this binary Vector I will place it and then I also know that I have to divide my number five by two this is a divisor so I will simply divide my number five by two and I have simply assigned it to same n because this is my N I am taking n is firstly this then n becomes two then n becomes one and then ultimately n becomes zero because my condition is actually on N while my n is more than zero keep on repeating the process so whatsoever divisor you have got simply assign it to n and ultimately as you go on to the next for Loop make sure to increase your ey pointer so as next time your I is increased and is assigned a new value so you saw that in the very beginning the first remainder is one that will go at the index zero the second remainder is zero that will go at the index one next is one that will go at the index two if I do a simple dry in the very beginning my n is five so 5 mod 2 is 1 at the index zero I will simply say okay I will have a binary value of one and then simply my n will become a two which is 5 by 2 I will increase and I will now become a one for the next follow Loop now again while my n is more than zero because you can see n has become two so n is for sure more than zero so simply two more two your binary Vector value has become one again you will do a simple 2x two to get the new value of N and increase your I point for the next loop again your one is more than zero still you can repeat this V Loop you will get 1 more two which is one again this is the binary Vector of index 2 which which I have already increased in the previous for Loop and then I will do a n is equal to n by2 Now 1 by 2 is 0 so n now has become zero I will also increase for the next for Loop next sorry next y Loop but now we will realize that 0 is not more than equal to 0 0 is equal to 0 so this Loop will break here and thus we have got our final representation of a vector although in your terms this will look something like this Vector is left to right so index zero is actually in the left in the most left but but make sure you represent the binary presentation from right to left so technically I can also show that Z to index value one first index value zero second index value one cool now what is the time complexity of this entire approach you can see you are every time dividing your number by two this is a while loop which is dependent upon n and n is the number which is being divided by two dividing by two dividing by two dividing by two so as I divide by two any number I have already seen in the complexity analysis video that that give me a o of n log n Factor base decides if the number kept on dividing by two what if if the number would have been dividing by 10 then I would have said it will be log n to the base 10 so this is how the complexity works but are what is the space complexity yeah that is the most interesting part so space complexity we'll be about number of different indexes which can come up in its actual n so you remember that you have a simple Vector that is what you made although technically you can argue with me that R in this Vector is already required so this should not be any extra space correct but still if I ask you what is the space used by this Vector you will tell AR I can simply see that this depends upon how many indexes I can give although technically I have to initially Define the size of this vector or I I have to do a push back here I have do a push back so but if I ask you rather than hard coding the size if I do a push back then how many maximum value I will be pushing back that is a question how many I be pushing back so as you can see at every n by two my I is increasing so it is that okay up till my n n is alive it will in it will keep on increasing the I and N is alive for log n by 2 base step log n to the base two number of steps my n is alive so I will increase my I log n to the base 2 number of times and that's number of the space used will be log n the base 2 now as we have already seen that we can simply have a decimal number and convert that to a binary and also previously we had also seen that binary decimals also we can convert let's see the program for converting our binary number to the decimal number although we had already seen that we will simply take firstly in the very beginning I will take a one multiply that one by a two I will get a two then multiply that existing two by two I'll get a four then multiply that four by Exist by two I'll get a eight and then multiply that by two I'll get a 16 mly that by two I'll get a 32 and so on and so forth this is the corresponding values but their contribution will be counted by what corresponding value I have in the binary vector so do I take the do I take its contribution yes because it is one do I take its contribution no no because it is zero do I take it contribution yes because it is one and for sure if something is not written all of them are zero all of them are zero so all of these are zero this is a zero this is a zero this is a zero all of these are zero so I'll simply write the exact same stuff in our code we have a binary Vector which is the same Vector representing this 101 101 make sure this is the zero Index this is the first Index this is the second index now if I come on back I will have a power of two which is initialized to one why is that needed because in the very beginning we saw that this is one this is two then four then 8 so existing power of two I have initialized to one and at every step or basically as I move on to every index of this specific Vector this Vector I keep on multiplying my existing Power of Two by Two okay multiply that existing power of two is one multiply that by two got a two the existing power of two became a 2 m that by two got a four now your existing power of two is four mtip that by two got a 8 so this is how I can keep on going about it so I'll go on to my entire binary Vector from from index 0 to up till whatsoever is the length then I have to as you can see I have to add the contribution so in the existing answer I'm just simply adding the contribution of what the binary Vector of I multiplied by the current power of two binary Vector of I MTI by current power of two and I know for the next step I have to just multiply the existing power of two multiply that by a two to get a new power of two which is two if you have existing power of 2 S2 multiply that by two to get a new power of two which is four so power of two multiply that by two I get a new value of R of2 which can be used in the next iteration of for Loop and that's how I can simply solve it now again the same way this will work this will this entire thing as you can see is bounded by the size of this binary Vector right and space technically we have just used this input space and we have just made two variables so no extra space is used but your question will be ar in how big this binary Vector can be because you can easily see I have taken integer I have taken integer so your question might be I must be multiplying something how big that number can go that is very important so we can easily see that this if we go on to the previous example the complexity of or the size of the binary Vector was limited by a login Factor if you remembered in the previous step the same way I can simply say is that this size if my n and you can see n at Max for your programming Journey you will have seen that at Max n is 10^ 18 this can easily fit into 64 space so if I take a log n off of this this will come around 63 or something so I can easily see that 64 blocks or the size of a 64 is maximum required and that to for a long long I have taken integer although I will show you in the very detail about long integer and all the sizes but I'm just showing you that this actually is a constant size which is at Max 64 now this is a very basic of your binary representation and that brings your base but you must be thinking Arian why is this binary number useful especially for CP and DSA like what what makes it so useful the so useful part is that if you had seen you had a length of n then this length of n you can convert this entire length of binary number representation into just a single number so I can do I can have an array and I can convert this array to just a single number and again this is not necessarily be sh an array it again if I take if I say it's an array it can be a visited array that I can convert again that is very highly used especially in graph entry problems and you will see that the problem list which I have given in that also I have given two variations one is of strings and one is of graphs in which both of these conversions are used to optimize your problem so the most important again the most important optimization use case for bit manipulation is converting a vector to actually single number and operate on those single number which is actually our because we know that binary number if I just have a binary array I can represent as a single decimal number now everything seems super fine but Aran uh what was the limit of N and what you were talking about as okay 64bit 32bit integer long long so you know that you have a 32bit integer why is that name given to him do you ever know that okay your integer which you have taken in your programming is actually a 32-bit integer your long long is actually a 64 bit so why is that the case see if I take this integer value the minimum value is this maximum again for rough estimate you can say it will be around 2 into 189 minus 2 into 189 and same way maximum is plus 2 into 199 again it has a specific value which I've written but this is how roughly you can go about to these values now if I just ask okay roughly if this is a value I can represent this value if I take a log n to the base 2 this this value will be less than my 32 so this means that I can represent this integer n in at Max 32 bits same way for my 64 bit which is like for your long long end the actual limits is this big again this big this you can easily represent as 64bit integers now it seems fine but uh you should are in this number now I will have the same number as 2 into 29 I will have the same number as minus 2 into 189 then am I not confused between how to write a negative representation versus a positive one which means for five you showed me that I can write it as a 101 then what about minus 5 do I have a use case for it although negative numbers are not that much used but they are internally helpful in determining a very good use case to determine other problems what I mean by that is this negative number representation you will learn how to achieve it that is achieved by simply once compliment and then flipping it and then this entire strategy is used in another problem of removing some last set bit then this strategy will actually be used in Fen victores and other problems which again I have listed in the entire problem practice problem like videos link which I given now this is the entire thing how these negative numbers are actually used not directly used but in this inactive it is used how so firstly let's represent our negative decimal which means I had a five I have to get the value of minus5 so how I achieve it there are a simple two-step process firstly get the On's complement don't worry about this name one's compliment simply make sure you represent your actual number five into its binary form which is as you can see 1 0 1 again this this is 32 bit and from right to left right when I say one's complement which means flip every bit so I will just flip every W which means okay this zero will become one this zero will become one this 0o will become one this one will become zero this zero will become one this one will become zero I just flipped every BD that is called as one's complement now when the step one is done just do one thing add A+ one in the end add the plus one in the end so if I have this flipped which means once complement representation I will simply add a plus one it is same way you add two numbers 0 + 1 is 1 1 + 0 is 1 so again I will show you the actual carryon and a bit hacky stuff in that as in like how this addition works but so far just remember it is a simple addition which is happening so I just simply add a one as you can see 0 + 1 is 1 and again everything if it is not written everything is a 0 0 0 0 so I will simply carry over these okay it's a one it's a zero it's a one and a one and a one so now I have got this value this is actually called as Min -5 this is called as Min -5 and if you want to have a quick again this is not important for you but if you want to have a glance at this number if the extreme leftmost bit if it's a one that represent it's a negative number it's a sign bit which is given to that specific leftmost bit as you can see for this original number the extreme leftmost bit was a zero it is a sign bit now coming on back that we talking about adding some number although in here we simply added it but R in you added a zero and a one so you got a one if you add a z and Z you'll get a zero but if I add a one and a one so technically in math terms adding a one and one you get a two but we know it's a binary representation so the value can be either a zero or a one nothing else so if I add a one and a one I got a two just imagine that you got a two just roll over the number which means say you got a two now roll over to the next number which is zero because 0 one and then next come is zero so R over to next zero and then you will still have a one left so carry over that one here again this is a simple strategy just how you can add your B although it will not be useful for you at all because nothing like no one will ask this it's just for your understanding of how these binary addition or subtraction will work same way I add a 1 plus 0 again it's the same carry over I add a 1 one I got a zero here and I carry over a one here then 1+ 0 I got a one then 1 + 0 1 1 + 0 1 cool same way uh if I had a 0 + 1 it's a one just add as it is now you have seen how to add the these numbers same way let's see how to subtract the numbers if I add if I do a 0 - 0 it's a 0 1 - 0 it's a 1 what about a 0 minus one then you have to take the carry from the left just first as you're doing a simple maths as you're doing a simple maths you ask for this one to get a one value he will be zero now but he will give you a two then 2 - 1 is a 1 same way if you had a one here you will ask for him he will he will be zero he will give you a two then again you have to give something two on the right so you will again take one from him he will get a one and he will get a two here now 2 - 1 is a 1 and 1 - 1 is a 1 0 1 so that's how you can simply get it and again to verify this is called as a number four 01 this is a number one if I do a subtraction I get a number three same way this is a number two this is a number one I'll get a number one this is in the decimal form so now you have realized that you can easily do addition and subtraction now comes the most important bit operators this is very very very very important listen it very carefully because I will tell you tricks on how to solve these bit operations primarily you have three most important operators although it seems like R and I for sure know about these and ORS or I know it but these are the most important ones and I will show you what you have to always look for as soon as you hear that and is being applied here so this is and this is or this is zor again in coding terms you represent and as and or as a single line or you just say this line I don't know and this is nothing but a carrot now all you have also a not operator but not just simply says one exact same thing as I showed you above also simply flip the bits which means if you have something flip the bits as you can see I just simply flipped the bits and that's how I got a not not is not that important and or and zor is very important in and again the basic thing which you also know I'm also telling that if I do a z and Z I'll get a zero one and 0 0 0 and one 0o one and one is the only thing which is one okay same way for or 0 or 0 0 0 or 1 is one one or0 is one one or one is one and the same way for zor that is very important for you to remember these that how they work 0 or Z Z's or 0 Z 1's or Z is z but Z's or one or Z's Z one is one 1 Z zero is one make sure this very important point if you do a zor with the same number you always get a zero if you do the zor of the same number number but RN it is a binary presentation right then how can you say bro if I have a five or five I can simply say five is 1 1 Z with one 0 1 same numbers z z same number z z same number z z so make sure same numberb Z is zero again this is a very important property we used again in the practice problem sheet one of the medium problems require this concept also so it is very important now coming on back this is not only about the and or enor operators the specific the most important thing is these properties again I have given example that how and operation will work corresponding bits one and one is one one and 0 or 0 and one is zero same way I did for the or and same way I did for the zor just make sure the corresponding bits you are doing the corresponding zor operation now the prime part is that make sure you always remember do a star mark on all these three conditions If Ever I have an and condition it again if I have an and condition between a few numbers let's say A and B and C and D and so on and so forth this is how we encounter the actual CP or DSA problems in that case always make sure that and always shrinks or keeps the value same of this entire evaluation which means if I have a value of let's say A and B B and C and D so I am saying and I'm always referring that this as I do A and B the value will either remain same or will shrink again let's say if this turns out to be the a dash again I'm saying a dash will be either equal to a or b again either equal to minimum of a or b or it will be even less than both A or B and same way if I keep on I'm just saying if I keep on doing the addition I will keep on either shrinking the value or the value in best case can remain same it can never increase on doing the hand operation and that's a very important property people say okay I it's it's obvious it's obvious people forget this obvious thing so as I can simply say that okay five and three if I do a simple and operation I can simply see that the value shrink and it became a one if I do a five and seven again the value remain five itself same way for or or value says that either the value increases or it remains same which means as I keep on doing the or of few values then it will either increase or will remain same which means five or three is nothing but my seven it increased five or four is same but five now zor zor it is also again this is very useful for flipping the specific bit I'm not saying about the not operation this F flip all the bits I am saying if I let's say want to flip some specific bit then I always used a use a zor operation how if I have a specific number five and I know that I have to flip the first bit AR what do you mean by first bit this is the zeroth bit this is the first bit this is the second bit always make sure this is how we name these binary numbers cool now I have want to flip this value so first make sure that you will make a mask where again I'll show you what the mask is and all that stuff but you will simply make a mask where this first bit will be there and then simply apply the zor operation so whatsoever you will get in this the first bit will be flipped if it was a one it will become a zero if it was a zero it will become a one that is how you can simply flip that specific IDE bit by simply again make a mask I will tell you how to make a mask of the I bit so simply make remember make a mask of ath bit and then apply the Z operation you will simply get a value in which others values are never affected only the value at the I location will be flipped and that is the beauty of zor operation now we talking about mask first what is a mask it is a very important concept for very medium medium easy medium medium hard and hard problems it's a very important concept of mask so mask in general what it is how it is made because you saw that this was a mask which is made firstly and why the name mask is given to him we'll see that and also why it is used okay we already saw that why it is used it is used to specifically highlight on a specific bit as you can see I when I was making this mask I told told you I made a mask of the first bit so I highlighted some specific bit so if you want to highlight some specific and only have to or only want to work on that specific bit then you make a mask that is a use case of mask now why is the name mask is given to him as you can see the simple face mask how we apply so this portion mask as you can see mask is applied at in in and on this portion right so my mask will actually clean up that portion of my face so my mask will affect this head portion this cheek portion and stuff but as you can see mask have some holes mask has some holes so this portion is never affected so mask helps us to affect or basically to impact only the portion which I want only the portion which I want I want to clean I want to maybe do anything with that portion I will apply mask on that portion so this is the beauty of mask as you can see that only this bit was actually impacted now comes the interesting fact that how to actually make this specific mask now as we simply saw that this is how the mask will look like in the very beginning in the very beginning we have to make sure that we are always given a number zero or a one zero has no value it's a zero but one has some value one has some value if I just take a one either as a decimal number or as a binary number if I take a one as a decimal number if I represent that one as a binary number then I will simply can write that same one as this binary form which means 0 and last in last one this is the same we seeing the decimal value of one will be equal to this binary representation this one is a very useful weapon for you how because now you have this one here and you can just make sure okay this is the one here in the if you remembered that for you when you have to make a mask you have to bring one on the first bit that's what you wanted you got this one right here simply shift this one shift where shift left one is here one okay this left for you right one is here I shift this left how much I shift this left how much I shift this one time if I if if this is the one this is the one if I shift this one one time I'll get a one here and again this will go blank this will go blank because I have shifted this and anything when it goes blank it means it's a zero make sure anything which goes blank is a zero so this is the one now this is the one now this is called as a left shift operator so I had a by default value of one this is the same value I have taken I applied what shift I applied a left shift as you can see people are very confused in these signs also that's also very important stuff firstly you must have realized that I actually shifted my one on the left side so the wording itself you are remembering okay if you have the one in the very extreme right you have to bring one at this location which means you have to shift your one to the left because it there's a number shift left so left shift wording you remember but how R and I will remember the sign as you can see this sign actually points to left this sign if if I simply make the sign and if I go you it's a path and if I make this sign this easily shows you now that okay go left if I make a sign like this it simply shows you go right so this sign will help you that okay you know you have to apply a left shift and this sign is to the left so apply left shift but okay apply left shift but I also made sure that okay my first bit is set my first bit set so technically my one was on the extreme right I have to just shift this one by one step so this next parameter says that by how many step should I shift my that specific number which is one for me and I so and I told you I will shift by one step so I get a number like this and this number itself is called a mask this is called as a mask same let's say if I give you another example let's say if you have a one you have to left shift by two times so it will become as you can see it shifted two times again empty places replaced with a zero so you'll get a one here now are in okay are you saying that can we only shift a number which is zero or one okay zero has no value of Shifting but yeah if I can I only shift a one I'm saying no you can also shift the normal numbers decimal numbers because if I convert this decimal number to a one1 I have to just make sure okay this entire thing is shifted left two times so I can entirely shift this left two times and that's how you simply do a left shift so you realized how important my left shift operator is and that is primarily used for making your mask and again if you look very closely what is happening in this left shift is that you are actually skipping a bit you are just skipping a bit and we remembered that every bit has a contribution of a factor of two so technically by doing a left shift you are multiplying that number by two right again don't do a ratification of it you remember that contribution of every V is a factor of two as I go on to next number I multiply by two next number multiply by that two you remembered one you remember 1 2 4 8 16 and so on and so forth so I remembered every contribution of a bit is a fact multiplied by two it is multiplied by two so I know if I do a left shift I'm actually skipping a bit and going on to the next bit which means I'm actually skipping a factor of two so just simply make sure to multiply that by two and you can also see by example as I can see I shift left shift of one one time I multiply that by two I left shift of one two times I multiply that by two two times 1 into two into two I got a four same way I I have done one left shift three I would have got a eight same way for every other number also now if we are studying left shift let's also see right shift it is again although it is not that much used because left shift is primarily used in making mask and then operating on those mask right shift is not that much used it is ideally again this operation or this use case of right shift you will again see in the practice problem list which I have given because you remember that I had a integer representation of a 32 bits so I can simply place my numbers in those 32 bits I can use those places for placing two numbers also this this problem you will see in the practice problem playlist which means this will help you understand the use case of your right shift this is very important also not that much not directly used but applied in problems now same way as that of left shift right shift simply says that if you have a number let's say five I have taken in this case I just simply shift this right if I shift something right okay I know that this is the zeroth bit this is the first bit if I'm shifting it right where this will one go it has no space it is the same V saying I am standing at a bench I'm sitting on the left soorry extreme right someone says me shift right I will go down go down lost down lost so as soon as something is Shifting right it is going down and getting lost so same way if this thing wants to shift right it will get lost same way it will also get lost so this will become your zeroth bit so this is how your right shift twice will work same way as you can simply see I will have value of one same way saying right shift will divide the number by two so I have five one time I did a right shift I got a two another time I do a right shift I got a one that is the reason I got a one so left shift will actually go on to and shift the bit to the left side and we multiply the number by one right shift we'll shift the bit to the right side and multiply the number by sorry divide the number by two okay these things are done and we also learned that how easily we can flip a bit and that is done by zor operation but flipping a bit as in okay it's a one will become a zero if it's a zero it will become one but what if I primarily wanted okay no matter what if it's a one or a zero make it a one or if it's a zero one make it a zero so this is called as a set the specific bit or unset the specific bit again as soon as I'm talking about a specific bit I know one thing for sure that my mask will come in picture right and this set and unset word we had already seen in the very beginning I told you set means okay the bit value is one unset means the bit value is zero and I'm saying no matter what I'm saying no matter what even if the bit value at that location is a zero or one no matter what it should become a one if I do a set if I do a unset no matter values of Z or one I should make it a zero no matter what so if I am saying that okay set a specific bit I have given a mask to you okay make the I get bit as set so I know that I'll do a one left shift I to make a mask of one on the I location so for sure I know that I will simply make a mask at the I location which means one is there and rest all for sure will be a zero now I have to make sure whatsoever my n value is this location again let's represent the any arbitrary in value let's say 1 0 1 1 1 0 0 I want to specifically set this what do you think what operation I should apply operation remember the and or or these are the only operation which we have in picture that's it that's it so if I want again I'm saying anything it can be one here it can be zero here anything whatsoever it should become a one simply it is a r operation because one is fixed so if you go back to the or operation which you learned you see that one is fixed if you have one on one of the sides you will simply get a one for sure as a result so I realize that I can simply apply a simple or operation so I do n or this is a or one left shift I which is a mask I will simply set the I bit as one an example you can see in front of your eyes n was let's say five which is 101 I want to set the third bit I do a one left shift three my one is left shifted three times I will simply set this bit again make sure all the other bits remain untouched intact that's set and this bit will set for sure even if it would have been a one it will still have got set same way if I want to unset if I want to to unset the bit which means again I'll take the same example let's say if I have an n and I want to unset the specific bit answer this bit I know technically my mask will make a one 0 0 0 0 even if I do a and operation for sure or operation will will not even work because what if it's a zero I want to unset the bit or operation will set the bit I I don't want that can I apply a zor operation if I do apply a zor if it's a zero my mask will have a one I will make it a one I also don't want that okay how about and operation seems like seems nice that because zero and one will will will be a zero Set uh but what if what if if this would have been a one one and one will be a one H you ideally wanted to actually make this number as zero no matter what if even if it's a zero make a zero even if it's a one make a zero but unset the specific bit but my mask says a one ideally I should place and instead of this one what if I actually do one thing what what if I have a zero here and rest all are one so I inverted my mask I flipped my entire mask if you remembered not operation is the one which flip the entire entire stuff so I'll do a simple not operation which will flip the entire stuff now I have got a zero here if you remembered and operation is the one that no matter what you do if you have a zero in the end you will for sure get a zero value and because of these all are ones so other values will remain untouched these will remain intact of what n had provided me and this will for sure turn to zero and that's how I simply by using and and not I'll simply get and can unset my specific I bit make sure these are very important Concepts and these are the most used ones now you have flipped the bit flipped the I bit you have unset the I bit you have set the I bit but what about you have to check if some specific ath bit is set or not because it might be important that you have to check if that bit is sit but Aran why would I need that even in future because as I told you in the very beginning I can have given you a I could have given you a string which means a b c d e let's say I represent this string in a form of a binary number so I would represented okay let's say I have a a b d okay let's say I have a a e so I I would have represent this represent that as a 0 one okay it's a zero bit it's a first bit it's a second bit it's a third bit it's a fourth bit so a is there b is there C is not there D is not there e is there so I would have represented this string in as a form of one integer and let's say if I ask you I want to know do I have a D in this string I will simply check if the ith bit is set or not that is the use case where your set or unset bit checking that will be required again this exact same problem you can see in the practice problem medium playlist like medium problems in which what I have given in the comment in the description below now coming on back we can simply see we have to check if the I bit is set or not simply we'll take the exact same example where n is five five 1 1 I want to check let's say if my second bit second bit which means 0 1 2 if this second bit is set or not I have to check that make sure always when you have to work on a specific bit make a mask of it first so I'll firstly make a mask of it which means one left shift I which means one left shift two times I want to check the second bit so I simply got a one and rest all a zero now I want to check if that bit is set or not right set or not what is the operation which you should make sure you should apply it what if I apply a or operation then what I will get no matter if it's a zero or one I will for sure get a one it's it's it's it's not good for me what if I apply and operation I will get a one here only if this location is a one if this is a zero I'll get a zero here so if I apply and operation if I apply and operation I will get the exact same bit on this location but R what about the other bits other bits as you can see all the other bits are here zero so and of anything with a zero will for sure be zero so other bits will all be zero and this bit I bit will only B one provided this I bit is one on in the number five and this is my actual main Crux how I will simply use this ith bit I simply use I bit to determine if this number I have got is a nonzero number which means for sure again why nonzero Aran because this bit can be set at any location it can be one here also so if I convert that to a number it can be any different number any non zero number I'm specifically focusing on a zero is because of the reason if the bit is zero in my n equal 5 then for sure as as as I told you this will become a zero and rest all will for sure be zero because of the and operation which I'm doing all right thus the entire number is zero so if the entire number is a zero then the bit was unset if the number is non zero then the bit was set and this is a entire C that you will simply do a n and operation with the mass which is one left shift I if this value is equal to zero which means the bit is not set if it is not zero it is set and that's how you simply you can achieve your answer now now comes that okay if we slightly use these stuff which we have studied left shift right shift mask which are very important concept and and the only concept which you need for bet manipulation problems comes is next important Point finding the rightmost bit or removing the rightmost bit but Arian it is a problem rather than concept right so why should I study it like I can just solve the problem for it like it's a problem right although technically makes sense it's a problem and you can simply solve it by making mask and stuff which I've already told you earlier but what is so so special about it is it is directly like hands on like put it like this used in another algorithms one of them being F victories and not only this but also directly use in another famously known problems for example power of two or maybe another number in that you just have to remove the last set bit again removing the last set bit is the same way I'm saying flip the last set bit if I flip a set bit it will become a zero which means removing that last set bit so this is very very very important that you specifically focus on the last bit again when I say last I mean okay if it's a number 1 0 1 0 1 1 0 0 so last set bit this is the last set bit for me right last set bit for me I have to work upon it I have to Simply remove it make it a zero this is very special and you will see why it is so special it will actually help you solving many problems and many tricks you'll get know by this so one I I I'll tell you two ways to get or to basically remove the last set bit or basically to flip the last set bit I'll two two very important ways one of the ways again both have their importance in bit manipulation one of the Bas is again R why you have taken id id and stuff because this exact same stuff we have already taught on our in our bit manipulation crash course that in bit manipulation the prime thing is actually using your numbers and getting a value out in that you use the id id as an index it's the same we have taken the exact same stuff that if you have this number called as ID and you have to remove this last bit this last again for you this is the last set bit and you have to just simply remove it remove it as in make it a zero make it a zero so what you will do you will simply grab this ID which is 0111 you know that you have to flip this bit so ideally this bit should be this bit should be gone now you have to get something that this bit this bit is remaining and like others are actually like so this bit is gone and other are remaining so I did a minus of ID what is this minus minus is nothing but two's complement if you remember in the very beginning I showed you if you have a decimal number if you want to do a minus of that some firstly flip the bits I have a 011 I'll flip the bits I'll get a 1 0 0 0 then I add a plus one this plus one is the two's complement so this is one's complement plus one is the two's complement so this is the two's complement of a number which is negative of a number I'll simply get a 1 1 now on this one1 I will simply apply a and how this will help me this will help me in simply saying bro get this a one get this get this a one simply get the mask of the rightmost set bit but in if I want to achieve a mask I can simply achieve by iterating on this entire number from the right side yes you can do it but if you know that this operation which you do which you did here I D and minus ID it's a o of one operation exactly of one but if you go on and search for this number from right to left for the first bit which is set it will take at Max o of 64 time o of 64 time although it also constant but still this is higher than actually constant o of one operation cool that's the reason this I have got a mask which is having the extreme rightmost set bit right and now I have to Simply make sure I simply remove this from my existing number ID from the existing number ID I'll simply remove this mask simply subtract this number one I'll simply get a zero at that last set bit location and the other numbers remain intact as it is so I simply did flip the bits this one more strategy of flipping that last set bit and again I'm showing both of them because both have the importance the above one I showed you has importance in Fen victores because we have told that exactly same in Fen victores you can use other strategies also but it's good to know that how these are linked to each other and that's the only one right this is the only course which you need for all the problems of a b manipulation that's so good right yeah the strategy says get a number again you have to make sure you have to remove this last set bit if I look back closely to my previous number which is n minus one I will look that okay everything remains same in that the last set bit is actually unset so what I can do is I can do and operation with my previous number and I will make sure I will unset the last set bit but then you will have a question Arian then why can't I simply take my previous number okay I did a n and n minus one I got a 1 0 1 1 0 0 which means this bit was unset because of the previous mask technically why can't I simply take this number 12 okay if you say that then simply look at this example 12 and 11 so if you say that for 12 you'll take 11 that's obviously wrong because you wanted to remove this specific one right so it is the reason you will do 12 and 11 12 and 11 which means n and n minus one how it will help you it will help you by saying that this is the bit which will get unset I will simply unset my last set bit because you can see this is the last bit which is set and I will simply unset this bit and get the answer awesome right yes make sure we D on this part also okay N is8 I will just check from the last number and then last number is seven I do add this is okay I had only one set bit and that set bit I have simply removed so number becomes a zero and this is a very great point we should which you should remember what's the point you always remember that if I have one in the binary representation they are the contribution the factors of two right so one if I have a one in the very beginning let's say 0 0 0 0 1 this is one if I have a 0 1 this is two 1 0 it's a four it's a eight it's a 16 so for the powers of two we realize we will have only one set bit so anyhow if I want to figure out any power of two if I have a number and I want to figure out if that number is a power of two or not then I can simply say that if n and n minus one if it is equal to zero then for sure it had only one set bit which means it's is a power of two else it is not and that is the beauty of this now this is the entire stuff which you should know make sure you very well know how to make a mask how to set and set the bit how to flip the bits how to know that I bit is set or not and especially make sure you always remember these three strategies of and or and zor and never forget this entire Crux now make sure that you will go and practice all these problems every problems have a specific thing which they going to teach you so make sure you practice them because see I have written what this going to teach you what this going to teach you so everything has a significance now go and rock bye-bye if you like this video if you want other crash course to be coming in just comment down below which other crash course you want we will focus only on the specific tricks and stuff which will help you to solve any problem whatsoever this is one stop video for your any issue on bit manipulation and do make sure to join the Discord Channel and also see the comment section below bye-bye take care

hi guys good morning welcome back to the new crash course so this going to be a bit manipulation crash course in which we going to cover every concept you going to need for any problem from easy medium medium hard to hard so the contents which you going to cover in this video are okay all these contents you can pause and read if you want and also on top of it for every concept you read or you have studied or you can encounter in bit manipulation or bit masking these are problems easy medium and hard which I will give corresponding video links also in description below for you to practice and notes you can see on COD within.com again right now it is not uploaded but yeah we will have them soon in this website so in the very beginning starting with what actually is bit manipulation simply we not go into very deep because we are actually going into deep step by step but pit manipulation is the act of algorithmically manipulating bits for us basically we are talking about these bits which are nothing but zeros and ones binary numbers are these and we&#39;ll just use them or manipulate them the same way your X manipulates you that the same way we will manipulate these bits to get our value done to get our answer so first very basic thing is what are these binary numbers and how these are used in programming so you usually deal with the normal numbers which are 10 15 20 these are called as the decimal numbers so firstly we&#39;ll see okay if you want to even use those binary numbers how we will convert them so we have to convert these normal decimal numbers again these numbers which you see in daily life 10 15 30 45 all these are decimal numbers we will convert them into the binary number although we have usually seen in the fifth standard okay and decimal number five we can represent that as a binary number as 1 1 make sure binary numbers are written from right to left so this is the zeroth bit this is the first bit this is the second bit that is one thing you have to make sure forever in this course now we will firstly understand that this decimal number how we will convert it programmatically into this binary number we can easily see that this binary number is 101 five&#39;s binary representation is 101 101 so if I ask you pause a minute and if I have given you this binary number and I would have asked you convert it back so this is much easier for the people how because they know that this is the extreme rightmost bit has a contribution of 2^ 0 then the next bit which is the first bit have a contribution of 2^ 1 the next bit have a contribution of 2^ 2 and then the actual contribution will be 1 0 or one which means Zer saying do I take this contribution even in consideration or not one is saying do I take this contribution even in consideration or not so as soon as I multiply something by zero it will ultimately become a zero this will still remain as it which is 2^ 2 this will still remain as it which is 2^ 0 so the answer is 4 + 1 which is 5 so now you know that if any way I would have given you a binary representation of a number you can easily go on from right to left contribute for the zero bit 2^ 0 then the next bit 2^ 1 the next bit 2 power two and so on and so forth and you can just check the contribution and get the value programmatically we will also see later on but this is for you just get familiarize of how these binary numbers we can convert them back to decimal but this is not important because we always start the decimal number now the big question is how we convert this decimal number into the binary number so if you saw above I was actually multiplying by two to get my next value next value next value same way from decimal to Binary I will keep on dividing by two so if I have a number five I will divide by two I&#39;ll get a remainder as one and then whatever okay 2 2 are 4 right then okay remainder is one again two I divide then remainder is zero okay one I have got because 2 1&#39;s are two then two I divide like one by two I get the divisor as zero but remainder will be one now AR in how to write this write always backwards because you know things in this work from right to left so if things work from right to left and you have got this value which is one so you will have to write this one here which is this is the C this is the B and this is the a so ultimately like for us in human writing we write from right to left but these binary things or binary representations work from right to left we write from left to right but these work from right to left so it&#39;s the reason you have to make sure that this is the zeroth bit which you write then the the first bit then the second bit so the first number which you have got is the zeroth bit then the first bit then the second bit that is how you write it but Aran like you represent the AR like is it the array which you have represented um you can say but if I can say then I should also say that the arrays are actually represented from left to right so ideally this should be the zeroth index this should be the first Index this should be the second index yeah that is true that is the reason although I will show show you as in this representation which means I will show you an array in which the indexing I I will show you okay it is a zero index it is the first index but I will always write from right to left but in programming make sure this zero index actually comes in in the LIF it should be one it should be zero it should be one this is a prime portion of your binary numbers that is very confusing for people that oh how it is working right left or left right but we&#39;ll make sure in program also and I will Dy also for you that how this will work but just make sure one thing that what they actually are called this one is called as a set bit which means at this location the bit is set okay he set this zero say okay it is unset which means it is not yet set this is are the few terminology which you should be knowing so as to easily understand what the actual web will tell you now we realized we can easily convert our any integer decimal number to a binary number by simply keep on dividing that by two the remainder whatsoever I&#39;m getting I will store that remainder in my actual Vector I can take a vector I can store in a vector and that will be actually my binary representation of a number so let&#39;s imagine I have take a binary Vector which will store the binary information of a specific number n and and then I have taken an index why index because I know that as soon as I will place an element at a specific index I I have to move my index I to the next location which is i++ now I have to keep on repeating this step until my this number which was N I gave in it becomes a zero I have to keep on repeating that you can easily see so I have simply written that while my n is more than zero I should keep keep on repeating my step what was the step I was repeating I was simply firstly getting the remainder of a number okay I will get N I will simply divide that number by two because this two is always fixed because I&#39;m converted to a binary representation although there are many more octagonal hexagonal representation which but we will not go into them because they are never used in your programming only the binary one and it has a very high importance so coming on back that we know that this is the remainder so remainder is mod in programming terms remainder is this is 5 more 2 this is 2 more two this is 1 more two 1 more two so it is n mod 2 so I know that n mod 2 is the remainder which should be placed at a specific I index of this binary Vector I will place it and then I also know that I have to divide my number five by two this is a divisor so I will simply divide my number five by two and I have simply assigned it to same n because this is my N I am taking n is firstly this then n becomes two then n becomes one and then ultimately n becomes zero because my condition is actually on N while my n is more than zero keep on repeating the process so whatsoever divisor you have got simply assign it to n and ultimately as you go on to the next for Loop make sure to increase your ey pointer so as next time your I is increased and is assigned a new value so you saw that in the very beginning the first remainder is one that will go at the index zero the second remainder is zero that will go at the index one next is one that will go at the index two if I do a simple dry in the very beginning my n is five so 5 mod 2 is 1 at the index zero I will simply say okay I will have a binary value of one and then simply my n will become a two which is 5 by 2 I will increase and I will now become a one for the next follow Loop now again while my n is more than zero because you can see n has become two so n is for sure more than zero so simply two more two your binary Vector value has become one again you will do a simple 2x two to get the new value of N and increase your I point for the next loop again your one is more than zero still you can repeat this V Loop you will get 1 more two which is one again this is the binary Vector of index 2 which which I have already increased in the previous for Loop and then I will do a n is equal to n by2 Now 1 by 2 is 0 so n now has become zero I will also increase for the next for Loop next sorry next y Loop but now we will realize that 0 is not more than equal to 0 0 is equal to 0 so this Loop will break here and thus we have got our final representation of a vector although in your terms this will look something like this Vector is left to right so index zero is actually in the left in the most left but but make sure you represent the binary presentation from right to left so technically I can also show that Z to index value one first index value zero second index value one cool now what is the time complexity of this entire approach you can see you are every time dividing your number by two this is a while loop which is dependent upon n and n is the number which is being divided by two dividing by two dividing by two dividing by two so as I divide by two any number I have already seen in the complexity analysis video that that give me a o of n log n Factor base decides if the number kept on dividing by two what if if the number would have been dividing by 10 then I would have said it will be log n to the base 10 so this is how the complexity works but are what is the space complexity yeah that is the most interesting part so space complexity we&#39;ll be about number of different indexes which can come up in its actual n so you remember that you have a simple Vector that is what you made although technically you can argue with me that R in this Vector is already required so this should not be any extra space correct but still if I ask you what is the space used by this Vector you will tell AR I can simply see that this depends upon how many indexes I can give although technically I have to initially Define the size of this vector or I I have to do a push back here I have do a push back so but if I ask you rather than hard coding the size if I do a push back then how many maximum value I will be pushing back that is a question how many I be pushing back so as you can see at every n by two my I is increasing so it is that okay up till my n n is alive it will in it will keep on increasing the I and N is alive for log n by 2 base step log n to the base two number of steps my n is alive so I will increase my I log n to the base 2 number of times and that&#39;s number of the space used will be log n the base 2 now as we have already seen that we can simply have a decimal number and convert that to a binary and also previously we had also seen that binary decimals also we can convert let&#39;s see the program for converting our binary number to the decimal number although we had already seen that we will simply take firstly in the very beginning I will take a one multiply that one by a two I will get a two then multiply that existing two by two I&#39;ll get a four then multiply that four by Exist by two I&#39;ll get a eight and then multiply that by two I&#39;ll get a 16 mly that by two I&#39;ll get a 32 and so on and so forth this is the corresponding values but their contribution will be counted by what corresponding value I have in the binary vector so do I take the do I take its contribution yes because it is one do I take its contribution no no because it is zero do I take it contribution yes because it is one and for sure if something is not written all of them are zero all of them are zero so all of these are zero this is a zero this is a zero this is a zero all of these are zero so I&#39;ll simply write the exact same stuff in our code we have a binary Vector which is the same Vector representing this 101 101 make sure this is the zero Index this is the first Index this is the second index now if I come on back I will have a power of two which is initialized to one why is that needed because in the very beginning we saw that this is one this is two then four then 8 so existing power of two I have initialized to one and at every step or basically as I move on to every index of this specific Vector this Vector I keep on multiplying my existing Power of Two by Two okay multiply that existing power of two is one multiply that by two got a two the existing power of two became a 2 m that by two got a four now your existing power of two is four mtip that by two got a 8 so this is how I can keep on going about it so I&#39;ll go on to my entire binary Vector from from index 0 to up till whatsoever is the length then I have to as you can see I have to add the contribution so in the existing answer I&#39;m just simply adding the contribution of what the binary Vector of I multiplied by the current power of two binary Vector of I MTI by current power of two and I know for the next step I have to just multiply the existing power of two multiply that by a two to get a new power of two which is two if you have existing power of 2 S2 multiply that by two to get a new power of two which is four so power of two multiply that by two I get a new value of R of2 which can be used in the next iteration of for Loop and that&#39;s how I can simply solve it now again the same way this will work this will this entire thing as you can see is bounded by the size of this binary Vector right and space technically we have just used this input space and we have just made two variables so no extra space is used but your question will be ar in how big this binary Vector can be because you can easily see I have taken integer I have taken integer so your question might be I must be multiplying something how big that number can go that is very important so we can easily see that this if we go on to the previous example the complexity of or the size of the binary Vector was limited by a login Factor if you remembered in the previous step the same way I can simply say is that this size if my n and you can see n at Max for your programming Journey you will have seen that at Max n is 10^ 18 this can easily fit into 64 space so if I take a log n off of this this will come around 63 or something so I can easily see that 64 blocks or the size of a 64 is maximum required and that to for a long long I have taken integer although I will show you in the very detail about long integer and all the sizes but I&#39;m just showing you that this actually is a constant size which is at Max 64 now this is a very basic of your binary representation and that brings your base but you must be thinking Arian why is this binary number useful especially for CP and DSA like what what makes it so useful the so useful part is that if you had seen you had a length of n then this length of n you can convert this entire length of binary number representation into just a single number so I can do I can have an array and I can convert this array to just a single number and again this is not necessarily be sh an array it again if I take if I say it&#39;s an array it can be a visited array that I can convert again that is very highly used especially in graph entry problems and you will see that the problem list which I have given in that also I have given two variations one is of strings and one is of graphs in which both of these conversions are used to optimize your problem so the most important again the most important optimization use case for bit manipulation is converting a vector to actually single number and operate on those single number which is actually our because we know that binary number if I just have a binary array I can represent as a single decimal number now everything seems super fine but Aran uh what was the limit of N and what you were talking about as okay 64bit 32bit integer long long so you know that you have a 32bit integer why is that name given to him do you ever know that okay your integer which you have taken in your programming is actually a 32-bit integer your long long is actually a 64 bit so why is that the case see if I take this integer value the minimum value is this maximum again for rough estimate you can say it will be around 2 into 189 minus 2 into 189 and same way maximum is plus 2 into 199 again it has a specific value which I&#39;ve written but this is how roughly you can go about to these values now if I just ask okay roughly if this is a value I can represent this value if I take a log n to the base 2 this this value will be less than my 32 so this means that I can represent this integer n in at Max 32 bits same way for my 64 bit which is like for your long long end the actual limits is this big again this big this you can easily represent as 64bit integers now it seems fine but uh you should are in this number now I will have the same number as 2 into 29 I will have the same number as minus 2 into 189 then am I not confused between how to write a negative representation versus a positive one which means for five you showed me that I can write it as a 101 then what about minus 5 do I have a use case for it although negative numbers are not that much used but they are internally helpful in determining a very good use case to determine other problems what I mean by that is this negative number representation you will learn how to achieve it that is achieved by simply once compliment and then flipping it and then this entire strategy is used in another problem of removing some last set bit then this strategy will actually be used in Fen victores and other problems which again I have listed in the entire problem practice problem like videos link which I given now this is the entire thing how these negative numbers are actually used not directly used but in this inactive it is used how so firstly let&#39;s represent our negative decimal which means I had a five I have to get the value of minus5 so how I achieve it there are a simple two-step process firstly get the On&#39;s complement don&#39;t worry about this name one&#39;s compliment simply make sure you represent your actual number five into its binary form which is as you can see 1 0 1 again this this is 32 bit and from right to left right when I say one&#39;s complement which means flip every bit so I will just flip every W which means okay this zero will become one this zero will become one this 0o will become one this one will become zero this zero will become one this one will become zero I just flipped every BD that is called as one&#39;s complement now when the step one is done just do one thing add A+ one in the end add the plus one in the end so if I have this flipped which means once complement representation I will simply add a plus one it is same way you add two numbers 0 + 1 is 1 1 + 0 is 1 so again I will show you the actual carryon and a bit hacky stuff in that as in like how this addition works but so far just remember it is a simple addition which is happening so I just simply add a one as you can see 0 + 1 is 1 and again everything if it is not written everything is a 0 0 0 0 so I will simply carry over these okay it&#39;s a one it&#39;s a zero it&#39;s a one and a one and a one so now I have got this value this is actually called as Min -5 this is called as Min -5 and if you want to have a quick again this is not important for you but if you want to have a glance at this number if the extreme leftmost bit if it&#39;s a one that represent it&#39;s a negative number it&#39;s a sign bit which is given to that specific leftmost bit as you can see for this original number the extreme leftmost bit was a zero it is a sign bit now coming on back that we talking about adding some number although in here we simply added it but R in you added a zero and a one so you got a one if you add a z and Z you&#39;ll get a zero but if I add a one and a one so technically in math terms adding a one and one you get a two but we know it&#39;s a binary representation so the value can be either a zero or a one nothing else so if I add a one and a one I got a two just imagine that you got a two just roll over the number which means say you got a two now roll over to the next number which is zero because 0 one and then next come is zero so R over to next zero and then you will still have a one left so carry over that one here again this is a simple strategy just how you can add your B although it will not be useful for you at all because nothing like no one will ask this it&#39;s just for your understanding of how these binary addition or subtraction will work same way I add a 1 plus 0 again it&#39;s the same carry over I add a 1 one I got a zero here and I carry over a one here then 1+ 0 I got a one then 1 + 0 1 1 + 0 1 cool same way uh if I had a 0 + 1 it&#39;s a one just add as it is now you have seen how to add the these numbers same way let&#39;s see how to subtract the numbers if I add if I do a 0 - 0 it&#39;s a 0 1 - 0 it&#39;s a 1 what about a 0 minus one then you have to take the carry from the left just first as you&#39;re doing a simple maths as you&#39;re doing a simple maths you ask for this one to get a one value he will be zero now but he will give you a two then 2 - 1 is a 1 same way if you had a one here you will ask for him he will he will be zero he will give you a two then again you have to give something two on the right so you will again take one from him he will get a one and he will get a two here now 2 - 1 is a 1 and 1 - 1 is a 1 0 1 so that&#39;s how you can simply get it and again to verify this is called as a number four 01 this is a number one if I do a subtraction I get a number three same way this is a number two this is a number one I&#39;ll get a number one this is in the decimal form so now you have realized that you can easily do addition and subtraction now comes the most important bit operators this is very very very very important listen it very carefully because I will tell you tricks on how to solve these bit operations primarily you have three most important operators although it seems like R and I for sure know about these and ORS or I know it but these are the most important ones and I will show you what you have to always look for as soon as you hear that and is being applied here so this is and this is or this is zor again in coding terms you represent and as and or as a single line or you just say this line I don&#39;t know and this is nothing but a carrot now all you have also a not operator but not just simply says one exact same thing as I showed you above also simply flip the bits which means if you have something flip the bits as you can see I just simply flipped the bits and that&#39;s how I got a not not is not that important and or and zor is very important in and again the basic thing which you also know I&#39;m also telling that if I do a z and Z I&#39;ll get a zero one and 0 0 0 and one 0o one and one is the only thing which is one okay same way for or 0 or 0 0 0 or 1 is one one or0 is one one or one is one and the same way for zor that is very important for you to remember these that how they work 0 or Z Z&#39;s or 0 Z 1&#39;s or Z is z but Z&#39;s or one or Z&#39;s Z one is one 1 Z zero is one make sure this very important point if you do a zor with the same number you always get a zero if you do the zor of the same number number but RN it is a binary presentation right then how can you say bro if I have a five or five I can simply say five is 1 1 Z with one 0 1 same numbers z z same number z z same number z z so make sure same numberb Z is zero again this is a very important property we used again in the practice problem sheet one of the medium problems require this concept also so it is very important now coming on back this is not only about the and or enor operators the specific the most important thing is these properties again I have given example that how and operation will work corresponding bits one and one is one one and 0 or 0 and one is zero same way I did for the or and same way I did for the zor just make sure the corresponding bits you are doing the corresponding zor operation now the prime part is that make sure you always remember do a star mark on all these three conditions If Ever I have an and condition it again if I have an and condition between a few numbers let&#39;s say A and B and C and D and so on and so forth this is how we encounter the actual CP or DSA problems in that case always make sure that and always shrinks or keeps the value same of this entire evaluation which means if I have a value of let&#39;s say A and B B and C and D so I am saying and I&#39;m always referring that this as I do A and B the value will either remain same or will shrink again let&#39;s say if this turns out to be the a dash again I&#39;m saying a dash will be either equal to a or b again either equal to minimum of a or b or it will be even less than both A or B and same way if I keep on I&#39;m just saying if I keep on doing the addition I will keep on either shrinking the value or the value in best case can remain same it can never increase on doing the hand operation and that&#39;s a very important property people say okay I it&#39;s it&#39;s obvious it&#39;s obvious people forget this obvious thing so as I can simply say that okay five and three if I do a simple and operation I can simply see that the value shrink and it became a one if I do a five and seven again the value remain five itself same way for or or value says that either the value increases or it remains same which means as I keep on doing the or of few values then it will either increase or will remain same which means five or three is nothing but my seven it increased five or four is same but five now zor zor it is also again this is very useful for flipping the specific bit I&#39;m not saying about the not operation this F flip all the bits I am saying if I let&#39;s say want to flip some specific bit then I always used a use a zor operation how if I have a specific number five and I know that I have to flip the first bit AR what do you mean by first bit this is the zeroth bit this is the first bit this is the second bit always make sure this is how we name these binary numbers cool now I have want to flip this value so first make sure that you will make a mask where again I&#39;ll show you what the mask is and all that stuff but you will simply make a mask where this first bit will be there and then simply apply the zor operation so whatsoever you will get in this the first bit will be flipped if it was a one it will become a zero if it was a zero it will become a one that is how you can simply flip that specific IDE bit by simply again make a mask I will tell you how to make a mask of the I bit so simply make remember make a mask of ath bit and then apply the Z operation you will simply get a value in which others values are never affected only the value at the I location will be flipped and that is the beauty of zor operation now we talking about mask first what is a mask it is a very important concept for very medium medium easy medium medium hard and hard problems it&#39;s a very important concept of mask so mask in general what it is how it is made because you saw that this was a mask which is made firstly and why the name mask is given to him we&#39;ll see that and also why it is used okay we already saw that why it is used it is used to specifically highlight on a specific bit as you can see I when I was making this mask I told told you I made a mask of the first bit so I highlighted some specific bit so if you want to highlight some specific and only have to or only want to work on that specific bit then you make a mask that is a use case of mask now why is the name mask is given to him as you can see the simple face mask how we apply so this portion mask as you can see mask is applied at in in and on this portion right so my mask will actually clean up that portion of my face so my mask will affect this head portion this cheek portion and stuff but as you can see mask have some holes mask has some holes so this portion is never affected so mask helps us to affect or basically to impact only the portion which I want only the portion which I want I want to clean I want to maybe do anything with that portion I will apply mask on that portion so this is the beauty of mask as you can see that only this bit was actually impacted now comes the interesting fact that how to actually make this specific mask now as we simply saw that this is how the mask will look like in the very beginning in the very beginning we have to make sure that we are always given a number zero or a one zero has no value it&#39;s a zero but one has some value one has some value if I just take a one either as a decimal number or as a binary number if I take a one as a decimal number if I represent that one as a binary number then I will simply can write that same one as this binary form which means 0 and last in last one this is the same we seeing the decimal value of one will be equal to this binary representation this one is a very useful weapon for you how because now you have this one here and you can just make sure okay this is the one here in the if you remembered that for you when you have to make a mask you have to bring one on the first bit that&#39;s what you wanted you got this one right here simply shift this one shift where shift left one is here one okay this left for you right one is here I shift this left how much I shift this left how much I shift this one time if I if if this is the one this is the one if I shift this one one time I&#39;ll get a one here and again this will go blank this will go blank because I have shifted this and anything when it goes blank it means it&#39;s a zero make sure anything which goes blank is a zero so this is the one now this is the one now this is called as a left shift operator so I had a by default value of one this is the same value I have taken I applied what shift I applied a left shift as you can see people are very confused in these signs also that&#39;s also very important stuff firstly you must have realized that I actually shifted my one on the left side so the wording itself you are remembering okay if you have the one in the very extreme right you have to bring one at this location which means you have to shift your one to the left because it there&#39;s a number shift left so left shift wording you remember but how R and I will remember the sign as you can see this sign actually points to left this sign if if I simply make the sign and if I go you it&#39;s a path and if I make this sign this easily shows you now that okay go left if I make a sign like this it simply shows you go right so this sign will help you that okay you know you have to apply a left shift and this sign is to the left so apply left shift but okay apply left shift but I also made sure that okay my first bit is set my first bit set so technically my one was on the extreme right I have to just shift this one by one step so this next parameter says that by how many step should I shift my that specific number which is one for me and I so and I told you I will shift by one step so I get a number like this and this number itself is called a mask this is called as a mask same let&#39;s say if I give you another example let&#39;s say if you have a one you have to left shift by two times so it will become as you can see it shifted two times again empty places replaced with a zero so you&#39;ll get a one here now are in okay are you saying that can we only shift a number which is zero or one okay zero has no value of Shifting but yeah if I can I only shift a one I&#39;m saying no you can also shift the normal numbers decimal numbers because if I convert this decimal number to a one1 I have to just make sure okay this entire thing is shifted left two times so I can entirely shift this left two times and that&#39;s how you simply do a left shift so you realized how important my left shift operator is and that is primarily used for making your mask and again if you look very closely what is happening in this left shift is that you are actually skipping a bit you are just skipping a bit and we remembered that every bit has a contribution of a factor of two so technically by doing a left shift you are multiplying that number by two right again don&#39;t do a ratification of it you remember that contribution of every V is a factor of two as I go on to next number I multiply by two next number multiply by that two you remembered one you remember 1 2 4 8 16 and so on and so forth so I remembered every contribution of a bit is a fact multiplied by two it is multiplied by two so I know if I do a left shift I&#39;m actually skipping a bit and going on to the next bit which means I&#39;m actually skipping a factor of two so just simply make sure to multiply that by two and you can also see by example as I can see I shift left shift of one one time I multiply that by two I left shift of one two times I multiply that by two two times 1 into two into two I got a four same way I I have done one left shift three I would have got a eight same way for every other number also now if we are studying left shift let&#39;s also see right shift it is again although it is not that much used because left shift is primarily used in making mask and then operating on those mask right shift is not that much used it is ideally again this operation or this use case of right shift you will again see in the practice problem list which I have given because you remember that I had a integer representation of a 32 bits so I can simply place my numbers in those 32 bits I can use those places for placing two numbers also this this problem you will see in the practice problem playlist which means this will help you understand the use case of your right shift this is very important also not that much not directly used but applied in problems now same way as that of left shift right shift simply says that if you have a number let&#39;s say five I have taken in this case I just simply shift this right if I shift something right okay I know that this is the zeroth bit this is the first bit if I&#39;m shifting it right where this will one go it has no space it is the same V saying I am standing at a bench I&#39;m sitting on the left soorry extreme right someone says me shift right I will go down go down lost down lost so as soon as something is Shifting right it is going down and getting lost so same way if this thing wants to shift right it will get lost same way it will also get lost so this will become your zeroth bit so this is how your right shift twice will work same way as you can simply see I will have value of one same way saying right shift will divide the number by two so I have five one time I did a right shift I got a two another time I do a right shift I got a one that is the reason I got a one so left shift will actually go on to and shift the bit to the left side and we multiply the number by one right shift we&#39;ll shift the bit to the right side and multiply the number by sorry divide the number by two okay these things are done and we also learned that how easily we can flip a bit and that is done by zor operation but flipping a bit as in okay it&#39;s a one will become a zero if it&#39;s a zero it will become one but what if I primarily wanted okay no matter what if it&#39;s a one or a zero make it a one or if it&#39;s a zero one make it a zero so this is called as a set the specific bit or unset the specific bit again as soon as I&#39;m talking about a specific bit I know one thing for sure that my mask will come in picture right and this set and unset word we had already seen in the very beginning I told you set means okay the bit value is one unset means the bit value is zero and I&#39;m saying no matter what I&#39;m saying no matter what even if the bit value at that location is a zero or one no matter what it should become a one if I do a set if I do a unset no matter values of Z or one I should make it a zero no matter what so if I am saying that okay set a specific bit I have given a mask to you okay make the I get bit as set so I know that I&#39;ll do a one left shift I to make a mask of one on the I location so for sure I know that I will simply make a mask at the I location which means one is there and rest all for sure will be a zero now I have to make sure whatsoever my n value is this location again let&#39;s represent the any arbitrary in value let&#39;s say 1 0 1 1 1 0 0 I want to specifically set this what do you think what operation I should apply operation remember the and or or these are the only operation which we have in picture that&#39;s it that&#39;s it so if I want again I&#39;m saying anything it can be one here it can be zero here anything whatsoever it should become a one simply it is a r operation because one is fixed so if you go back to the or operation which you learned you see that one is fixed if you have one on one of the sides you will simply get a one for sure as a result so I realize that I can simply apply a simple or operation so I do n or this is a or one left shift I which is a mask I will simply set the I bit as one an example you can see in front of your eyes n was let&#39;s say five which is 101 I want to set the third bit I do a one left shift three my one is left shifted three times I will simply set this bit again make sure all the other bits remain untouched intact that&#39;s set and this bit will set for sure even if it would have been a one it will still have got set same way if I want to unset if I want to to unset the bit which means again I&#39;ll take the same example let&#39;s say if I have an n and I want to unset the specific bit answer this bit I know technically my mask will make a one 0 0 0 0 even if I do a and operation for sure or operation will will not even work because what if it&#39;s a zero I want to unset the bit or operation will set the bit I I don&#39;t want that can I apply a zor operation if I do apply a zor if it&#39;s a zero my mask will have a one I will make it a one I also don&#39;t want that okay how about and operation seems like seems nice that because zero and one will will will be a zero Set uh but what if what if if this would have been a one one and one will be a one H you ideally wanted to actually make this number as zero no matter what if even if it&#39;s a zero make a zero even if it&#39;s a one make a zero but unset the specific bit but my mask says a one ideally I should place and instead of this one what if I actually do one thing what what if I have a zero here and rest all are one so I inverted my mask I flipped my entire mask if you remembered not operation is the one which flip the entire entire stuff so I&#39;ll do a simple not operation which will flip the entire stuff now I have got a zero here if you remembered and operation is the one that no matter what you do if you have a zero in the end you will for sure get a zero value and because of these all are ones so other values will remain untouched these will remain intact of what n had provided me and this will for sure turn to zero and that&#39;s how I simply by using and and not I&#39;ll simply get and can unset my specific I bit make sure these are very important Concepts and these are the most used ones now you have flipped the bit flipped the I bit you have unset the I bit you have set the I bit but what about you have to check if some specific ath bit is set or not because it might be important that you have to check if that bit is sit but Aran why would I need that even in future because as I told you in the very beginning I can have given you a I could have given you a string which means a b c d e let&#39;s say I represent this string in a form of a binary number so I would represented okay let&#39;s say I have a a b d okay let&#39;s say I have a a e so I I would have represent this represent that as a 0 one okay it&#39;s a zero bit it&#39;s a first bit it&#39;s a second bit it&#39;s a third bit it&#39;s a fourth bit so a is there b is there C is not there D is not there e is there so I would have represented this string in as a form of one integer and let&#39;s say if I ask you I want to know do I have a D in this string I will simply check if the ith bit is set or not that is the use case where your set or unset bit checking that will be required again this exact same problem you can see in the practice problem medium playlist like medium problems in which what I have given in the comment in the description below now coming on back we can simply see we have to check if the I bit is set or not simply we&#39;ll take the exact same example where n is five five 1 1 I want to check let&#39;s say if my second bit second bit which means 0 1 2 if this second bit is set or not I have to check that make sure always when you have to work on a specific bit make a mask of it first so I&#39;ll firstly make a mask of it which means one left shift I which means one left shift two times I want to check the second bit so I simply got a one and rest all a zero now I want to check if that bit is set or not right set or not what is the operation which you should make sure you should apply it what if I apply a or operation then what I will get no matter if it&#39;s a zero or one I will for sure get a one it&#39;s it&#39;s it&#39;s it&#39;s not good for me what if I apply and operation I will get a one here only if this location is a one if this is a zero I&#39;ll get a zero here so if I apply and operation if I apply and operation I will get the exact same bit on this location but R what about the other bits other bits as you can see all the other bits are here zero so and of anything with a zero will for sure be zero so other bits will all be zero and this bit I bit will only B one provided this I bit is one on in the number five and this is my actual main Crux how I will simply use this ith bit I simply use I bit to determine if this number I have got is a nonzero number which means for sure again why nonzero Aran because this bit can be set at any location it can be one here also so if I convert that to a number it can be any different number any non zero number I&#39;m specifically focusing on a zero is because of the reason if the bit is zero in my n equal 5 then for sure as as as I told you this will become a zero and rest all will for sure be zero because of the and operation which I&#39;m doing all right thus the entire number is zero so if the entire number is a zero then the bit was unset if the number is non zero then the bit was set and this is a entire C that you will simply do a n and operation with the mass which is one left shift I if this value is equal to zero which means the bit is not set if it is not zero it is set and that&#39;s how you simply you can achieve your answer now now comes that okay if we slightly use these stuff which we have studied left shift right shift mask which are very important concept and and the only concept which you need for bet manipulation problems comes is next important Point finding the rightmost bit or removing the rightmost bit but Arian it is a problem rather than concept right so why should I study it like I can just solve the problem for it like it&#39;s a problem right although technically makes sense it&#39;s a problem and you can simply solve it by making mask and stuff which I&#39;ve already told you earlier but what is so so special about it is it is directly like hands on like put it like this used in another algorithms one of them being F victories and not only this but also directly use in another famously known problems for example power of two or maybe another number in that you just have to remove the last set bit again removing the last set bit is the same way I&#39;m saying flip the last set bit if I flip a set bit it will become a zero which means removing that last set bit so this is very very very important that you specifically focus on the last bit again when I say last I mean okay if it&#39;s a number 1 0 1 0 1 1 0 0 so last set bit this is the last set bit for me right last set bit for me I have to work upon it I have to Simply remove it make it a zero this is very special and you will see why it is so special it will actually help you solving many problems and many tricks you&#39;ll get know by this so one I I I&#39;ll tell you two ways to get or to basically remove the last set bit or basically to flip the last set bit I&#39;ll two two very important ways one of the ways again both have their importance in bit manipulation one of the Bas is again R why you have taken id id and stuff because this exact same stuff we have already taught on our in our bit manipulation crash course that in bit manipulation the prime thing is actually using your numbers and getting a value out in that you use the id id as an index it&#39;s the same we have taken the exact same stuff that if you have this number called as ID and you have to remove this last bit this last again for you this is the last set bit and you have to just simply remove it remove it as in make it a zero make it a zero so what you will do you will simply grab this ID which is 0111 you know that you have to flip this bit so ideally this bit should be this bit should be gone now you have to get something that this bit this bit is remaining and like others are actually like so this bit is gone and other are remaining so I did a minus of ID what is this minus minus is nothing but two&#39;s complement if you remember in the very beginning I showed you if you have a decimal number if you want to do a minus of that some firstly flip the bits I have a 011 I&#39;ll flip the bits I&#39;ll get a 1 0 0 0 then I add a plus one this plus one is the two&#39;s complement so this is one&#39;s complement plus one is the two&#39;s complement so this is the two&#39;s complement of a number which is negative of a number I&#39;ll simply get a 1 1 now on this one1 I will simply apply a and how this will help me this will help me in simply saying bro get this a one get this get this a one simply get the mask of the rightmost set bit but in if I want to achieve a mask I can simply achieve by iterating on this entire number from the right side yes you can do it but if you know that this operation which you do which you did here I D and minus ID it&#39;s a o of one operation exactly of one but if you go on and search for this number from right to left for the first bit which is set it will take at Max o of 64 time o of 64 time although it also constant but still this is higher than actually constant o of one operation cool that&#39;s the reason this I have got a mask which is having the extreme rightmost set bit right and now I have to Simply make sure I simply remove this from my existing number ID from the existing number ID I&#39;ll simply remove this mask simply subtract this number one I&#39;ll simply get a zero at that last set bit location and the other numbers remain intact as it is so I simply did flip the bits this one more strategy of flipping that last set bit and again I&#39;m showing both of them because both have the importance the above one I showed you has importance in Fen victores because we have told that exactly same in Fen victores you can use other strategies also but it&#39;s good to know that how these are linked to each other and that&#39;s the only one right this is the only course which you need for all the problems of a b manipulation that&#39;s so good right yeah the strategy says get a number again you have to make sure you have to remove this last set bit if I look back closely to my previous number which is n minus one I will look that okay everything remains same in that the last set bit is actually unset so what I can do is I can do and operation with my previous number and I will make sure I will unset the last set bit but then you will have a question Arian then why can&#39;t I simply take my previous number okay I did a n and n minus one I got a 1 0 1 1 0 0 which means this bit was unset because of the previous mask technically why can&#39;t I simply take this number 12 okay if you say that then simply look at this example 12 and 11 so if you say that for 12 you&#39;ll take 11 that&#39;s obviously wrong because you wanted to remove this specific one right so it is the reason you will do 12 and 11 12 and 11 which means n and n minus one how it will help you it will help you by saying that this is the bit which will get unset I will simply unset my last set bit because you can see this is the last bit which is set and I will simply unset this bit and get the answer awesome right yes make sure we D on this part also okay N is8 I will just check from the last number and then last number is seven I do add this is okay I had only one set bit and that set bit I have simply removed so number becomes a zero and this is a very great point we should which you should remember what&#39;s the point you always remember that if I have one in the binary representation they are the contribution the factors of two right so one if I have a one in the very beginning let&#39;s say 0 0 0 0 1 this is one if I have a 0 1 this is two 1 0 it&#39;s a four it&#39;s a eight it&#39;s a 16 so for the powers of two we realize we will have only one set bit so anyhow if I want to figure out any power of two if I have a number and I want to figure out if that number is a power of two or not then I can simply say that if n and n minus one if it is equal to zero then for sure it had only one set bit which means it&#39;s is a power of two else it is not and that is the beauty of this now this is the entire stuff which you should know make sure you very well know how to make a mask how to set and set the bit how to flip the bits how to know that I bit is set or not and especially make sure you always remember these three strategies of and or and zor and never forget this entire Crux now make sure that you will go and practice all these problems every problems have a specific thing which they going to teach you so make sure you practice them because see I have written what this going to teach you what this going to teach you so everything has a significance now go and rock bye-bye if you like this video if you want other crash course to be coming in just comment down below which other crash course you want we will focus only on the specific tricks and stuff which will help you to solve any problem whatsoever this is one stop video for your any issue on bit manipulation and do make sure to join the Discord Channel and also see the comment section below bye-bye take care

Transcript for:Bit Manipulation Crash Course

Transcript for:
Bit Manipulation Crash Course