Bit-Manipulation Medium

**Abstract：**位操作 中等难度合集

29. Divide Two Integers

解法一：递归

不会处理溢出，先贴个投机取巧的方法，虽然也是和题解学的/瘫倒/

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor ==  1) return dividend;
        if(divisor == -1) {
            return dividend == INT32_MIN ? INT32_MAX : -dividend;
        }
        long a = dividend, b = divisor;
        bool isNeg = (dividend ^ divisor) >> 31;
        long res = div(abs(a), abs(b));
        if(res > INT32_MAX) return INT32_MAX;
        return isNeg ? -res : res;
    }

    int div(long a, long b) {
        if (a < b) return 0;
        long cnt = 1, t = b;
        while((t << 1) <= a) {
            cnt <<= 1;
            t <<= 1;
        }
        return cnt + div(a - t, b);
    }
};

260. Single Number III

解法一：掩码

• 先用一个掩码异或所有数组元素，剩下的将会是出现奇数次的数

• mask & -mask，取得x， y中最右边的1，这个1只能来自x，y其中之一，可以用来筛掉其中一个

• 注意位运算的优先级很低，一定要加括号

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int mask = 0;
        vector<int> res;
        for(int i : nums) mask ^= i;

        int t = mask & -mask, tmask = 0;
        for(int i : nums) if((i & t) != 0) tmask ^= i;
        return {tmask, tmask ^ mask};
    }
};

137. Single Number II

解法一：unordered_map

最简单的办法显然是用map统计出现的次数，再找到出现次数不等于3的那个

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> map;
        for(int i : nums) map[i]++;
        for(auto i : map)
            if(i.second != 3) 
                return i.first;
        return -1;
    }
};

解法二：逐位计数

对每一位出现1的次数计数，时间复杂度 $O(32 * n) = O(n)$, 空间复杂度降到了$O(1)$

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < 32; i++) {
            int idx = 1 << i, cnt = 0;
            for(int v : nums) {
                if((v & idx) != 0)
                    cnt++;
            }
            if(cnt % 3 == 1)
                res |= idx;
        }
        return res;
    }
};

解法三：有限状态自动机

用两个位来记录出现次数，一共有三种状态也就是

a	b	代表出现的次数
0	0	0
0	1	1
1	1	2

• 当出现次数超过2时，则重新变回1状态

• 如果画出状态转移表

a	b	c	目标状态
0	0	0	00
0	1	0	01
1	0	0	10
0	0	1	01
0	1	1	10
1	0	1	00

• 可以得出转移表达式为

  b = !a & (b ^ c);
  a = !b & (a ^ c);
  

• 最后32位二进制数中剩下非0位即为出现次数为 $3n + 1$ 的位

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for(int i : nums) {
            b = ~a & (i ^ b);
            a = ~b & (i ^ a);
        }
        return b;
    }
};