You are probably interested in this post because it touches two complicated areas of programming, Bit Manipulations &Recursion. Indeed it does. I will dig deep into these. Bear with my speed and be patient, you will get it. The best way would be to take a problem and follow through it. There are chances that you might have already heard about this problem but I will try to follow an approach which hopefully will highlight some new things about the problem.
So first the problem. Lets say your friend comes to you and puts a challenge across, Programming Interviews: Implement adding two unsigned numbers without using "+" or "++"?. You being a problem solver, accept the challenge & try to work on a solution. You think, Is there a possibility that by using any in-built operators other then '+', you will be able to solve this? Probably. So you try various operator '-', '*', '%' etc. You put all your effort into it but solution remains elusive. You think that there is no harm in asking for help to get some pointers. Absolutely, no harm. You approach another nerdy friend to get some help on the problem. After seeing the problem, what do you think would be his first response? Think... Well, it is highly likely (if he is a nerd) that he will ask you this question, "Can you try bit operators?". It looks like your friend has taken quite a journey. He asked you this question because he thinks that if a in-built language operator is not an option, can we do what computer itself would be doing? Use bit operators.
So you get a cue. You have some basic idea about bit manipulation. You start working on the program using bit operations. You look at bit array associated with two numbers which need to be added & do some mental wrestling:
19 = 10011
29 = 11101
Since you are aware of bit operations, what is the first thing which crosses your mind? Take a moment & think. May be, you look at the whole binary representation of each number & think that adding bits is simple but how to handle carry from right to left? If you considered the ENTIRE string and thought about moving carry across, there is a problem. The issue is that you are not breaking problem into smaller sub problems. What instead you should have done is this (the last one is important):
Case-1: Case-2: Case-3: Case-3:
0 0 1 1
0 1 0 1
= = = =
0 1 1 0
I know you might be thinking that, "hold on, this is not different from what I thought". In fact, it is not THAT different but with a caveat. The above cases don't worry about carry. We will see how this will help. So lets say, you took my advice and only cared about adding bits without carry, you will obviously write below statement with XOR to get it:
19 = 10011
29 = 11101
---------------------
19 ^ 29 = 01110 (14)
I know you are not willing to give up your take on carry, so lets now consider the cases associated with carry.
Case-1: Case-2: Case-3: Case-3:
0 0 1 1
0 1 0 1
= = = =
0 0 0 1
Considering the above cases, you will write below statement to get it:
19 = 10011
29 = 11101
---------------------
19 & 29 = 10001 (17)
Look carefully at above results & think. You have to look at both results otherwise you will not get it, so take a look again. OK, so probably you will ask yourself, what if we could just move, the 1s in (19 & 29) to the left, then carry would be in right position. So you might try this, a & b << 1 since you are aware of shifting bits. As you can see from the result, this works great, carry moves exactly at the position where it should be.
19 = 10011
29 = 11101
-------------------------
(19 & 29) << 1 = 100010 (34)
Wonderful! Now the first thought might be to combine the non-carry and only carry binary representations. So you write both together and look at it. For simplicity, we call 14, number without carry & 34 as carry. Here you go:
19 ^ 29 = 01110 (14 - number without carry)
(19 & 29) << 1 = 100010 (34 - carry)
What do you see? Well, you readily identify the problem. You see that there are two 1s at second position from left and you have to deal with carry again. What are your thoughts now? Think about it for a moment! You might feel that you have hit a roadblock. But some optimistic programmer will see it as a win and will tell you that this is nothing but the same problem which you have already solved earlier, isn't it? You see it now. So you try to repeat the same process, which you did above, again:
14 ^ 34 = 101100 (44 - number without carry)
(14 & 34) << 1 = 100 (4 - carry)
Since you have already found, that this is the same problem again, you realize that you will need to repeat the calculation again. So here you are:
44 ^ 4 = 101000 (40 - number without carry)
(44 & 4) << 1 = 1000 (8 - carry)
You do it couple of times more until the tension of carry vaporizes:
40 ^ 8 = 100000 (32 - number without carry)
(40 & 8) << 1 = 10000 (16 - carry)
32 ^ 16 = 110000 (48 - number without carry)
(32 & 16) << 1 = 0 (0 - carry)
Finally, you got rid of carry. What next? Nothing, we are done. Yes. Recall we had 19 and 29, so 19+29=48. Congrats!! You have solved a complex problem. Great!!
Look carefully, you used recursion to solve the problem. Recursion is a very simple technical concept but is extremely hard to apply while solving a problem. If you get it, you can solve any hard problem, really. I guess you might have heard about dynamic programming. It is nothing but trying to solve small problems using recursion to reach to the final solution while keeping track of what you solved so that you don't repeat yourself (Memoization, to be precise). That's why it is often called optimization over backtracking. Anyways, I was trying to convince you that for learning high level programming concepts like dynamic programming, you have to think recursively. That sounds simple, isn't it? In fact, it is that simple. Ok enough, lets return back to the problem at hand & formally write the solution. It should be amazingly simple now:
So first the problem. Lets say your friend comes to you and puts a challenge across, Programming Interviews: Implement adding two unsigned numbers without using "+" or "++"?. You being a problem solver, accept the challenge & try to work on a solution. You think, Is there a possibility that by using any in-built operators other then '+', you will be able to solve this? Probably. So you try various operator '-', '*', '%' etc. You put all your effort into it but solution remains elusive. You think that there is no harm in asking for help to get some pointers. Absolutely, no harm. You approach another nerdy friend to get some help on the problem. After seeing the problem, what do you think would be his first response? Think... Well, it is highly likely (if he is a nerd) that he will ask you this question, "Can you try bit operators?". It looks like your friend has taken quite a journey. He asked you this question because he thinks that if a in-built language operator is not an option, can we do what computer itself would be doing? Use bit operators.
So you get a cue. You have some basic idea about bit manipulation. You start working on the program using bit operations. You look at bit array associated with two numbers which need to be added & do some mental wrestling:
19 = 10011
29 = 11101
Since you are aware of bit operations, what is the first thing which crosses your mind? Take a moment & think. May be, you look at the whole binary representation of each number & think that adding bits is simple but how to handle carry from right to left? If you considered the ENTIRE string and thought about moving carry across, there is a problem. The issue is that you are not breaking problem into smaller sub problems. What instead you should have done is this (the last one is important):
Case-1: Case-2: Case-3: Case-3:
0 0 1 1
0 1 0 1
= = = =
0 1 1 0
I know you might be thinking that, "hold on, this is not different from what I thought". In fact, it is not THAT different but with a caveat. The above cases don't worry about carry. We will see how this will help. So lets say, you took my advice and only cared about adding bits without carry, you will obviously write below statement with XOR to get it:
19 = 10011
29 = 11101
---------------------
19 ^ 29 = 01110 (14)
I know you are not willing to give up your take on carry, so lets now consider the cases associated with carry.
Case-1: Case-2: Case-3: Case-3:
0 0 1 1
0 1 0 1
= = = =
0 0 0 1
Considering the above cases, you will write below statement to get it:
19 = 10011
29 = 11101
---------------------
19 & 29 = 10001 (17)
Look carefully at above results & think. You have to look at both results otherwise you will not get it, so take a look again. OK, so probably you will ask yourself, what if we could just move, the 1s in (19 & 29) to the left, then carry would be in right position. So you might try this, a & b << 1 since you are aware of shifting bits. As you can see from the result, this works great, carry moves exactly at the position where it should be.
19 = 10011
29 = 11101
-------------------------
(19 & 29) << 1 = 100010 (34)
Wonderful! Now the first thought might be to combine the non-carry and only carry binary representations. So you write both together and look at it. For simplicity, we call 14, number without carry & 34 as carry. Here you go:
19 ^ 29 = 01110 (14 - number without carry)
(19 & 29) << 1 = 100010 (34 - carry)
What do you see? Well, you readily identify the problem. You see that there are two 1s at second position from left and you have to deal with carry again. What are your thoughts now? Think about it for a moment! You might feel that you have hit a roadblock. But some optimistic programmer will see it as a win and will tell you that this is nothing but the same problem which you have already solved earlier, isn't it? You see it now. So you try to repeat the same process, which you did above, again:
14 ^ 34 = 101100 (44 - number without carry)
(14 & 34) << 1 = 100 (4 - carry)
Since you have already found, that this is the same problem again, you realize that you will need to repeat the calculation again. So here you are:
44 ^ 4 = 101000 (40 - number without carry)
(44 & 4) << 1 = 1000 (8 - carry)
You do it couple of times more until the tension of carry vaporizes:
40 ^ 8 = 100000 (32 - number without carry)
(40 & 8) << 1 = 10000 (16 - carry)
32 ^ 16 = 110000 (48 - number without carry)
(32 & 16) << 1 = 0 (0 - carry)
Finally, you got rid of carry. What next? Nothing, we are done. Yes. Recall we had 19 and 29, so 19+29=48. Congrats!! You have solved a complex problem. Great!!
Look carefully, you used recursion to solve the problem. Recursion is a very simple technical concept but is extremely hard to apply while solving a problem. If you get it, you can solve any hard problem, really. I guess you might have heard about dynamic programming. It is nothing but trying to solve small problems using recursion to reach to the final solution while keeping track of what you solved so that you don't repeat yourself (Memoization, to be precise). That's why it is often called optimization over backtracking. Anyways, I was trying to convince you that for learning high level programming concepts like dynamic programming, you have to think recursively. That sounds simple, isn't it? In fact, it is that simple. Ok enough, lets return back to the problem at hand & formally write the solution. It should be amazingly simple now:
public int sum(int num1, int num2) {
if (num2 == 0) {
return num1;
}
int numWithoutCarry = num1 ^ num2;
int carry = (num1 & num2) << 1;
return sum(numWithoutCarry, carry);
} I hope you are able to see the power of recursion here. Whenever you encounter a problem which seems pretty similar to what you have solved earlier, recursion is the way to go. I agree, its hard to apply in practice but you have to practice hard to master something, isn't it? Some structures like tree, graphs are inherently recursive so unless you get how to think recursively, you will find it hard to dig deep. Recursion helps you break a problem into smaller pieces and solve those recursively. That's the beauty of it. So think recursively!!
Credits : Pawan Bhadauria
Post A Comment:
0 comments:
Post a Comment