This approach imitates the addition mechanism in digital circuits using bitwise operations. The key operations involved are:
Time Complexity: O(n), where n is the number of bits needed to represent the numbers.
Space Complexity: O(1), constant space usage.
1public class Main {
2 public static int getSum(int a, int b) {
3 while (b != 0) {
4 int carry = a & b;
5 a = a ^ b;
6 b = carry << 1;
7 }
8 return a;
9 }
10
11 public static void main(String[] args) {
12 System.out.println(getSum(1, 2));
13 }
14}The Java implementation follows the same process: determine carry with a & b, determine interim sum with a ^ b, and update carry by shifting it left. This continues until there are no more carries left.
This approach is an extension of the iterative bitwise method but uses recursive calls to achieve the result. Instead of using a loop, it relies on recursive function calls to process the sum and carry until the carry becomes zero.
Time Complexity: O(n), where n is the number of bits.
Space Complexity: O(n), due to the recursive call stack.
1#include <stdio.h>
2
3int getSum(int a, int b) {
4 if (b == 0) return a;
5 int sum = a ^ b;
6 int carry = (a & b) << 1;
7 return getSum(sum, carry);
8}
9
10int main() {
11 int a = 1, b = 2;
12 printf("%d", getSum(a, b));
13 return 0;
14}In this C solution, the base case for the recursion is when b (carry) becomes zero, at which point a contains the result. sum is calculated using XOR and carry is calculated and shifted. These new values are passed in the next recursive call.