【算法】位运算题目总结

位运算

基础结论

x & (-x) :   得到x的二进制序列当中,最右边的一个比特位1对应的值  ==> 写法2： a&(~a+1)
x & (x - 1): 将x的二进制序列当中,最右边的一个1变为0
x | (x + 1): 将x的二进制序列当中,最右边的一个0变为1
1
2
3

---

Pow(x，n)

https://leetcode.cn/problems/powx-n/

快速幂的思想：

如果n为负数：要将n转为正数，x取倒数

• x^(-n) == $(1/x{)}^n$， 如果n = INT_MIN ，则-n就会溢出，所以要定义一个变量y为long类型接收n变量之后再取倒数， 本来要计算$x^n (n为负数) $转化为求: $(1/x{)}^y$

定义类型为double的变量res记录答案，x每次都乘自己

• 如果y的二进制位为1: 就让res累乘x
• 而x每次都累乘自己，y每次都右移1位
• 循环结束条件: y不为0 最后res记录的就是x^y的结果.

class Solution {
public:
    double myPow(double x,int n) {
        //如果n是负数：x的n次方 ==> (1/x)的n次方 
        //例子：2的-9次方 = 二分之一的9次方
        //n需要提升为long类型，否则如果n为INT_MIN，那么n = -n就会溢出
        if(x == 0.0) return x;
        long y = n;  //计算x^y
        if(y < 0)
        {
            x = 1/x;
            y = -y;
        }
        double res = 1.0;
        //例如：求2^9  x^y
        //9的二进制序列为：1     0    0    1
        //              2^8  2^4  2^2  2^1  只有bit为1的才需要统计到结果当中  每次计算都要累乘x
        //2^9 = 2^8 * 2^1  当y的bit为1的时候，累乘当前的值
        while(y != 0)
        {
            if(y & 1) //只有bit为1的才需要统计到结果当中
            {
                res *= x;
            }
            x *= x;
            y >>= 1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

方法2：递归

2^6 => 2^3 * 2^3 * 2^0
2^3 => 2^1 * 2^1 * 2^1
规律：mypow(x,n) =  myPow(x, n / 2) *  myPow(x, n / 2) *  myPow(x, n % 2)   针对n为负数也适合
1
2
3

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0) return 1.0;
        if(n == 1) return x;
        if(n == -1) return 1/x;
        double half = myPow(x,n / 2);
        double rest = myPow(x,n % 2);
        return rest * half *half;
    }
};
1
2
3
4
5
6
7
8
9
10
11

---

位运算实现加法

https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/description/

首先：a^b：本质是a和b的无进位相加 (a&b)<< 1 ：得到a和b相加的进位信息，所以循环终止条件：进位信息为0

class Solution {
public:
    int add(int a, int b) {
      while(b != 0) //将a当成无进位相加,b当成进位
      {
        int sum = a ^ b;
        int carry = (a & b) << 1; //最好写成： (unsigned int)(a & b) << 1 因为进位没有负数
        a = sum;
        b = carry;
      }
      return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

递归版本：

class Solution {
public:
    int process(int sum,int carry)
    {
      return carry == 0 ? sum : process(sum ^ carry,(sum&carry)<<1);
    }
    int add(int a, int b) {
      return process(a,b);
    }
};
1
2
3
4
5
6
7
8
9
10

---

位运算实现减

$a-b$ 相当于 $a+(-b)$ ，由于不能使用减号，而$-b=b按位取反+1$，所以可以复用上面的位运算实现加法

//得到相反数
int negNum(int n)
    return add(~n, 1);
//减法
int minus(int a, int b)
    return add(a, negNum(b));//a+b的相反数
1
2
3
4
5
6

---

位运算实现乘

$a\ast b$ ==>本质是$a$每次左移一位，$b$每次右移一位，如果当前$b$这一位是1，那么就需要把当前$a$的值累加到结果当中

int Add(int a, int b)
{
	return b == 0 ? a : Add(a ^ b, (a & b) << 1);
}
int Multi(int a, int b)
{
	long res = 0;//防止结果溢出

	while (b != 0)
	{
		if (b & 1) //b的最后一位为1,那么就累加当前a移位之后的结果
		{
			res = Add(a, res);
		}

		a = (size_t)a << 1;
		b = (size_t)b >> 1;//如果b是负数,不强转为无符号整型会导致b为-1,造成死循环
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

坑点：如果b是负数，那么b每次右移，因为最高位补的是符号位，所以最后会导致b变成-1，而不是0，造成死循环，更改方法：使用无符号右移：右移时不考虑符号问题，即无论右移正数还是负数，其最高位都是补0

• 只需要：先将要进行右移的数转换成无符号类型，然后执行普通右移即可

---

只出现一次的数字

https://leetcode.cn/problems/single-number/

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

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto& x:nums)
            ans ^= x;
        return ans;
    }   
};
1
2
3
4
5
6
7
8
9

---

只出现一次的数字 II

https://leetcode.cn/problems/single-number-ii/

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

方法1：需要使用额外空间

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int bits[32] = {0};
        for(auto& x:nums)
        {
            //判断x的32个bit
            for(int i = 0;i<32;i++)
            {
                if( (x>>i) & 1)
                    bits[i]++;
            }
        }
        int ans = 0;
        for(int i = 0;i<32;i++)
        {
            if(bits[i] % 3 == 1)
                ans |= (1 << i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最优解：不需要额外空间保存比特位

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0;i<32;i++)
        {
            int count = 0;
            for(auto& x:nums)
            {
                if((x >> i) & 1) count++;
            }
            if(count % 3 == 1) 
                ans |= (1 << i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

位1的个数

https://leetcode.cn/problems/number-of-1-bits/

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数

方法1：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n)
        {
            n  = n &(n-1);
            count++;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

方法2：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n)
        {
            n  -= n&(-n); //n = n - (n&(-n))
            count++;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

方法3：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0; //统计0的个数
        while(n != -1)
        {
            n = n | (n+1);
            count++;
        }
        return 32-count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

---

颠倒二进制位

https://leetcode.cn/problems/reverse-bits/

颠倒给定的 32 位无符号整数的二进制位

本质是将比特位反转：1100 -> 0011

• 将最低位放到最高位，最高位放到最低位

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        //本质是将n的二进制序列反转
        uint32_t ans = 0;
        for(int i = 0;i<32;i++)
        {
            ans |= (n&1) <<(31 - i);
            n = n >>1;
        } 
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---

只出现一次的数字 III

https://leetcode.cn/problems/single-number-iii/

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

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int eor = 0;
        for(auto& x:nums)
            eor ^= x;
        
        int rightOne = eor & (-eor);//有可能溢出！ 如果eor为INT_MIN,那么-eor就溢出了！
        int rightOne = eor == INT_MIN ? INT_MIN : eor & (-eor);
        int ans = 0; 
        for(auto& x:nums)
        {
            if(x & rightOne)
                ans ^= x;
        }
        return {ans,eor ^ ans};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

判定字符是否唯一

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。$s[i]$仅包含小写字母

做法1：哈希表

做法2：因为仅包含小写字母，所以可以使用一个整形变量的32位来判断某个字符是否唯一，每个字符映射到该变量的$ch{-}^{\prime }{a}^{\prime }$比特位中

class Solution {
public:
    bool isUnique(string astr) {
        int bits = 0;
        for(auto& ch:astr)
        {
            int index = ch - 'a';//当前字符映射的比特位
            if(bits& (1 << index) ) //鸽巢原理,如果当前比特位已经被映射为1,所以字符重复出现
                return false;
            bits |= ( 1<< index );
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---