This content originally appeared on DEV Community and was authored by Bernice Waweru
Instructions
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Approach
We cannot use arithmetic operators, so we have to use bit manipulation to achieve addition.
The XOR operator is useful for bit manipulation where its output is shown below.
From the code above we observe that 1^1=0 which is not equal to 1+1. We can use the AND(&) operator to handle carry to calculate the correct answer. We shift the carry to the left and repeat the operations until we get a result of 0 meaning there are no more carries.
Here is an example:
Python Implementation
def getSum(self, a: int, b: int) -> int:
while (b != 0):
carry = a & b
a = a ^ b
b = carry << 1
return a
The time complexity is 0(n).
The solution is sufficient for most scenarios but we can improve it by consider that the range of bits for representing a value is not 32 in Python.
Therefore, we have to use a 32 bit mask of 1's represented by 0xfffffff.
The mask expands a number into a 32 bit / unsigned integer.
Our solution becomes:
def getSum(self, a: int, b: int) -> int:
mask = 0xffffffff
while (b & mask) > 0:
carry = (a & b) << 1
a = (a ^ b)
b = carry
return (a & mask) if b > 0 else a
Approach 2
We can use logarithms to achieve the same result.
From our knowledge of logarithms, we know that
def getSum(self, a: int, b: int) -> int:
return int(math.log2(pow(2,a)*pow(2,b)))
Useful Link
This content originally appeared on DEV Community and was authored by Bernice Waweru
Bernice Waweru | Sciencx (2022-02-18T16:38:33+00:00) Sum of Two Integers. Retrieved from https://www.scien.cx/2022/02/18/sum-of-two-integers/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.