【C++刷题】优选算法——位运算

常见位运算操作总结：

1. 基础位运算
   &：有0则为0
   |：有1则为1
   ^：相同为0，相异为1 / 无进位相加
2. 运算符的优先级
   管它什么优先级，加括号就完事儿了
3. 给一个数 n，确定它的二进制表示中的第 i (默认是从右起第0位) 位是 0 还是 1
   (n >> i) & 1
4. 将一个数 n 的二进制表示的第 i 位修改为 1
   n |= (1 << i)
5. 将一个数 n 的二进制表示的第 i 位修改成 0
   n &= (~(1 << i))
6. 提取一个数 n 二进制表示中最右侧的 1 （lowbit操作）
   n & (-n)
   (-n) 将 n 最右侧的 1 的 左边的区域 全部变成了相反的位
7. 干掉一个数 n 二进制表示中最右侧的 1
   n &= (n - 1)
   (n - 1) 将 n 最右侧的 1 的 右边的区域(包括最右侧的1)，全部变成了相反的位
8. 异或 ^ 运算的运算律
   n ^ 0 = n
n ^ n = 0 - 消消乐
   a ^ b ^ c = a ^ (b ^ c)

根据第6、7条位运算操作，可以搞定1-3题。

1. 位1的个数

int hammingWeight(int n)
{
    int ret = 0;
    while(n)
    {
        ++ret;
        n &= (n - 1);
    }
    return ret;
}

2. 比特位计数

int hammingWeight(int n)
{
    int ret = 0;
    while(n)
    {
        ++ret;
        n &= (n - 1);
    }
    return ret;
}
vector<int> countBits(int n)
{
    vector<int> ret(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        ret[i] = hammingWeight(i);
    }
    return ret;
}

3. 汉明距离

int hammingWeight(int n)
{
    int ret = 0;
    while(n)
    {
        ++ret;
        n &= (n - 1);
    }
    return ret;
}
int hammingDistance(int x, int y)
{
    int ret = 0;
    while(x && y)
    {
        if((x & (-x)) < (y & (-y)))
        {
            ++ret;
            x &= (x - 1);
        }
        else if((x & (-x)) > (y & (-y)))
        {
            ++ret;
            y &= (y - 1);
        }
        else
        {
            x &= (x - 1);
            y &= (y - 1);
        }
    }
    ret += hammingWeight(x);
    ret += hammingWeight(y);
    return ret;
}

结合第 8 条位运算操作，可以搞定4-5题。
4. 只出现一次的数字

int singleNumber(vector<int>& nums)
{
    int ret = 0;
    for(int e : nums) ret ^= e;
    return ret;
}

5. 只出现一次的数字 III

vector<int> singleNumber(vector<int>& nums)
{
    long long lowbit = 0;
    for(int e : nums) lowbit ^= e;
    lowbit &= (-lowbit);

    long long low_0 = 0, low_1 = 0;
    for(int e : nums)
    {
        if(e & lowbit) low_1 ^= e;
        else low_0 ^= e;
    }
    return {(int)low_0, (int)low_1};
}

6. 判定字符是否唯一

bool isUnique(string astr) 
{
    if(astr.size() > 26) return false;
    int hash = 0;
    for(char c : astr)
    {
        int bit = 1 << (c - 'a');
        if( hash & bit ) return false;
        else hash |= bit;
    }
    return true;
}

7. 丢失的数字

// 高斯求和
int missingNumber(vector<int>& nums)
{
    int n = nums.size();
    int sum = (0 + n) * (n + 1) / 2;
    for(int e : nums) sum -= e;
    return sum;
}

// 异或 运算律
int missingNumber(vector<int>& nums)
{
    int n = nums.size();
    int ret = 0;
    for(int i = 0; i <= n; ++i) ret ^= i;
    for(int e : nums) ret ^= e;
    return ret;
}

8. 两整数之和

int getSum(int a, int b)
{
    while(b)
    {
        int no_carry = a ^ b;
        int carry = (a & b) << 1;
        a = no_carry;
        b = carry;
    }
    return a;
}

9. 只出现一次的数字 II

int singleNumber(vector<int>& nums)
{
    int ret = 0;
    for(int i = 0; i < 32; ++i)
    {
        int num = 0;
        for(int e : nums) if( e & (1 << i) ) ++num;
        if(num % 3) ret |= (1 << i);
    }
    return ret;
}

10. 消失的两个数字

vector<int> missingTwo(vector<int>& nums)
{
    int n = nums.size();
    int N = n + 2;

    int num = 0;
    for(int i = 1; i <= N; ++i) num ^= i;
    for(int e : nums) num ^= e;

    int lowbit = num & (-num);
    int low_0 = 0, low_1 = 0;

    for(int i = 1; i <= N; ++i)
    {
        if(i & lowbit) low_1 ^= i;
        else low_0 ^= i;
    }
    for(int e : nums)
    {
        if(e & lowbit) low_1 ^= e;
        else low_0 ^= e;
    }
    
    return {low_0, low_1};
}