【算法】位运算

目录

01.?整数在内存中的存储

01.1?无符号整数的表示方法

01.2?有符号整数的表示方法

02. 移位操作符

02.1 左移操作符

1 << n = 2的n次幂

02.2 右移操作符

n >> 1 和 n / 2

03. 位操作符

03.1 按位与

n & 1 和 n % 2

n >> i & 1

n & (n - 1)

03.2 按位或

03.3 按位异或

a ^ a = 0? ? 0 ^ a = a

1. 比特位计数（简单）

2. 只出现一次的数字（简单）

3. 只出现一次的数字 II（中等）

4. 最大单词长度乘积（中等）

---

01.?整数在内存中的存储

整数在计算机中以二进制数表示。

整数表示的范围在头文件limits.h中定义。

01.1?无符号整数的表示方法

unsigned int a = 25;

00000000000000000000000000011001? ? ? ?1×2^4+1×2^3+0×2^2+0×2^1+1×2^0=25

高位<------------------------------------->低位

n位可以表示的无符号整数的范围是0~

无符号整数类型	最小值	最大值
unsigned char	0	255
unsigned short	0	65535
unsigned int	0	4294967295

01.2?有符号整数的表示方法

有符号整数有3种二进制表示方法，即原码、反码和补码。最高位为符号位，0表示正数，1表示负数，其余为数值位。在计算机中整数以补码的形式存储。

原码：直接将数值按照正负数的形式翻译成二进制。

正数的反码、补码与原码相同。负数的反码、补码要经过如下计算。

反码：将原码的符号位不变，其他位依次按位取反。补码：反码+1就得到补码。

int a = -25;
// 原码：10000000000000000000000000011001
// 反码：11111111111111111111111111100110
// 补码：11111111111111111111111111100111

8位有符号整数的取值范围如下图所示：（补码10000000不表示-0，表示-128）

?n位可以表示的无符号整数的范围是~

有符号整数类型	最小值	最大值
signed char	-128	127
signed short	-32768	32767
signed int	-2147483648	2147483647

02. 移位操作符

02.1 左移操作符

整数的二进制表示有3种：原码、反码、补码。正整数的原码、反码、补码相同。负整数的反码是原码符号位不变，其他位按位取反，补码是反码+1。整数在内存中存储的是补码。

+7：
原码：00000000000000000000000000000111
反码：00000000000000000000000000000111
补码：00000000000000000000000000000111
-7：
原码：10000000000000000000000000000111
反码：11111111111111111111111111111000
补码：11111111111111111111111111111001

移位规则：左边抛弃，右边补0

int a = 7;
int b = a << 1;

0[00000000000000000000000000001110]

int a = -7;
int b = a << 1;

1[11111111111111111111111111110010]

1 << n = 2的n次幂

int a = 1;

int b = a << 1;

0[00000000000000000000000000000010]=2的1次幂

int b = a << 2;

00[00000000000000000000000000000100]=2的2次幂

int b = a << 3;

000[00000000000000000000000000001000]=2的3次幂

所以，1<<n=2的n次幂

02.2 右移操作符

移位规则：

• 逻辑移位：左边补0，右边抛弃
• 算术移位：左边补原符号位，右边抛弃（常见编译器都是算术移位）

算术移位：

int a = 7;
int b = a >> 1;

[00000000000000000000000000000011]1

int a = -7;
int b = a >> 1;

[11111111111111111111111111111100]1

n >> 1 和 n / 2

n为非负数时，n>>1=n/2??????????10>>1=5??????10/2=5，0>>1=0??????0/2=0

n为负偶数时，n>>1=n/2??????????-10>>1=-5??-10/2=-5

n为负奇数时，n>>1=n/2-1???????-5>>1=-3??????-5/2=-2（n>>1是n除以2向下取整，n/2是n除以2向上取整）

03. 位操作符

&按位与，|按位或，^按位异或

位操作符通过逐位比较两个运算对象，生成一个新值。对于每个位：

• &：两个操作数相应的位都为1，结果为1
• |?：两个操作数相应的位至少有一个为1，结果为1
• ^：两个操作数相应的位相同为0，相异为1

03.1 按位与

int a = 3;
int b = -5;
int c = a &?b;

 3的补码：00000000000000000000000000000011
-5的补码：11111111111111111111111111111011
 c的补码：00000000000000000000000000000011

n & 1 和 n % 2

n为非负数时，n&1=n%2

• n为奇数：n&1=1? n%2=1
• n为偶数：n&1=0? n%2=0

n为负数时，

• n为奇数：n&1=1? n%2=-1
• n为偶数：n&1=0? n%2=0

n >> i & 1

n>>i&1用来获取二进制的每一位。

以75（000000000000000000000001001011）为例：

要想获取最后一位，就要&1，即

 000000000000000000000001001011
&000000000000000000000000000001
=000000000000000000000000000001
=1

要想获取倒数第二位，就要>>1，再&1，即

75>>1=[000000000000000000000000100101]1

 000000000000000000000000100101
&000000000000000000000000000001
=000000000000000000000000000001
=1

要想获取倒数第三位，就要>>2，再&1，即

75>>2=[000000000000000000000000010010]11

 000000000000000000000000010010
&000000000000000000000000000001
=000000000000000000000000000000
=0

n & (n - 1)

n-1表示将n的二进制位最右边的1变为0，该1右边的所有0都变为1。

n&(n-1)表示将n的二进制位最右边的1变为0，其余位不变。

24：? ? ?? 00000000000000000000000000011000

23：? ? ???00000000000000000000000000010111

