剑指 Offer 15. 二进制中1的个数 & 65. 不用加减乘除做加法

15题目描述：

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。

解析：

1.初始化数量统计变量count；
2.循环消去最右边的1：当n=0时跳出；
n &= n - 1：消去数字最右边的1；
count++：统计变量加1；
3.最后返回统计数量count。

Java:

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

JavaScript:

var hammingWeight = function(n) {
    let count = 0;
    while(n !== 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
};

65题目描述：

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

解析：

1.无进位和n与进位c的计算公式如下:
n = a ^ b 非进位和: 异或运算
c = (a & b) << 1 进位: 与运算+左移一位
2.因为 (和s) = (非进位和n) + (进位c) ，所以即可将 s = a + b 转化为 s = n + c ，即 s = a ^ b + (a & b) << 1
3.采用递归思想: 虽然s = a + b = n + c，但是n + c还是用了'+'，因此我们对n + c再次采用这种运算 (也就是把n当成a，c当成b，继续做a+b运算。看似无限循环，但是进位c总会有等于0的时候，此时结果就等于n)
4.非递归同理，循环求n和c，直至进位c = 0; 此时s = n, 返回n即可。

Java:

class Solution {
    public int add(int a, int b) {
        if(b == 0) {
            return a;
        }
        int c = a ^ b;
        int d = (a & b) << 1;
        return add(c, d);
    }
}

JavaScript:

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