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.
1#include <iostream>
2
3int getSum(int a, int b) {
4 while (b != 0) {
5 unsigned carry = a & b;
6 a = a ^ b;
7 b = carry << 1;
8 }
9 return a;
10}
11
12int main() {
13 int a = 2, b = 3;
14 std::cout << getSum(a, b);
15 return 0;
16}Similar to the C solution, this code uses bitwise operations in a loop to achieve the sum of two integers without using '+' or '-'. a & b finds carry, a ^ b finds the sum without carry, and then shifts carry one bit to the left to proceed.
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.
1public class Main {
2 public static int getSum(int a, int b) {
3 if (b == 0) return a;
4 int sum = a ^ b;
5 int carry = (a & b) << 1;
6 return getSum(sum, carry);
7 }
8
9 public static void main(String[] args) {
10 System.out.println(getSum(1, 2));
11 }
12}The Java recursive implementation follows the pattern of calculating sum and carry and uses recursive method calls, returning the result when carry is zero.