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

写个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
输入: a = 1, b = 1
输出: 2

思路

显然，这道题是想让我们用位运算进行实现。注意到两数相加就是进位和本位相加，用carry表示进位，用curb表示本位，那么有：

carry=(a \\& b)<<1

$$curb=(a\wedge b)$$

然后就有两种方式进行计算了：

1. 递归

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

2. 非递归

class Solution {
public:
    int add(int a, int b) {
      while(b != 0){
        int c = (unsigned int)(a & b) << 1;
        a = (a ^ b);
        b = c;
      }
      return a;
    }
};

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

思路

很容易想到$O(n*logn)$的做法，这里需要$O(n)$的算法

class Solution {
public:
    vector<int> countBits(int n) {
      // int ans = 0;
      vector<int> ans(n+1);
      for(int i= 1; i <= n; i++){
      	//ans[i] = ans[i&(i-1)] + 1; //最低设置有效位
        ans[i] = ans[i >> 1] + (i & 1); //最低位
      }
      return ans;

    }
};