XOR Multiplication – The Daily Programmer #315


Hey Frico Camp and welcome to another the daily program or webseries video and in this one We’re going to talk about problem number 315 XOR Multiplication which is posted on the daily program or subreddit and then before we dive into this problem remember to brush up on your bitwise? Operations because we’re going to be using them in a solution come time to implement in Javascript, all right So let’s break it down the whiteboard So for this xor multiplication example. They give you two inputs right They give you an input A in this case is the integer 14 and then they give you input B? Which is another integer in this case It’s 13 And then the base two equivalents of these two integers would be 1 1 1 0 for 14 and 1 1 0 1 for 13 so given this information their whole xor multiplication is defined like so for every bit an Input b. Or in this case the bottom number 13 We need to write out input A if the bit is 1 so in this case the first bit on the right is a 1 So we’re going to go ahead and write out input A and Then we’ve taken care of that bit so we can cross it up and then for the next part of the multiplication you just go ahead and indent 1 so I’ll go ahead an indent 1 here and Then if it’s a 0 for this bit on the far right that you’ve moved in 1 on we just go ahead and write a 0 here and then repeat the process where you indent one more time and In this case we’re at a 1 so we need to rewrite this 14 out so I can say 0 1 1 1 and Again, if it is a very last bit We need to end it a third time and write out 0 1 1 1 and Now at this point. You can just do an xor operation on all the ones beforehand so in this case if you xor 1 1 1 0 1 0 you get 1 1 1 0 so I can go ahead and write that out here and You get x or this line with this line you’re going to go ahead and get 1 1 0 1 1 0 and I’ll ask you the x for this line with this line you’re going to go ahead and get one zero zero zero One one zero Which will actually convert to the integer of seventy? So just to make sure that was kind of odd because I still can walk through it one last time so I’ll go ahead erase this and I’ll rewrite this bottom string so remember the algorithm that they’re presenting to you is That for every bit in 13 starting from the right you need to write out the top one If it’s a 1 and then indent for every bit, so let’s do this One by one so again we’ll cross that the one will write out and put a which is 14 so then we get to the next bit zero and then we have to indent one so let’s go ahead and set a to zero here and Then we can xor these which leaves us with one one one zero We can cross out this bit Which leaves us two indentations? And because the first one this is the second one and then write out input eggs x where those together and we get one one zero one one zero and It’s finally we cross that this bitch. We end in three right out input a and then xor them all together Which again leaves us with one zero zero zero one one zero which equates to 70? So again for this problem they basically broke down the algorithm that we need to implement and The only thing we need to do is just let galva Script and implement it. So let’s go ahead and do that now, okay? So to start off let’s go ahead and make a function called x or multiply We’re going to take two parameters and be like we discussed on the whiteboard and down here let’s just go ahead and call it with 14 and 13 the same values that we did on the board and Then we can just go ahead and return null here so the first thing I’m gonna do is I’m going to declare a results variable where we can keep track of The results when we keep x soaring a to a shifted to a shifted ETC, and then I could just say return results down here so that function should make sense and The first thing that we mentioned in the white board is that we want to keep looping over b Until We run out of bits or run out of those you know digits 1 to 0? so we can say While b is not equal to 0 We can just go ahead and keep shifting off bits So if you know anything about bitwise operations when you do this operation, we’re pretty much saying take the integer B Take its base to representation and shift a bit off to the right so if it was 1 1 0 1 it will now become 1 1 0 and then 1 1 and then 1 and we can actually show this if I also go ahead and say console.log beat out 2 string Base 2 And C console is not defined, so it prints out Again the first iteration the first thing and loop is going to print out 1 1 0 1 and Then it prints out 1 1 0 and then it prints out 1 1 1 and then 1 So it’s going to be four times and then one time for every character right until we reach 0 so hopefully this part makes sense and then again to Demonstrate the other part you know step two of that algorithm is every time you do an iteration you need to shift a over to the left one so you need to add a zero to a And what we can do is the opposite we can say a less than less than equal one which Is again a bitwise operation which will push the integer a of the base to representation over one so again I can say console.log a two strings a base two and We see each iteration. It adds a zero to the end so now for the last part remember all we do all we have to do is just take a result and keep x oaring it with a if the bit of B on the far right is equal to one so I can say result x or equals a Which won’t necessarily give us which our site results? So that won’t give us the answer that we’re looking for because we need to only x or when the rightmost right bit of b is equal to 1 so we can times it by B and then check if the right bit is on and we get our final answer of 70 down here. I Was going to print out this two string So again we can kind of walk through this and get a better understanding what’s going on. So the first iteration B is 1 1 0 1 and a is 1 1 1 0 and then we need 2 times 1 1 1 0 By the first bit and B, and it’s 1 in this case the result it becomes 1 1 1 0 and then the way We’re going to shift over a shift over b the loop goes on One more where b is equal to 1 1 0 a now has an extra 0 at the end and Again, we check if the most far-right bit is on for B. And if it is we just xor results with a again Which leaves us with the exact same results down here? So you see that results for the first iteration is 1 1 1 0 second iteration is also 1 1 1 0 and then for the third iteration B is equal to 1 1 the most right bits on so therefore we xor results with 1 1 1 0 which is a And we’re left with this and then we again repeat it for the last one Again be sure to like the video. We thought it was good and be sure to subscribe to Frito Camp below alright. Thanks for watching

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *