Sum of Two Integers

Mark as Completed

Lesson

Write a function that takes in two integers, A and B, and returns their sum without using the plus or minus operators. Instead, you should use bitwise operators such as

xor

and

and

to manipulate the integers. If there is a carry value, it should be accounted for in the addition.

Walkthrough

To solve this problem, we will use bitwise operators instead of addition and subtraction operators. We will first handle the carry value if there is one, and then we will calculate the sum of the bits of number one and number two where at least one of the bits is not set. To handle the carry value, we will use a while loop to iterate until there's no more value to carry. We will create a variable called carry that will be number one with the bitwise and on number two to contain the common set bits of number one and number two. We will then calculate the sum of the bits of number one and number two by using bitwise xor where at least one of the bits is not set. We will assign the value of the carry left shifted by one to number two to account for the carry value.

function add(A, B) {
  while (B !== 0) {
    let carry = A & B;
    A = A ^ B;
    B = carry << 1;
  }
  return A;
}

Big O Complexity Analysis: The time complexity of this solution is O(log n), where n is the maximum number of bits of A and B. This is because the while loop iterates only log n times as each iteration reduces the number of set bits in B by one. The space complexity is O(1) as we only use constant extra space to store carry and the function parameters.

Previous Lesson Next Lesson