Title description:

The original address

Given two binary strings, return their sum (in binary).

The input is a non-empty string containing only the digits 1 and 0.

The sample a

Input: a = "11", b = "1" output: "100"Copy the code

Example 2

Input: a = "1010", b = "1011" output: "10101"Copy the code

prompt

  • Each string consists only of the character '0' or '1'.
  • 1 <= a.length, b.length <=
    1 0 4 10^4
  • Strings that are not "0" have no leading zeros

Thought analysis

The first thing that comes to mind is the method one in the official problem solution: simulation, which is called vertical column, end alignment, bit by bit addition. In decimal calculation, we need to put ten into one; in binary we need to put two into one. I’m not going to write the process.

Then I looked at the solution of the problem. Most of them were bit operations, and it was the first time to contact bit operations. I drew several times on the small book before I could understand the whole process.

An operation

Example: A = “1010”, b = “1011”

  • Step 1: Complete the binary bits

    • a = "0000 1010".b = "0000 1011"

  • Step 2: A ^ b

    ^ Represents an xor operation. For binary, the result is 1 when two corresponding binary bits differ. It’s just addition without carrying.

  • Step 3: A & B

    The & represents the and operation. For binary, the result of that bit is 1 if both corresponding bits are 1, and 0 otherwise.

    The result is shifted one bit to the left (<<1) to get the carry.

  • Step 4: Update a ^ b calculated in step 2 to A, and update the carry calculated in Step 3 to B. Repeat step 2 and Step 3 until B is 0, indicating that there is no carry. The value of A is the answer.

ps:

a = 0000 1010, b = 0000 1011
a ^ b      = 0000 0001--> New A (a&B) <<1 = 0001 0100--> new b a ^ b =0001 0101--> New A (a&B) <<1 = 0000 0000--> New b b already for0A is the answer10101

Copy the code

AC code

class Solution {
    public String addBinary(String a, String b) {
        int x = Integer.parseInt(a,2);
        int y = Integer.parseInt(b,2);
        int ans = 0, carry = 0;
        while(y > 0) {
            ans =  x^y;
            carry = (x&y)<<1;
            x = ans;
            y = carry;
        }
        returnInteger.toBinaryString(x); }}Copy the code

conclusion

Bit operation, also need to brush a few more problems to find a feeling.

reference

State the problem solving

“Hand drawing diagram” bit operation, bit-by-bit addition, the combination of the two

[official problem solving method 2] : Do not use the addition bit operation