67 add binary

---

title: Add Binary
tags:
- add-binary
- No.67
- simple
- boolean-algebra

---

Problem

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"

Corner Cases

• carry digit

Solutions

Boolean Algebra

By adding binary in String, we can avoid the annoying complement and int range problem. We only need to consider the two digits x, y, and carry c from last digit. The truth table is:

x	y	c	s	c_
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

The sum of minterms can be drawn from truth table:

s  = (!x && !y && c) || (!x &&  y && !c) || ( x && !y && !c) || ( x &&  y &&  c);
c_ = (!x &&  y && c) || ( x && !y &&  c) || ( x &&  y && !c) || ( x &&  y &&  c);

Then we convert boolean values into strings. Be careful with different lengths and highest digit.

The running time is O(n).

class Solution {
    public String addBinary(String a, String b) {
        boolean c = false;
        String  t = "";
        
        String longOne  = (a.length() > b.length()) ? a : b;
        String shortOne = (a.length() > b.length()) ? b : a;
        int    ll       = longOne.length();
        int    sl       = shortOne.length();
        
        for (int i=sl-1; 0<=i; i--) {
            t = digit(shortOne.charAt(i), longOne.charAt(i+ll-sl), c).concat(t);
            c = carry(shortOne.charAt(i), longOne.charAt(i+ll-sl), c);
        }
        for (int i=ll-sl-1; 0<=i; i--) {
            t = digit('0', longOne.charAt(i), c).concat(t);
            c = carry('0', longOne.charAt(i), c);
        }
        if (c) {t = "1".concat(t);}
        
        return t;
    }
    
    private String digit(char aa, char bb, boolean c) {
        boolean x = (aa == '1');
        boolean y = (bb == '1');
        return (!x && !y && c) || (!x && y && !c) || (x && !y && !c) || (x && y && c) ? "1" : "0";
    }
    
    private boolean carry(char aa, char bb, boolean c) {
        boolean x = (aa == '1');
        boolean y = (bb == '1');
        return (!x && y && c) || (x && !y && c) || (x && y && !c) || (x && y && c);
    }
}