Given bit strings, perform a bitwise addition 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() &lt; 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 &gt;= 0; j--, i--) {
            int num1Digit = longNum.charAt(i) - '0';
            int num2Digit = shortNum.charAt(j) - '0';

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

        for (; i &gt;= 0; i--) {
            int num1Digit =  longNum.charAt(i) - '0';
            sum.append(num1Digit ^ carry);
            carry = num1Digit &amp; 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"));
    }

}
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.