Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1" Output: "100"
Example 2:
Input: a = "1010", b = "1011" Output: "10101"
Constraints:
'0' or '1' characters.1 <= a.length, b.length <= 10^4"0" or doesn't contain any leading zero.
Description is taken from https://leetcode.com/problems/add-binary/.
#O(M+N) Time O(Max(M,N)) Spaceclass Solution: def addBinary(self, a: str, b: str) -> str: a, b = int(a, 2), int(b, 2) while b is not 0: answer = a ^ b carry = (a & b) << 1 a, b = answer, carry return bin(a)[2:]We can solve this question by using bit manipulation since we're processing a binary number.
Similarly, we could also have chosen to solve this question like the Add Strings Leetcode question.
To solve this question using bit manipulation, however, we will use XOR and AND logic gates.
The XOR logic gate will isolate the bits we need to carry to the next iteration, the AND gate will isolate the bits that we can sum which won't require any carry-over values.
We’ll first convert a and b to binary numbers, base two.
a, b = int(a, 2), int(b, 2)
We will then use a loop that will run while b is greater than zero, until this happens, we still have bits we need to carry to the next position.
while b is not 0:
We will then do our initial addition of the two binary numbers.
We will use an XOR gate to sum the bits in both numbers where only one of the bits in each position is one.
If both values aren’t equal to one, we won’t need to carry any values.
answer = a ^ b
After we get that calculation, we’ll then apply an AND gate to get the values we’ll need to carry.
These values will be where both bits at each position are one. Since we’re carrying the value, we’ll need to shift the value to the left so that we can add it to the answer within the next iteration.
carry = (a & b) << 1
At the end of each iteration, we'll set a to our running answer and b to our running carry.
We'll do this to keep track of our answer but also to see if we still need to carry any values or break from our loop.
a, b = answer, carry
Once there are no more values to carry, we will return the binary sum.
If for example, we had a sum of four and wanted to return bin(a), it would return 0b100.
To return everything from the second index onwards, we will use [2:].
return bin(a)[2:]
When it comes to binary questions, it is good to remember some of the logic gate tricks like XOR and AND operations.