剑指 Offer 15. 二进制中1的个数

循环判断

循环判断每一位是不是1

class Solution {
public:
  int hammingWeight(uint32_t n) {
      // 循环判断某位是不是1
      int res = 0;
      for (int i = 0; i < 32; i++) {
          if (n & (1 << i))
              res++;
      }
      return res;
  }
};

时间复杂度O(k) k是二进制位数比如32位要比较32次
空间复杂度O(1)

将n不断右移每次判断最右边一位是否为1（不能处理负数）

class Solution {
public:
  int hammingWeight(uint32_t n) {
      int count = 0;
      while (n) {
          if (n & 1) {
              count++;
          }
          n = n >> 1;
      }
      return count;
  }
};

如果函数输入的是一个负数，如0x80000000，把负数右移一位，要保证移位后的数仍未负数，因此第一位补1而不是像正数那样补0，因此得到的结果为0xC0000000而不是0x40000000，如果一直右移位，那么数字最后会变为0xFFFFFFFF，而进入死循环。

位运算优化

运算：n&(n - 1)，其结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果

如：6&(6-1) = 4, 6 = (110)_2, 4 = (100)_2，运算结果 44 即为把 66 的二进制位中的最低位的 1 变为 0 之后的结果。

这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 n 与 n - 1 做与运算，直到 n 变为 0 即可。因为每次运算会使得 n 的最低位的 1 被翻转，因此运算次数就等于 n 的二进制位中 1 的个数。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        // n & (n - 1) 操作后，n的最低位1会变为0
        int res = 0;
        while (n) {
            n &= n - 1;
            res++;
        }
        return res;
    }
};

时间复杂度O(k) k为二进制数中1的个数
空间复杂度O(1)

lowbit(线段树的基础)

lowbit，返回最低位的1以及后面的0

int lowbit(int n) {
    return n & (~n + 1);
}

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

这个取反加一有些数据会越界，不过无所谓，记住思想

剑指 Offer 56 - I. 数组中数字出现的次数

异或的一个性质：如果一组数中除了一个数字之外其他的都有两个（偶数对），因为相同为0，不同为1，将这组数进行异或后得到的就是没有重复的那个数字
记不重复的两个数字为a, b
根据这个思路，想办法将数组分为两个部分，一个部分包含a和其他重复数字，另一部分包含b和另外的重复数字
对两组数分别异或，得到的就是a，b

首先，根据将数组异或，最后得到的数字是x = a^b的结果，因为a、b不相同，那么x应该至少有一位是1，表示a与b这一位不相同
然后，我们找到x中第一个为1的那一位，然后根据这一位是不是1对数组进行分组，这样a、b必然会被分到两组中，然后重复的数值因为每一位都是相同的，将会分到同一组
最后，两组异或就得到了a、b

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        if (nums.size() == 2) return nums;
        // 得到两个不同的数字异或的结果
        int x = 0;
        for (auto num: nums) x ^= num;
        // 找到第一个1，也就时两数不同的一位，根据这个分组
        int tmp = 1;
        while ((tmp & x) == 0) tmp <<= 1;
        int a = 0, b = 0;
        for (auto num: nums) {
            if (num & tmp) a ^= num;
            else b ^= num; 
        }
        return {a, b};
    }
};

剑指 Offer 56 - II. 数组中数字出现的次数 II

有些数字出现了三次，那么二进制数的每一位也会出现三次，也就是说这一位能够被3整除。
那么可以把该数组中所有数的二进制位数加起来，如果某一位的和能够被3整除，那么只出现一次的那个数该位为0，否则为1

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> bitSum(32, 0);
        // 求各位之和
        for (auto num: nums) {
            for (int i = 0; i < 32; i++) {
                if (((num >> i) & 1) != 0) {
                    bitSum[i]++;
                }
            }
        }

        // 求出现一次的数
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            res = (res << 1);
            res += bitSum[i] % 3;
        }
        return res;
    }
};

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

思路：
两个数异或，相当于求二进制的不进位和，两个数的与运算，可以得到有进位的位，比如 1 + 1进位，1&1的结果位1，那么将两数与运算，再将得到的结果左移位，然后与不进位和再进行不进位和运算，循环直到进位为0为止，就是二数相加的结果
位运算 - 图5
c++不支持负数左移，需要强制转换为无符号整数左移

class Solution {
public:
    int add(int a, int b) {
//因为不允许用+号，所以求出异或部分和进位部分依然不能用+ 号，所以只能循环到没有进位为止        
        while(b!=0)
        {
//保存进位值，下次循环用
            int c=(unsigned int)(a&b)<<1;//C++中负数不支持左移位，因为结果是不定的
//保存不进位值，下次循环用，
            a^=b;
//如果还有进位，再循环，如果没有，则直接输出没有进位部分即可。
            b=c;   
        }
        return a;
    }
};