[Algo] 位运算

1. 出现奇数次的数①

// 1. 一个数组中，只有一种数A出现过奇数次，其余数都出现过偶数次，问A？
int oddNumber(const vector<int> &v)
{
    int eor = 0;
    for (const auto &e : v) eor ^= e;
    return eor;
}

2. 出现奇数次的数②

// 2. 一个数组中，只有两种数A与B出现过奇数次，其余数都出现过偶数次，问A与B？
pair<int, int> oddNumbers(const vector<int> &v)
{
    int eor = 0;
    for (const auto &e : v) eor ^= e; // eor = A ^ B
    int rightOne = eor & (-eor); // 获取二进制状态中最后一个1
    int eor0 = 0;
    for (const auto &e : v) eor0 = (e & rightOne) == 0 ? eor0 ^ e : eor0; // 通过该二进制位的状态分离A与B
    return make_pair(eor0, eor ^ eor0); 
}

3. 连续与运算

// 3. 返回[A,B]依次与运算的结果
int continuousAnd(int A, int B)
{
    while (A < B) B -= B & (-B);
    return B;
}

4. 二进制状态的逆序

// 4. 返回一个数二进制状态的逆序
unsigned int binaryReverse(unsigned int val)
{
    val = ((val & 0xaaaaaaaa) >> 1) | ((val & 0x55555555) << 1); // 2个为一组进行交换
    val = ((val & 0xcccccccc) >> 2) | ((val & 0x33333333) << 2); // 4个为一组进行交换
    val = ((val & 0xf0f0f0f0) >> 4) | ((val & 0x0f0f0f0f) << 4); // 8个为一组进行交换
    val = ((val & 0xff00ff00) >> 8) | ((val & 0x00ff00ff) << 8); // 16个为一组进行交换
    val = ((val & 0xffff0000) >> 16) | ((val & 0x0000ffff) << 16); // 32个为一组进行交换
    return val;
}

5. 二进制状态中1的个数

// 5. 返回一个数二进制状态中1的个数
unsigned int binaryOnes(unsigned int val)
{
    val = (val & 0x55555555) + ((val & 0xaaaaaaaa) >> 1); // 2个为一组进行计数
    val = (val & 0x33333333) + ((val & 0xcccccccc) >> 2); // 4个为一组进行计数
    val = (val & 0x0f0f0f0f) + ((val & 0xf0f0f0f0) >> 4); // 8个为一组进行计数
    val = (val & 0x00ff00ff) + ((val & 0xff00ff00) >> 8); // 16个为一组进行计数
    val = (val & 0x0000ffff) + ((val & 0xffff0000) >> 16); // 32个为一组进行计数
    return val;
}

* 基数排序(补)

// 基数排序 时间复杂度为O(m*(n+r)),空间复杂度为O(n+r)
void radixSort(vector<int> &v, int bits)
{
    // 总共m(bits)轮
    for (int offset = 1; bits > 0; bits--, offset *= 10)
    {
        vector<int> cnts(10);
        for (const auto &e : v) cnts[e / offset % 10]++;
        for (int i = 1; i < cnts.size(); i++) cnts[i] += cnts[i - 1];
        vector<int> help(v);
        for (int i = v.size() - 1; i >= 0; i--) help[--cnts[v[i] / offset % 10]] = v[i];
        v = help; 
    }
}
void RadixSort(vector<int> &v)
{
    // 需要处理存在负数的情形
    auto min_it = min_element(v.begin(), v.end());
    int min_val = *min_it;
    for (auto &e : v) e -= min_val;
    // 计算最大值的位数
    auto max_it = max_element(v.begin(), v.end());
    int max_val = *max_it;
    int bits = 0;
    while (max_val > 0)
    {
        max_val /= 10;
        bits++;
    }
    radixSort(v, bits);
    for (auto &e : v) e += min_val;
}