【C++算法/学习】位运算详解

IsLand1314

发布于 2024-10-15 20:33:44

7400

文章被收录于专栏：学习之路学习之路

引言

位运算（Bit Operation）：在计算机内部，数是以「二进制（Binary）」的形式来进行存储。位运算就是直接对数的二进制进行计算操作，在程序中使用位运算进行操作，会大大提高程序的性能。

二进制数（Binary）：由 0 和 1 两个数码来表示的数。二进制数中每一个 0 或每一个 1 都称为一个「位（Bit）」。

注：本文中参考代码均使用C++编写。

1. 位运算的运算符

运算符	描述	运算规则	🌰实例（下面以四位二进制数为例）
&	按位与运算符	只有对应的两个二进位都为 1 ，结果位才为 1。	0001&0001=1，0001&0000=0
\|	按位或运算符	只要对应的两个二进位有一个为1，结果位就为 1。	0001∣0001=0001，0001∣0000=0001
^	按位异或运算符	对应的两个二进位相异时，结果位为 1，二进位相同时则结果位为 0。	0001∧0001=0000，0001∧0000=1
~	取反运算符	对二进制数的每个二进位取反，使数字 1 变为 0，0 变为 1。	∼0=1，∼1=0
<<	左移运算符	将二进制数的各个二进位全部左移若干位。<< 右侧数字指定了移动位数，高位丢弃，低位补 0。	0001 << 2 -- > 0100
>>	右移运算符	对二进制数的各个二进位全部右移若干位。>> 右侧数字指定了移动位数，低位丢弃，高位补 0。	0100 << 2 -- > 0001

2. 位运算的性质

2.1 优先级

从上到下优先级依次递减

运算符	结合方向
−（负号运算符）,∼（取反运算符），++（自增），−−（自减），&（取地址运算符）	从右到左
∗（乘），/（除），%（取余）	从左到右
+（加），−（减）	从左到右
<<（左移），>>（右移）	从左到右
>（大于），<(小于)，>=(大于等于)，<=(小于等于)	从左到右
==(等于)，!=（不等于）	从左到右
&（按位与）	从左到右
∧ (按位异或)	从左到右
∣ (按位或)	从左到右

总结：能加括号就加括号

2.2 运算律

公式名称	运算规则
交换律	a & b = b & a , b ∧ a = a ∧ b
结合律（注：结合律必须在同符号下进行）	( a & b ) & c = a & ( b & c )，a ∧ b ∧ c = a ∧ (b ∧ c)
等幂律	a & a = a ， a ∣ a = a
零律	a & 0 = 0，a ∧ a = 0
互补律	a & ∼ a = 0 , a ∣ ∼ a = − 1
同一律	a∣ 0 = a ， a ∧ 0 = a

2.3 位运算的常用操作

功能（都是在二进制表示中的操作，k默认从1开始）	位运算（对于某个数x）	示例(默认右边为低位)
去掉最后一位	x >> 1	101101 -> 10110
在最后加一个 0	x << 1	101101 -> 1011010
在最后加一个 1	( x << 1 ) + 1	101101 -> 1011011
把最后一位变成 1	x ∣ 1	101100 -> 101101
把最后一位变成 0	(x ∣ 1) − 1	101101 -> 101100
最后一位取反	x ∧ 1	101101 -> 101100
把右数第 k 位变成 1	x ∣ ( 1 << ( k − 1 ))	101001 -> 101101, k = 3
把右数第 k 位变成 0	x & ( ∼ ( 1 << ( k − 1 )))	101101 -> 101001, k = 3
右数第 k 位取反	x ∧ ( 1 << ( k − 1 ))	101001 -> 101101, k = 3
取末尾 k 位	x & (( 1 << k) − 1 )	1101101 -> 1101, k = 4
取右数第 k 位	（x >> k − 1 ) & 1	1101101 -> 1, k = 4
把末尾 k 位全变成 1	x ∣ (( 1 << k ) − 1 )	101001 -> 101111, k = 4
末尾 k 位取反	x ∧ (( 1 << k ) − 1 )	101001 -> 100110, k = 4
把右边连续的 1 变成 0	x & ( x + 1 )	100101111 -> 100100000
把右边起第一个 0 变成 1	x \| ( x + 1 )	100101111 -> 100111111
把右边连续的 0 变成 1	x \| ( x - 1 )	11011000 -> 11011111
只保留右边连续的 1	(x ∧ ( x + 1 )) >> 1	100101111 -> 1111
提取右数最右侧的 1，其他位均为0	x & ( x ∧ ( x − 1 )) 或 x & ( - x )	100101000 -> 1000
从右边开始，把最后一个 1 改写成 0	x & ( x - 1 )	100101000 -> 100100000

