【算法】位运算

昨晚 Win10 更新 2h 都没有更新完，然后电脑因为没电关机了。。重启后恢复出厂设置都无效

还好自己用 PE 救回来了，怕重蹈覆辙，把最近的记录的东东都搬到博客上了

仅为个人学习记录，如有错误欢迎指正（毕竟也都是随笔记录

前言

逻辑代数与位运算的关系

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

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

逻辑代数公式

A ⊕ B = AB' + A'B

即 (A ^ B) = (A & ~B) | (~A & B)

A ⊙ B = AB + A'B'

二进制加法

S = A ⊕ B ⊕ C_in

C_out = (A · B) + (B · C_in) + (A · C_in)

可换算 C_out，式子如下：

C_out = (A · B) + (C_in · (A + B))

也可用一个异或门来代替或门对其中两个输入信号进行求和

C_out = (A · B) + (C_in · (A ⊕ B))

换成位运算即

init: C = C_out = C_in = 0

s = a ^ b ^ c

c = (a & b) | (c & (a ^ b))

例题

class Solution {
public:
    string addBinary(string a, string b) {
        int lena = a.size(), lenb = b.size();
        int n = max(lena, lenb) + 1;
        int ai, bi, s, c = 0;
        int i = 0;
        string res(n, 0);
        for(; i < n; ++i) {
            ai = (lena - i - 1 >= 0 ? a[lena - i - 1] - '0' : 0);
            bi = (lenb - i - 1 >= 0 ? b[lenb - i - 1] - '0' : 0);
            s = ai ^ bi ^ c;
            c = (ai & bi) | (c & (ai ^ bi));
            res[n - i - 1] = s + '0';
        }
        if('0' == res[0]) res.erase(res.begin());
        return res;
    }
};

统计n中1的个数

0xAAAAAAAA = 10101010101010101010101010101010
0x55555555 = 01010101010101010101010101010101（奇数位为1，以1位为单位提取奇偶位）

0xCCCCCCCC = 11001100110011001100110011001100
0x33333333 = 00110011001100110011001100110011（以“2位”为单位提取奇偶位）

0xF0F0F0F0 = 11110000111100001111000011110000
0x0F0F0F0F = 00001111000011110000111100001111（以“8位”为单位提取奇偶位）

0xFFFF0000 = 11111111111111110000000000000000
0x0000FFFF = 00000000000000001111111111111111（以“16位”为单位提取奇偶位）

例如：32位无符号数的1的个数可以这样数：

int count_one(unsigned long n){
    //0xAAAAAAAA，0x55555555分别是以“1位”为单位提取奇偶位
    n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);

    //0xCCCCCCCC，0x33333333分别是以“2位”为单位提取奇偶位
    n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);

    //0xF0F0F0F0，0x0F0F0F0F分别是以“4位”为单位提取奇偶位
    n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);

    //0xFF00FF00，0x00FF00FF分别是以“8位”为单位提取奇偶位
    n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF);

    //0xFFFF0000，0x0000FFFF分别是以“16位”为单位提取奇偶位
    n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF);

    return n;
}

举个例子吧，比如说我的生日是农历2月11，就用211吧，转成二进制：

n = 11010011

计算n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);

得到 n = 10010010

计算n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);

得到 n = 00110010

计算n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);

得到 n = 00000101 -----------------无法再分了，那么 5 就是答案了

倒置二进制位

分治法

int M1 = 0x55555555; //01010101010101010101010101010101
int M2 = 0x33333333; //00110011001100110011001100110011
int M3 = 0x0f0f0f0f; //00001111000011110000111100001111
int M4 = 0x00ff00ff; //00000000111111110000000011111111
int M5 = 0x0000ffff; //00000000000000001111111111111111

n = (n >> 16) & M5 | (n & M5) << 16;
n = (n >> 8) & M4 | (n & M4) << 8;
n = (n >> 4) & M3 | (n & M3) << 4;
n = (n >> 2) & M2 | (n & M2) << 2;
n = (n >> 1) & M1 | (n & M1) << 1;
return n;

对于正整数的模运算

等于 n % k，这里 k 必须等于 2^m才有用

公式

n & ((1 << k) - 1)

判断n是否是2的正整数幂

公式

n > 0 && !(n & (n - 1))

这里题目如果规定测试用例都是正整数，那么可以简写成 n && !(n & (n - 1))

引申题

1. 判断 n 是否是 4 的正整数幂

   (n & 0x55555555) && !(n & (n - 1)) && n;