位运算

剑指 Offer 15. 二进制中1的个数(简单)

通过移位运算符以及不停的&1来判断单位数是否为1

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans = 0;
        for(int i = 0; i <= 31; i++){
            if((n>>i)&1==1){
                ans++;
            }
        }
        return ans;
    }
};

剑指 Offer 65. 不用加减乘除做加法（重点）

• 一个关键是递推思想
• 异或运算^结果相当于二进制相加不进位，&运算结果左移相当于进位结果。每次都将进位结果和非进位结果重新相加，当进位结果位零时输出。
• c++不支持负数左移，因此转换为无符号数再次左移 ```cpp 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 ;
  

  } };

<a name="XxBS9"></a>
### [剑指 Offer 56 - I. 数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)（重点）
这一题和之前写过的一题非常相似，但是那一题是一个数组里面只有一个数字出现一次，这一道题是两个数字。那道题直接所有数字异或即可得出答案。此题在哪一题的基础上应该先进行分组异或，如何保证两个组各有一个只出现一次的数字呢？

- 直接将所有数组所有元素进行异或，最终的结果就是两个只出现一次的数字以异或的结果，如果最终某一位为1就代表这两个数字的这一位不同，达成分组条件。
- 直接按照不同的哪一位来进行两种异或就可以得到最终的答案。
- **关键1， c << 1并不能改变c， c<<=1才行**
- **关键2，==的优先级要大于&，因此在与的时候应该加()**
- **注意多用()号**
```cpp
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int a = 0;
        for(auto b : nums){
            a = a^b;
        }
        int c = 1;
        while((c&a) == 0){//注意的地方
            c = c<<1;//错误的地方
        }
        int num1 = 0, num2 = 0;
        for(auto b : nums){
            if((b&c) == 0){
                num1 = num1^b;
            } else {
                num2 = num2^b;
            }
        }
        return {num1, num2};
    }
};

剑指 Offer 56 - II. 数组中数字出现的次数 II(重点)

与上面相比，不同的是只有一个出现一次的数字，但是其他的数字出现3次。
有点难

位运算

想法很妙，但是时间复杂度比hash表高，但是空间复杂度低。
这里的想法太过巧妙，因为都是3个，只有一个出现一次。因为先统计各个位的1的数量，然后对3求余，如果不为零就代表目标数的这里也存在。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};

哈希表（笨比方法）

这里我忘记了遍历hash表的方法，这里记住，将原数组遍历即可。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hash;
        for(auto a : nums){
            hash[a]++;
        }
        for(auto a : nums){
            if(hash[a] == 1){
                return a;
            }
        }
        return 0;
    }
};

剑指 Offer II 001. 整数除法（越界问题）

这一题的含金量太重了，需要考虑越界问题和事件复杂度，为n的复杂度会超时

• 把a和b都转化成负数来计算，防止越界。
• 这一题有TCP拥塞控制的思想，慢启动，指数级增长。

• 复杂度为logn*logn，含金量太足了

  class Solution {
  public:
    int divide(int a, int b) {
    if (a == INT_MIN && b == -1) return INT_MAX;
  //当a为-2147483648，b为-1的时候会越界，因为整数最大只能到2147483647，因为整数首位是0，包括了0这一个非正非负的数，所以整数比负数少一位。
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;//把符号存储下来
  //同上原因，把两个都转化为负数防止越界
        if (a > 0) a = -a;
        if (b > 0) b = -b;
  
        int res = 0;
        while (a <= b) {
            int value = b;
            int k = 1;
            // 0xc0000000 是十进制 -2^30 的十六进制的表示
            // 判断 value >= 0xc0000000 的原因：保证 value + value 不会溢出
            // 可以这样判断的原因是：0xc0000000 是最小值 -2^31 的一半，
            // 而 a 的值不可能比 -2^31 还要小，所以 value 不可能比 0xc0000000 小
            while (value >= 0xc0000000 && a <= value + value) {
                value += value;
                // 代码优化：如果 k 已经大于最大值的一半的话，那么直接返回最小值
                // 因为这个时候 k += k 的话肯定会大于等于 2147483648 ，这个超过了题目给的范围
                if (k > 0x3fffffff) return INT_MIN;//这里的0x3fffffff是最大正数的一半
                k += k;
            }
            a -= value;
            res += k;
        }
  
        // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
        return sign == 1 ? res : -res;
  }
  };