3. 扩展概念&运算

🥝 lowbit

lowbit(x)即为二进制下 x 的最低位，如下：

6 => 0000 0110
-6=> 1111 1010(此处为6的补码)
6&(-6) = 2

严格来说 0 没有lowbit，部分情况下可视为lowbit(0) = 1。利用lowbit函数可实现树状数组等数据结构

lobit 的写法

暴力计算（简单粗暴的按位直接计算）

int lowbit(int x)
{
	int res = 1;
	while(x && !(x & 1))
		x >>= 1, res <<= 1;
	return res;
}

x & -x 巧妙利用lowbit(x) = x & -x。感兴趣的读者可自行尝试证明。时间复杂度O ( 1 ) 。相比(1)来说，代码更短，速度更快。

x& (x - 1) 注意：x& (x - 1)不是lowbit(x)，而是x - lowbit(x)。这种方法常用于树状数组中，可提升x - lowbit(x)的计算速度。

🥑 popcount

popcount(x)定义为 x 在二进制下 1 的个数，如popcount(10101) = 3，popcount(0) = 0。

popcount 的写法

暴力计算检查（枚举每一位并检查是否为1达到目的，时间复杂度为O ( log X )）

int popcount(int x)
{
	int res = 0;
	while(x)
	{
		res += x & 1;
		x >>= 1;
	}
	return res;
}

lowbit 优化时间复杂度还是O ( log ⁡X )，不过平均用时会比(1)快2~3倍左右。

int popcount(int x)
{
	int res = 0;
	for(; x; x&=x-1) res ++;
	return res;
}

builtin 函数（最快）

🍉 builtin 位运算函数

详情可见：C/C++ __builtin 超实用位运算函数总结 - 知乎 (zhihu.com)

注意：后面带 LL 的传入long long类型，不带 LL 接受int类型。本部分内容按常用程度递减排序。

__builtin_popcount / __builtin_popcountll ：返回参数在二进制下 1 的个数。
__builtin_ctz / __buitlin_ctzll ：返回参数在二进制下末尾 0 的个数。
__buitlin_clz / __buitlin_clzll ：返回参数在二进制下前导0 00的个数。
__builtin_ffs / __buitlin_ffsll ：返回参数在二进制下最后一个1在第几位（从后往前）。注：一般来说，builtin_ffs(x) = __builtin_ctz(x) + 1。当x = 0 时，builtin_ffs(x) = 0。
__builtin_parity / __builtin_parityll ：返回参数在二进制下1 的个数的奇偶性（偶：0，奇：1），即__builtin_parity(x) = __builtin_popcount(x) % 2。

4. 位运算的应用

4.1 两数交换

void swap(int& a, int& b)
{
    if(a == b) return ; // 避免 x ^ x = 0
	a ^= b ^= a ^= b;
}

4.2 gcd

位运算交换法扩展：超快GCD

int gcd(int a, int b)
{
	if(b) while(b ^= a ^= b ^= a %= b);
	return a;
}

4.3 两数平均数（防溢出）

