This is the 23rd day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Given two binary strings, return their sum (in binary). The input is a non-empty string and contains only numbers1 和 0. The sample1: Enter: a ="11", b = "1"Output:"100"The sample2: Enter: a ="1010", b = "1011"Output:"10101"Tip: Each string consists of characters only'0' 或 '1'Composition.1 <= a.length, b.length <= 10^4String if not"0", they do not contain leading zeros. Source: LeetCode//leetcode-cn.com/problems/add-binaryCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. The simulation

The difficulty of adding two binary numbers is how to deal with the carry, if you don’t consider the space-time problem, write this problem slowly, as smooth as writing a story.

Align the ends and add up bit by bit

Since you want to add two characters from the end, you have to take into account the inconsistent length of the two characters, so the algorithm starts by finding the longest character, iterating over that character, and replenishes the shorter character with 0 if it has no value.

There are only three results when two binary numbers are added in decimal: 0, 1, and 2, so in the code we will discuss these three separately and consider the carry problem according to the variable step

At the end, if the step result is 1, then the string needs one more bit

public String addBinary(String a, String b) {
    String res = "";
    char[] longArr = null;
    char[] shortArr = null;
    if (a.length() > b.length()) {
        longArr = a.toCharArray();
        shortArr = b.toCharArray();
    } else {
        longArr = b.toCharArray();
        shortArr = a.toCharArray();
    }
    int step = 0;
    for (int i = longArr.length - 1; i >= 0; i--) {
        int m = Integer.valueOf(String.valueOf(longArr[i]));
        int n = 0;
        if (i - (longArr.length - shortArr.length) >= 0) {
            n = Integer.valueOf(String.valueOf(shortArr[i - (longArr.length - shortArr.length)]));
        }

        int mn = m + n;
        if (mn == 0) {
            res = (mn + step) + res;
            step = 0;
        } else if (mn == 1) {
            if (step == 0) {
                res = mn + res;
            } else {
                res = "0" + res;
                step = 1; }}else if (mn == 2) {
            res = step + res;
            step = 1; }}if (step == 0) {
        return res;
    } else {
        returnstep + res; }}Copy the code

The official solution is the same as mine, but the code is completely different

The carry operation is done directly by char’s bit operation.

So here’s the type char.

Java uses Unicode encoding, so char is 16 bits, whereas ASCII is 8 bits, and is included in the Unicode encoding with a range of (0 to 127).

Char is used for character operations

Char a = 'g' print(a + 1) print(a + 1) Char c = '0' //int = 48 char c = '1' //int = 49 We can also convert int to char by adding '0'Copy the code
StringBuilder res = new StringBuilder();
    int sum = 0;
    // reverse order traversal
    for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
        // If I or j is greater than 0, the maximum character length is not exceeded
        // - '0' is used to convert char to int
        sum += i >= 0 ? a.charAt(i) - '0' : 0;
        sum += j >= 0 ? b.charAt(j) - '0' : 0;
        // We can calculate the value of the current position
        res.append((char) (sum % 2 + '0'));
        // A division operation can be used to calculate the carry value
        sum /= 2;
    }
    // Indicates that there is a carry at the end, which needs to be added to the string
    if (sum > 0) {
        res.append("1");
    }
    // In reverse order
    return res.reverse().toString();
Copy the code

2. api

There are many apis for numerical computation in Java

Convert aa and BB to decimal first, and then sum to binary.

  • If the string exceeds 3333 bits, it cannot be converted to Integer
  • If the string is longer than 6565 bits, it cannot be converted to Long
  • If the string contains more than 500000001500000001 bits, it cannot be converted to BigInteger

This algorithm will report errors for large numbers

public String addBinary2(String a, String b) {
    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}
Copy the code

Error reporting example exceeding int length

So use BigInteger instead, but you need to guide the packet manually

public String addBinary3(String a, String b) {
    return new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2);
}
Copy the code