Given bit strings, perform a bitwise addition

Question

I'm looking for code-review, optimizations and best practices. This code is a Java adaptation of code on geeksforgeeks.org. Please verify if space complexity is \$O(n)\$ where n is number of bits, and aux complexity is \$O(1)\,ドル since no temporary space was needed. Whatever space was needed was used for return value not for temporary purpose. Rectify my understanding of space and aux complexity if wrong.

public class AddBinaryStrings {
 public static String addBinaryStrings(String num1, String num2) {
 final StringBuilder sum = new StringBuilder(Math.max(num1.length(), num2.length()) + 1);
 String shortNum;
 String longNum;
 if (num1.length() < num2.length()) {
 shortNum = num1;
 longNum = num2;
 } else {
 shortNum = num2;
 longNum = num1;
 }
 int carry = 0;
 int i = longNum.length() - 1;
 int j = shortNum.length() - 1;
 for (; j >= 0; j--, i--) {
 int num1Digit = longNum.charAt(i) - '0';
 int num2Digit = shortNum.charAt(j) - '0';
 sum.append(num1Digit ^ num2Digit ^ carry);
 carry = (num1Digit & num2Digit) | (num1Digit & carry) | (num2Digit & carry);
 }
 for (; i >= 0; i--) {
 int num1Digit = longNum.charAt(i) - '0';
 sum.append(num1Digit ^ carry);
 carry = num1Digit & carry;
 }
 if (carry == 1) {
 sum.append(1);
 }
 return sum.reverse().toString();
 }
}
public class AddBinaryStringTest {
 @Test
 public void testCarry() {
 assertEquals("1000" , AddBinaryStrings.addBinaryStrings("101","11"));
 }
 @Test
 public void testNoCarry() {
 assertEquals("1101", AddBinaryStrings.addBinaryStrings("1000", "101"));
 }
}

• 200_success: Is there anything preventing you from writing new BigInteger(num1, 2).add(new BigInteger(num2, 2)).toString(2)?
• maaartinus: @200_success Maybe the "O(1) aux complexity" as your BigInteger needs some space? However, the StringBuilder needs some additional memory, too, and it needs surely more than the BigIntegers. The OP's claim "Whatever space was needed was used for return value not for temporary purpose" is wrong, the return value is the String.

Answer 1

Please verify if space complexity is O(n) where n is number of bits, and aux complexity is O(1), since no temporary space was needed. Whatever space was needed was used for return value not for temporary purpose. Rectify my understanding of space and aux complexity if wrong.

Wrong.

Let's use another example. Bubble-sort uses \$O(1)\$ auxiliary space complexity. Bubble-sort does an "in-place sort", it does not require additional space except for a single temp variable.

Auxiliary means "helper". In the case of your code, the "helper" is the return value. The auxiliary space complexity of your code is \$O(n)\$.

Also remember this line:

return sum.reverse().toString();

How could you possibly reverse a string without storing the string in the first place? The space required to store this String is \$O(n)\$

There is an article on Geeks for Geeks explaining this and a question on Stack Overflow about it.

Auxiliary space ignores the size of the input, not the output.

Answer 2

The sequence of

 sum.append(num1Digit ^ num2Digit ^ carry);
 carry = (num1Digit & num2Digit) | (num1Digit & carry) | (num2Digit & carry);

is absolutely correct; the typical bit adder works (almost) exactly like this. You are in a position to enjoy a high level language constructs. They are equally fast yet much more expressive:

 bitSum = num1Digit + num2Digit + carry;
 sum.append(result % 2);
 carry = result / 2;

Your complexity estimates seem correct (I have no idea what you mean by aux complexity). Reassignment of strings may affect the coefficient, but the asymptotics remains linear, both space- and time-wise.

• Simon Forsberg: The complexity estimates are not correct to my knowledge, see my answer.