位运算：二进制求和，求解《面试题 17.01. 不用加号的加法》和《剑指 Offer 65. 不用加减乘除做加法》

二进制求和

• 不考虑进1：a ^ b
• 只考虑进 1：(a & b) << 1
  • 相加一次：a ^ b ^ (a & b) << 1
  • 相加后，还需要进 1，继续 递归 或 迭代

模板

递归

function add(a, b) {
  if (b === 0) return a
  return add(a ^ b, (a & b) << 1)
}

迭代

function add(a, b) {
  while(b) {
    const t = a ^ b
    b = (a & b) << 1
    a = t
  }
  return a
}

例题

面试题 17.01. 不用加号的加法

剑指 Offer 65. 不用加减乘除做加法

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

答案

递归

var add = function(a, b) {
  if (b === 0) return a
  return add(a ^ b, (a & b) << 1)
};

func add(a int, b int) int {
  if b == 0 {
    return a
  }
  return add(a ^ b, (a & b) << 1)
}

class Solution {
    function add($a, $b) {
      if ($b === 0) return $a;
      return $this->add($a ^ $b, ($a & $b) << 1);
    }
}

迭代

var add = function(a, b) {
  while (b) {
    const t = a ^ b
    b = (a & b) << 1
    a = t
  }
  return a
};

func add(a int, b int) int {
  for b != 0 {
    t := a ^ b
    b = (a & b) << 1
    a = t
  }
  return a
}

class Solution {
    function add($a, $b) {
      while ($b) {
        $t = $a ^ $b;
        $b = ($a & $b) << 1;
        $a = $t;
      }
      return $a;
    }
}