int average1(int x, int y)
{
	return (x >> 1) + (y >> 1) + (x & y & 1);
}

int average2(int x, int y)
{
	return (x & y) + ((x ^ y) >> 1);
}

4.4 判断一个数是否为 2 的整数次幂

bool ispowof2(int x)
{
    // x & x - 1 把二进制的右数第一个 1 改为 0 
    //故当 x 为 2的幂的时候， x & x - 1 = 0
    return x > 0 && !(x & x - 1);
}

4.5 二进制枚举子集

先来介绍一下「子集」的概念。

子集：如果集合 A 的任意一个元素都是集合 S 的元素，则称集合 A 是集合 S 的子集。可以记为 A。

对于集合{ 0 , 1 , … , n − 1 }，我们使用一个N 位的二进制整数 S 来表示它的一个子集。从右往左第 i 位表示子集是否包含了 i 。容易发现，对于任意子集 S ，S ∈ [ 0 ,

− 1 ]，且对于任意S ∈ [ 0 ,

− 1 ] ，S 都是{ 0 , 1 , … , n − 1 }的一个有效子集。

下面我们来讲这种子集表示的具体操作：

空集：0
满集：

-1 （ n 个 1）

集合S 的元素个数：__builtin_popcount(S)或__builtin_popcountll(S)
集合S 是否包含i ：S >> i & 1
将i 加入S（操作前 S 是否包含 i 不影响操作结果）：S |= 1 << i
将i 从S 中删除（操作前 S 必须包含 i ）：S ^= 1 << i
将 i 从 S 中删除（操作前S SS是否包含 i 不影响操作结果）：S &= ~(1 << i)
S 和 T 的交集（S 和 T 都包含的集合）：S & T
S 和 T 的并集（S 和 T 中有任意一个包含的集合）：S | T
S 和 T 的差集（S 和 T 中恰好有一个包含的集合）：S ^ T

🌿 枚举N 个元素的所有子集

这个很简单，直接枚举S ∈ [ 0 ,

− 1 ] ，代码如下：

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    printf("n = %d\n", n);
    for (int s = 0, full = (1 << n) - 1; s <= full; s++)
    {
        printf("Subset %d:", s + 1);
        for (int i = 0; i < n; i++)
            if (s >> i & 1)
                printf(" %d", i);
        putchar('\n');
    }
    return 0;
}

5、位运算例题

1. 判定字符是否唯一

题目描述：实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

思路： 遍历字符串，将每个字符转化为数字即可，然后2.3 中位运算的常用操作即可

class Solution {
public:
    bool isUnique(string astr) {
        int x = 0; 
        for (auto e : astr)
        {
            // 1. 字符转化为数字
            int i = e - 'a';    
            // 2. 判断字符是否已经出现
            //if (x & (1 << i)) //取末尾 i 位
            //    return false; 
            // 上下两种都可以判断是否有重复数字出现
            if (((x >> i) & 1) == 1)  //右数 i 位
                return false;
            else x |= (1 << i);  //把右数 i 位变成 1
        }
        return true;
    }
};

2. 丢失的数字

题目描述：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数

思路： 遍历数组，将数字与[1,n]异或即可，用到了 x ^ x = 0，x ^ 0 = x 的性质

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 1; i <= nums.size(); i++) ret ^= i;
        for (auto x : nums)
        {
            ret ^= x;
        }
        return ret;
    }
};

3. 两整数之和

题目描述：给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

思路： 二进制异或运算，无进位相加，如下：

class Solution {
public:
    int getSum(int a, int b) {
        while (b)
        {
            int x = a ^ b; //先存储无进位相加结果
            b = (a & b) << 1; // 算出进位
            a = x;
        }
        return a;
    }
};

4. 只出现一次的数字

题目描述：给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

思路： 遍历数组，0异或数组里的每个值即可，最后的值就是出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        for(auto e : nums)
        {
            x ^= e;
        }
        return x;
    }
};