24&23：00000000000000000000000000010000

如果n&(n-1)为0，则n是2的幂。

+2：? 00000000000000000000000000000010

+1：? 00000000000000000000000000000001

+4：? 00000000000000000000000000000100

+3：? 00000000000000000000000000000011

2&1：00000000000000000000000000000000

4&3：00000000000000000000000000000000

03.2 按位或

int a = 3;
int b = -5;
int c = a |?b;

 3的补码：00000000000000000000000000000011
-5的补码：11111111111111111111111111111011
 c的补码：11111111111111111111111111111011

03.3 按位异或

int a = 3;
int b = -5;
int c = a ^?b;

 3的补码：00000000000000000000000000000011
-5的补码：11111111111111111111111111111011
 c的补码：11111111111111111111111111111000

a ^ a = 0? ? 0 ^ a = a

a^a=0：

如，3^3=00000011^00000011=00000000

0^a=a：

如，0^3=00000000^00000011=00000011

不创建临时变量实现两个数的交换：

#include <stdio.h>

int main()
{
	int a = 10;
	int b = 20;
	a = a ^ b; // 10^20
	b = a ^ b; // 10^20^20=10^0=10（^操作符支持交换律）
	a = a ^ b; // 10^20^10=0^20=20
	printf("a = %d b = %d\n", a, b);
	return 0;
}

1. 比特位计数（简单）

方法一：

vector<int> countBits(int n)
{
    vector<int> ret(n + 1, 0); // 创建n+1个元素的数组，将所有元素初始化为0

    // 0的二进制形式中没有1，现在ret[0]的值已经为0，所以可以从1开始计算
    for (int i = 1; i <= n; i++)
    {
        int n = i;
        while (n)
        {
            ret[i]++;
            // 每进行一次n&(n-1)的操作，就能去掉最后一个1，去掉所有的1时（n为0时）结束循环
            // 二进制位1的个数=循环的次数
            n = n & (n - 1);
        }
    }

    return ret;
}

如果一个整数共有k位，对于每个整数，while循环最多循环k次，每次循环的时间复杂度为O(1)，因此上述代码的时间复杂度为O(kn)。

方法二：

vector<int> countBits(int n)
{
    vector<int> ret(n + 1, 0); // 创建n+1个元素的数组，将所有元素初始化为0

    // 0的二进制形式中没有1，现在ret[0]的值已经为0，所以可以从1开始计算
    for (int i = 1; i <= n; i++)
    {
        // i的二进制形式中1的个数比i&(i-1)的二进制形式中1的个数多1个
        ret[i] = ret[i & (i - 1)] + 1;
    }

    return ret;
}

上述代码的时间复杂度为O(n)。

方法三：

如果正整数i是偶数，那么i相当于将i/2左移一位的结果，因此偶数i和i/2的二进制形式中1的个数是相同的。

如果正整数i是奇数，那么i相当于将i/2左移一位后，再将最右边一位设为1的结果，因此奇数i的二进制形式中1的个数比i/2的二进制形式中1的个数多1个。

例如，

3：00000000000000000000000000000011

6：00000000000000000000000000000110

7：00000000000000000000000000000111

vector<int> countBits(int n)
{
    vector<int> ret(n + 1, 0); // 创建n+1个元素的数组，将所有元素初始化为0

    // 0的二进制形式中没有1，现在ret[0]的值已经为0，所以可以从1开始计算
    for (int i = 1; i <= n; i++)
    {
        // ret[i] = ret[i / 2] + (i % 2);
        // 当i为非负数时，i/2=i>>1，i%2=i&1，且位运算比除法运算和取余运算效率高
        // 代码优化如下：
        ret[i] = ret[i >> 1] + (i & 1);
    }

    return ret;
}

上述代码的时间复杂度为O(n)。

2. 只出现一次的数字（简单）

a ^ a = 0? ? 0 ^ a = a

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 4^1^2^1^2=4^0=4
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans ^= nums[i];
        }
        return ans;
    }
};

3. 只出现一次的数字 II（中等）

将数组中只出现一次的元素剔除，剩下的元素都出现了三次，将这些元素的各个数位的值相加，各个数位的和一定是3的倍数。

将数组中所有元素的各个数位的值相加：

• 如果某位的和能被3整除，说明只出现1次的元素该位是0
• 如果某位的和被3除余1，说明只出现1次的元素该位是1

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        vector<int> bitSums(32, 0); // int型有32位
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < 32; j++)
            {
                bitSums[j] += nums[i] >> (31 - j) & 1;
            }
        }
        int ret = 0;
        for (int i = 0; i < 32; i++)
        {
            ret = (ret << 1) + bitSums[i] % 3;
        }
        return ret;
    }
};

4. 最大单词长度乘积（中等）

用int型整数记录某个字符串中出现的字符。

如果字符串中包含'a'，那么整数最右边的数位为1，

如果字符串中包含'b'，那么整数倒数第2的数位为1 ……

用flags[i]记录words[i]出现的字符，如果flags[i] & flags[j] == 0，那么words[i]和words[j]没有相同字符，此时可以计算它们长度的乘积，然后和之前计算过的最大值比较。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> flags(n, 0);
        // 设置flags[i]
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < words[i].size(); j++)
            {
                flags[i] |= 1 << (words[i][j] - 'a');
            }
        }
        // 找没有相同字符的words[i]和words[j]
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if ((flags[i] & flags[j]) == 0)
                {
                    int prod = words[i].size() * words[j].size();
                    ans = max(ans, prod);
                }
            }
        }
        return ans;
    }
};