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 <stdio.h>
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 = 1, b = 2;
14 printf("%d", getSum(a, b));
15 return 0;
16}The solution utilizes a while-loop that continues until there is no carry left. The carry is calculated as a & b, and the sum without carry is calculated via a ^ b. The carry is then shifted left by one position (as happens in binary addition) and added to 'b' for the next iteration until the carry becomes zero. Each iteration moves the carry one bit to the left (achieved by << 1), imitating the binary addition process.
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.
1function getSum(a, b) {
2 if (b === 0) return a;
3 return getSum(a ^ b, (a & b) << 1);
4}
5
6console.log(getSum(1, 2));JavaScript's solution employs recursion for bitwise addition: computing sum and carry with each call and stopping recursion when carry is zero.