LeetCode Js-67. Add Binary

Given two binary strings a and b, return their sum as a binary string.

給予兩個二進制字串(a & b)，回傳他們相加後的二進位字串。

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Solution:
1. 先了解二進位的規則。

(ex.如下 a + b = 2
  a   = 0001
  b   = 0001
a + b = 0010 //2^1 = 2

2. 我們可以了解到「1 + 1 = 2」。
3. 此時在「個位」的位置變成「0」，且在「十位」的位置加「1」，依序計算。

Code 1:

var addBinary = function(a, b) {
    let result = "", carry = 0
    for (let i = a.length - 1, j = b.length - 1; i >= 0 || j >= 0; i--, j--) {
        if(i >= 0) carry += Number(a[i])
        if(j >= 0) carry += Number(b[j])
        result = (carry & 1) + result //使用 & 來找出carry 和 1 相同的二進制
        carry >>= 1; //將carry的值右移
    }    
    return carry ? "1" + result : result 
    //carry = 1 => true => "1" + result
    //carry = 0 => false =>   result
};

FlowChart:
Example 1

step.1
i = a.length - 1 => 2 - 1 = 1 ; carry += 0 + 1 = 1
j = b.length - 1 => 1 - 1 = 0 ; carry += 1 + 1 = 2
result = carry & 1 + result => 2 & 1 + "" => "0" + "" = "0"
ex: carry & 1
   由 0010 => carry
   上 0001 =>   1
   往 ----
   下 0000
carry >>1 = 0010 => 0001

step.2
i = 1 - 1 = 0  ; carry += 2 + 0 = 2
j = 1 - 1 = -1 ; carry += 3 + -1 = 2
result = carry & 1 + result => 2 & 1 + "0" => "0" + "0" = "00"
ex: carry & 1
   由 0010 => carry
   上 0001 =>   1
   往 ----
   下 0000
carry >>1 = 0010 => 0001

step.3
return carry ? "1" + result : result
          1  ?  "1" + "00"  : "00"     
        true      "100"

Example 2

step.1
i = a.length - 1 => 4 - 1 = 3 ; carry += 0 + 0 = 0
j = b.length - 1 => 4 - 1 = 3 ; carry += 0 + 1 = 1
result = carry & 1 + result => 1 & 1 + "" => "1" + "" = "1"
ex: carry & 1
   由 0001 => carry
   上 0001 =>   1
   往 ----
   下 0001
carry >>1 = 0001 => 0000

step.2
i = 3 - 1 = 2  ; carry += 0 + 1 = 1
j = 3 - 1 = 2  ; carry += 1 + 1 = 2
result = carry & 1 + result => 2 & 1 + "0" => "0" + "0" = "01"
ex: carry & 1
   由 0010 => carry
   上 0001 =>   1
   往 ----
   下 0000
carry >>1 = 0010 => 0001

step.3
i = 2 - 1 = 1  ; carry += 1 + 0 = 1
j = 2 - 1 = 1  ; carry += 1 + 0 = 1
result = carry & 1 + result => 1 & 1 + "01" => "1" + "01" = "101"
ex: carry & 1
   由 0001 => carry
   上 0001 =>   1
   往 ----
   下 0001
carry >>1 = 0001 => 0000

step.4
i = 1 - 1 = 0  ; carry += 0 + 1 = 1
j = 1 - 1 = 0  ; carry += 1 + 1 = 2
result = carry & 1 + result => 0 & 1 + "101" => "0" + "101" = "0101"
ex: carry & 1
   由 0010 => carry
   上 0001 =>   1
   往 ----
   下 0000
carry >>1 = 0010 => 0001

step.5
return carry ? "1" + result : result
          1  ?   "1"+"0101" : "0101"
        true      "10101"      

Right shift assignment

Syntax:
x >>= y // x = x >> y
                                          ...8421
let a = 5; //   (00000000000000000000000000000101)
a >>= 2;   // 1 (00000000000000000000000000000001)
ex.二進制下最右邊的'01'消失，左邊往右移兩位。

JavaScript Demo: Expressions – Conditional operator

function getFee(isMember) {
  return (isMember ? '$2.00' : '$10.00');
}

console.log(getFee(true));
// expected output: "$2.00"

console.log(getFee(false));
// expected output: "$10.00"

console.log(getFee(null));
// expected output: "$10.00"

Remark: 暴力解 => 使用Js的BigInt()語法來處理「 > 2^53 」的數值，再運用toString(2)改成二進制來表示。
Code 2:

var addBinary = function(a, b) {
  return (BigInt("0b" + a) + BigInt("0b" + b)).toString(2);
};

const hugeBin = BigInt("0b11111111111111111111111111111111111111111111111111111");
// ↪ 9007199254740991n

參考數字範圍：