5. 只出现一次的数字 II

题目描述：给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 三次。请你找出并返回那个只出现了一次的元素。

思路： 由于数组中的元素都在 int（即 32 位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 0 还是 1。

具体地，考虑答案的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。
对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。
因此：答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和 % 3 。

这样一来，对于数组中的每一个元素 x，我们使用位运算 (x >> i) & 1 得到 x 的第 i 个二进制位，并将它们相加再对 3 取余，得到的结果一定为 0 或 1，即为答案的第 i 个二进制位。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) { //依次修改 ans 中的每一位
            int cnt = 0; //统计第 i 位 1 的数目
            for (int x : nums)
            {
                cnt += ((x >> i) & 1); // 获得 第 i 位上的1
            }
            if (cnt % 3) // cnt只有两种可能 1，3
                ans |= (1 << i); // 把ans的右数第i位变成1
        }
        return ans;
    }
};

6. 只出现一次的数字 III

题目描述：给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

思路： 假设数组 nums 中只出现一次的元素分别是 x1 和 x2。如果把 nums 中的所有元素全部异或起来，得到结果 x，那么一定有：x = x1 ⊕ x2 （其中 ⊕ 表示异或运算） 这是因为 nums 中出现两次的元素都会因为异或运算的性质 a⊕b⊕b=a 抵消掉，那么最终的结果就只剩下 x1 和 x2 的异或和 x 。注：这里的 x 肯定不为0，如果 x = 0，那么 x1 = x2，与所给条件冲突。因此，我们可以使用位运算 x & -x 取出 x 的二进制表示中最低位那个 1，设其为第 l 位，那么 x1 和 x2 中的某一个数的二进制表示的第 l 位为 0，另一个数的二进制表示的第 l 位为 1。在这种情况下，x1⊕x2 的二进制表示的第 l 位才能为 1。这样一来，我们就可以把 nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。可以发现：

对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
对于任意一个在数组 nums 中只出现了一次的元素，即 x1 和 x2，它们会被包含在不同类中。

因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 x1，另一类会得到 x2。这样我们就找出了这两个只出现一次的元素。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorsum = 0; 
        for (int x : nums) xorsum ^= x;

        // 写法一：
        int lowbit = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int num1 = 0, num2 = 0;
        for (int x : nums) {
            if (x & lowbit) num1 ^= x;
            else num2 ^= x;
        }

        // 写法二：
        int diff = 0;
        while (1) {
            if (((xorsum >> diff) & 1) == 1) break;
            else diff++;
        }
        int num1 = 0, num2 = 0;
        for (int x : nums) {
            if (((x >> diff) & 1) == 1) num1 ^= x;
            else num2 ^= x;
        }

        return { num1,num2 };
    }
};

7. 消失的两个数字

题目描述：给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？以任意顺序返回这两个数字均可。

思路： 该题的思想主要用到了丢失的数字 + 只出现一次的数字 III 假设 ans = 0，先让 ans先数组内的所有元素，再让 ans 异或 [1, n]内所有元素，此时的ans 与只出现一次的数字 III中的 xorsum相同，也是两个只出现一次的数字的异或（即丢失的那两个数字）

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 异或所有数
        int xorsum = 0;
        for (int x : nums) xorsum ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) xorsum ^= i;

        // 2. 找出a，b比特位不同的那一位
       int diff = 0;
        while (1) {
            if (((xorsum >> diff) & 1) == 1) break;
            else diff++; 
        }

        // 3. 根据最低比特位的不同，将所有的数分为两类来异或,需要进行两次，这样就可以把问题转化求只出现一次的数字III
        int num1 = 0, num2 = 0;
        for (int x : nums) {
            if (((x >> diff) & 1) == 1) num1 ^= x;
            else num2 ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (((i >> diff) & 1) == 1) num1 ^= i;
            else num2 ^= i;
        }
        return { num1,num2 };
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

c++