位运算

2020-08-05 本文已影响0人 juriau

常用的位运算符号包括

1.逻辑运算符

  "&"：按位与
  "|"：按位或
  "～"：取反
  "^"：按位异或

异或的特点

任何数字与自己异或结果是0；/ 两个相同数字异或的结果是0。
任何数字与0异或得到数字本身。

2.移位运算符

  "<<"：算术左移
  ">>"：算术右移

左移规则：高位丢弃，低位补0
右移规则：

有符号数-算数右移：高位补最高有效位（符号位）的值，低位丢弃；
无符号数-逻辑右移：高位补0，低位丢弃；

一、目录

461.汉明距离
190.颠倒二进制位
136.只出现一次的数字
268.缺失数字
不用临时变量实现swap(a, b)
137.只出现一次的数字 II
260.只出现一次的数字 III
231.2的幂
342.4的幂
338.比特位计数

二、题目

461.汉明距离（即不同位的个数）

思路：使用异或运算符可以轻松解决。

int hammingDistance(int x, int y) {
    int diff = x^y, ans = 0;
    while (diff) {
        ans += diff & 1;
        diff >>= 1;
    }
    return ans;
}

190.颠倒二进制位

思路：每次获得最后一位，然后一个往左移，一个往右移。

uint32_t reverseBits(uint32_t n) {
    uint32_t ans = 0;
    for (int i=0; i<32; i++) {
        ans = ans<< 1;
        ans += n & 1; 
        n = n>>1;
    }
    return ans;
}

136.只出现一次的数字

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

思路：利用异或的特点

任何数字与自己异或结果是0；
任何数字与0异或可以得到这个数字本身。

int singleNumber(vector<int>& nums) {
    int ans = 0;
    
    for (int a : nums) {
        ans ^= a;
    }
    return ans;
}

268.缺失数字

方法1：排序。既然是查找，那就先排序再查找。

方法2：哈希表。用一个连续的数组当作字典。

方法3：数学方法。等差数组求和公式： ( 首项 + 末项 ) * 项数 / 2 = 数列和

方法4：位运算-异或。利用异或的特点：两个相同元素的异或等于0。

先获得[0..n]的异或值，在与nums异或，即得到缺失值。这两步可以结合在一起。

int missingNumber(vector<int>& nums) {
    int lens = nums.size();
    int ans = lens;
    for (int i=0; i<lens; i++) {
        ans ^= i ^ nums[i];
    }
    return ans;
}

不用临时变量实现swap(a, b)

方法1：位运算异或

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

方法2：算术运算操作直接赋值

void mySwap1(int& a, int& b){
    b = a + b;
    a = b - a;
    b = b - a;
}

137.只出现一次的数字 II

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

思路：ans的每一位等于数组中的元素每一位除3的余数。

1.将每个数的第一位相加除以3，ans左移，元素右移
2.再把ans颠倒一下

int singleNumber(vector<int>& nums) {
    int ans2 = 0;
    
    // 遍历每一位
    for (int i=0; i<32; i++) {
        ans2 <<= 1;
        int temp = 0;
        for (int i=0; i<nums.size(); i++) {
            temp += nums[i] & 1;
            nums[i]>>=1;
        }

        ans2 += temp % 3;
    }
    
    // 颠倒
    int ans = 0;
    for (int i=0; i<32; i++) {
        ans <<= 1;
        ans += ans2 & 1;
        ans2 >>= 1;
    }
    return ans;
}

260.只出现一次的数字 III

题目描述：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

思路：
将数组中全部元素异或，结果其实就是那两个元素的异或；
因为那两个元素不相等，所以肯定有某一位为1，那么就用那一位来划分数组。
然后分别在两个数组中查找。（这就回到了136.只出现一次的数字）

vector<int> singleNumber(vector<int>& nums) {
    // 1.求所有元素的异或
    int diff = 0;
    for (int a : nums) {
        diff ^= a;
    }
    
    // 2.找到第一个为1的位数
    int flag = 1;
    while ((diff&1) != 1) {
        diff >>= 1;
        flag <<= 1;
    }
    
    // 3.以flag划分数组,并查找在两个数组中分别查找那个值
    int ans1 = 0, ans2 = 0;
    for (int a: nums) {
        if ((a & flag)== 0) {
            ans1 ^= a;
        }else{
            ans2 ^= a;
        }
    }
    
    return {ans1, ans2};
}

231.2的幂

思路：数字的二进制只有一个1存在

bool isPowerOfTwo2(int num) {
    if (num <= 0) return false;
    
    for (int i=0; i<32; i++) {
        if ((num&1) == 1) {
            if (num>>1 == 0) {
                return true;
            }else{
                return false;
            }
        }
        num>>=1;
    }
    return false;
}

342.4的幂

思路：数字的二进制只有一个1存在，且在奇数位。

338.比特位计数

如果二进制位的最后一位为1，那么dp[i] = dp[i-1] + 1;
如果二进制位的最后一位为0，那么dp[i] = dp[i>>1]。

vector<int> countBits(int num) {
    vector<int> dp(num+1, 0);
    for (int i=1; i<=num; i++) {
        if ((i & 1) == 1) dp[i] = dp[i-1] + 1;
        else dp[i] = dp[i>>1];
    }
    return dp;
}

位运算