C++中的位运算及其应用技巧-猿码集

1. 什么是位运算

在计算机中，所有的数据都以二进制形式存储。位运算就是对二进制数据按位进行操作的运算。

1.1 常见的位运算符

&（按位与）：将两个二进制数进行“与”操作，只有在相应位都为1时才为1。

|（按位或）：将两个二进制数进行“或”操作，只有在相应位都为0时才为0。

^（按位异或）：将两个二进制数进行“异或”操作，只有在相应位不同时才为1。

~（按位取反）：将二进制数按位取反。

<<（左移）：将二进制数向左移动指定的位数。

>（右移）：将二进制数向右移动指定的位数。

int a = 3; // 十进制数3的二进制表示为11
int b = 5; // 十进制数5的二进制表示为101
int c = a & b; // 11 & 101 = 001，c的值为1
int d = a | b; // 11 | 101 = 111，d的值为7
int e = a ^ b; // 11 ^ 101 = 110，e的值为6
int f = ~a; // ~11 = 11111111111111111111111111111100，f的值为-4
int g = b << 1; // 101 << 1 = 1010，g的值为10
int h = b >> 1; // 101 >> 1 = 10，h的值为2

1.2 位运算的优先级

位运算的优先级比较低，一般放在括号中以免出现错误。

int a = 3;
int b = 5;
int c = (a & b) ^ (a | b);

2. 位运算的应用技巧

2.1 位运算实现加法、减法和乘法

用位运算实现加法、减法和乘法的方法十分简单。

2.1.1 位运算实现加法

将两个数的二进制按位进行“异或”操作，得到的结果再和进位进行“与”操作。将得到的结果和进位左移1位后的结果相加，重复上述过程直到进位为0即可。

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

2.1.2 位运算实现减法

将减数取反后加1，即可实现减法。

int sub(int a, int b) {
    b = add(~b, 1);
    return add(a, b);
}

2.1.3 位运算实现乘法

将其中一个数不断右移1位，如果该数的最后一位为1，则将另一个数左移相应的位数后加到结果中。

int mul(int a, int b) {
    int res = 0;
    while (b) {
        if (b & 1) {
            res = add(res, a);
        }
        a <<= 1;
        b >>= 1;
    }
    return res;
}

2.2 位运算实现判断奇偶

判断一个数是奇数还是偶数，可以用该数的二进制表示中的最后一位来判断。如果该数的二进制表示中最后一位为1，则该数为奇数，否则为偶数。

int n = 5;
if (n & 1) {
    cout << "n is odd" << endl;
} else {
    cout << "n is even" << endl;
}

2.3 位运算实现交换两个数

用位运算实现交换两个数的值的方法也很简单。

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

2.4 位运算实现集合的运算

用二进制数表示集合的元素，对于两个集合可以进行并、交、补、异或等操作。

2.4.1 用二进制数表示集合元素

设集合S={a1, a2, ..., an}，用一个n位二进制数表示集合S中的元素，第i位为1说明集合S中存在第i个元素，为0说明集合S中不存在第i个元素。

例如，集合S={1, 3, 4}可以用二进制数1011表示。

2.4.2 集合的并、交、补、异或运算

设集合A和集合B的二进制数分别为a和b，则集合的运算可以用位运算实现。

并运算：a | b

交运算：a & b

补运算：~a

异或运算：a ^ b

int a = 11; // S = {1, 3, 4}
int b = 22; // T = {2, 3, 5}
int c = a | b; // S ∪ T = {1, 2, 3, 4, 5}
int d = a & b; // S ∩ T = {3}
int e = ~a; // S' = {2, 5, 6, ..., n}
int f = a ^ b; // (S ∪ T) - (S ∩ T) = {1, 2, 4, 5}

2.5 用位运算实现取模

用位运算实现取模的方法非常简单，只需要利用二进制数的性质即可。

2.5.1 取模运算的性质

对于任意正整数a和b，设a/b的结果为q，余数为r，则有：

① a = b * q + r

② 0 ≤ r < b

例如，13/5的结果为2，余数为3。

把a表示成二进制数，b表示成二进制数的形式，即可用位运算实现取模。

2.5.2 用位运算实现取模

将a的二进制数不断右移，直到小于b，同时记录右移的次数，然后将b左移相应的次数。然后用a减去b，重复上述过程直到a小于b为止。

int mod(int a, int b) {
    int res = 0;
    while (a >= b) {
        int p = 0;
        while ((b << p) <= a) {
            ++p;
        }
        res += 1 << (p - 1);
        a -= b << (p - 1);
    }
    return res;
}

2.6 用位运算实现求幂

用位运算实现求幂的方法比较特别，需要用到二进制数的性质。

2.6.1 求幂运算的性质

对于任意正整数x、y，有以下结论：

① x^y = x^(y/2) * x^(y/2)，当y为偶数时

② x^y = x^((y-1)/2) * x^((y-1)/2) * x，当y为奇数时

例如，2^10 = 2^5 * 2^5 = 32 * 32 = 1024。

2.6.2 用位运算实现求幂

这里采用的是迭代法，将幂按照2的幂次分解，从小到大递推即可。

int pow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) {
            res *= x;
        }
        x *= x;
        y >>= 1;
    }
    return res;
}

3. 总结

位运算是高效的、简单的计算机运算方式，可以用来解决很多问题，例如加法、减法、乘法、判断奇偶、交换两个数、集合操作、取模、求幂等问题。掌握位运算的技巧可以大大提高代码的效率。

C++中的位运算及其应用技巧