Viiisit [LeetCode] - 67. Add Binary

keep learning, keep coding!

Problem - Add Binary

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

翻譯蒟蒻

給定兩個二進位的數，要返回兩者的總和

---

• Example 1:

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

• Example 2:

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

---

Solution - JavaScript

藉由從最後一位數開始處理，並用 temp 作為存儲進位值

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
  let result = "";
  let i = a.length - 1, j = b.length - 1;
  let temp = 0;

  while (i >= 0 || j >= 0) {
    let sum = temp;
    if (i >= 0) {
      sum += parseInt(a[i--]);
    }
    if (j >= 0) {
      sum += parseInt(b[j--]);
    }
    result = (sum % 2) + result;
    temp = Math.floor(sum / 2);
  }

  if (temp) {
    result = temp + result;
  }

  return result;
};

parseInt() 函數可以將字符串轉換為整數，
但！ parseInt() 在解析二進制字符串時有一個限制：只能解析 32 位的二進制數字。
如果二進制字串表示的數字大於 11111111111111111111111111111111（32 個 1），parseInt() 就無法正確解析，所以以下方式不會過。

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
  const sum = parseInt(a, 2) + parseInt(b, 2);
  return sum.toString(2);
};

Solution - Ruby

Solution 1:

使用 reverse 為了從最右邊開始進行加法運算。

def add_binary(a, b)
  a = a.split("").reverse
  b = b.split("").reverse
  result = []
  temp = 0
  i = 0
  while i < a.length || i < b.length
    sum = temp
    sum += a[i].to_i if i < a.length
    sum += b[i].to_i if i < b.length
    result << sum % 2
    temp = sum / 2
    i += 1
  end
  result << temp if temp > 0
  result.reverse.join("") 
end

Solution 2:

def add_binary(a, b)
  sum = a.to_i(2) + b.to_i(2)
  sum.to_s(2)
end

與上面的 JavaScript parseInt() 相比之下，Ruby 的 to_i 方法可以解析任意長度的二進制字串。這也是為什麼在 Ruby 中可以直接使用 to_i 和 to_s 方法來進行二進制加法，而在 JavaScript 中則需要使用更複雜的方法。

Solution - PHP

function addBinary($a, $b) {
  $result = "";
  $temp = 0;
  $i = strlen($a) - 1;
  $j = strlen($b) - 1;
  while ($i >= 0 || $j >= 0 || $temp == 1) {
    $temp += $i >= 0 ? $a[$i--] : 0;
    $temp += $j >= 0 ? $b[$j--] : 0;
    $result = ($temp % 2) . $result;
    $temp = (int)($temp / 2);
  }
  return $result;
}

以下方式會造成 Runtime Error，原因在於處理非常大的數字時會失效。

function addBinary($a, $b) {
    return decbin(bindec($a) + bindec($b));
}

PHP 方法筆記

• bindec 函數用於將二進制字符串轉換為對應的十進制數字。

  函數的基本語法如下：

  int bindec ( string $binary_string )
  
  // `$binary_string`: 要轉換的二進制字符串。

  $binaryString = '1101';
  $decimalNumber = bindec($binaryString);
  echo $decimalNumber;
  
  // Output: 13

• decbin 函數用於將十進制數字轉換為對應的二進制字符串。

  函數的基本語法如下：

  string decbin ( int $number )
  
  // `$number`: 要轉換的十進制數字。

  $decimalNumber = 10;
  $binaryString = decbin($decimalNumber);
  echo $binaryString;
  
  // Output: 1010

LeetCode 傳送門 - Add Binary