专题复习：位运算

本文主要是介绍专题复习：位运算，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

注意：位运算& ^等 一定 要加括号 否则会 可能由于运算符优先级的问题导致意想不到的结果

(n&(n-1))可以消除n的二进制中最右边的1

(n&(-n) )可以只保留二进制中最右边的1

剑指 Offer 15. 二进制中1的个数

方法一： 进行移位操作

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        for(int i = 0; i < 32; i++)
        {
            if(n>>i&1) count++;
        }
        return count;
    }
};

方法二：对方法一进行优化，因为有的n不需要移位32位

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n)
        {
            count += (n&1);
            n>>=1;
        }
        return count;
    }
};

方法三：不是n进行移位操作，而是1进行移位操作

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n)
        {
            if(n&0x1) res++;
            n = n>>1;
        }
        return res;
    }
};

方法四：利用n&n-1 可以消除 n中最右边的1

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n)
        {
            n&=n-1;
            count++;
        }
        return count;
    }
};

方法五：查表法

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        int table[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
        while(n)
        {
            count += table[n&0xf];
            n>>=4;
        }
        return count;
    }
};

方法6：二进制平行算法

class Solution {
public:
    int hammingWeight(uint32_t n) {
        n = (n&0x55555555)+((n>>1)&0x55555555); //n为32位，相邻两位进行相加
        n = (n&0x33333333)+((n>>2)&0x33333333); // 相当于2位为一个单位， 相邻两个单位相加
        n = (n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f); // 相当于4位为一个单位， 相邻两个单位相加
        n = (n&0xff00ff)+((n>>8)&0x00ff00ff);   // 相当于8位为一个单位， 相邻两个单位相加
        n = (n&0xffff)+((n>>16)&0xffff);        //相当于16位为一个单位， 相邻两个单位相加
        return n;
    }
};

leetcode231. 判断一个数是否为2 的幂

思路：一个数 如果是2的幂，那么该数的二进制中质保函1个1.

方法一： 利用移位来计算n中1的个数

class Solution {
    int count1Num(int n) //计算n 若用二进制表示时 其中1的个数
    {
        int count = 0;
        while(n)
        {
            count += (n&1);
            n>>=1;
        }
        return count;
    }
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && count1Num(n) == 1;
    }
};

 方法二：利用n&(n-1)可以去掉 n中最右边的1

这种方法超级简单

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n&(n-1))==0;
    }
};

剑指 Offer 56 - II. 数组中数字出现的次数 II

其中一个数只出现一次，另外的数都出现三次，找到这个出现一次的数。

统计数组中，所有元素在 32位中每一位 1出现的次数，如果某一位上1出现的次数 count1Num%3 ==1，说明 该位上的1属于那个只出现一次的数。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < 32; i++)
        {
            int count1Num = 0;
            for(int j = 0; j < nums.size(); j++)
            {
                count1Num += (nums[j] >> i)&1;
            }
            if(count1Num % 3 != 0)
            {
                res |= (1<<i);
            }
        }
        return res;
    }
};

对于数组中，如果只有一个数字出现一次，其他数字都出现奇数次n（n > 1），我们可以用下面代码来找到只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < 32; i++)
        {
            int count1Num = 0;
            for(int j = 0; j < nums.size(); j++)
            {
                count1Num += (nums[j] >> i)&1;
            }
            if(count1Num % n != 0)
            {
                res |= (1<<i);
            }
        }
        return res;
    }
};

对于数组，如果只有一个数字出现一次，其他数字都出现偶数次，我们只需要把所有数字异或一
遍即可找到出现一次的数字。

对应leetcode136. 只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0;
        int res = 0;
        for(int i = 0; i < size; i++)
        {
            res ^= nums[i];
        }
        return res;

    }
};

leetcode 1442. 形成两个异或相等数组的三元组数目

思路：让 a = b 即 a ^ b = 0 即：

 我 们 只 需 要 从 数 组 arr 中 找 到 一 些 连续的 元 素 ， 他 们 的 异 或 结 果 等
于0即可。

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int count = 0;
        int size = arr.size();
        for(int i = 0; i < size - 1; i++)
        {
            int temp = arr[i];//注意 起始值为arr[i]
            for(int k = i + 1; k < size; k++)
            {
                temp ^= arr[k];
                if(temp == 0)
                {
                    count += k - i;
                }
            }
        }
        return count;
    }
};

剑指 Offer 53 - II. 0～n-1中缺失的数字

方法一：利用位运算 nums[i] &i

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int size = nums.size();
        int res = 0;
        for(int i = 0; i < size; i++)
        {
            res ^= nums[i]^i;
        }
        return res^size;
    }
};

方法二：暴力遍历

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i]!=i) return i;
        }
        return nums.size();
    }
};

方法三：利用二分法

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int med = (left + right)/2;
            if(nums[med] == med) left = med + 1;
            else right = med - 1;
        }
        return left;
    }
};

leetcode461:https://leetcode-cn.com/problems/hamming-distance/ 汉明距离
 

class Solution {
public:
    int hammingDistance(int x, int y) {

        int temp = x^y;//在求temp对应的二进制中1的个数
        int res = 0;
        while(temp)
        {
            if(temp & 1 == 1) res++;
            temp >>= 1;
        }
        return res;
    }
};

剑指 Offer 56 - I. 数组中数字出现的次数 

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int size = nums.size();
        int temp = 0;
        for(int i = 0; i < size; i++)
        {
            temp ^= nums[i];
        }
        temp &= -temp;
        int res1 = 0, res2 = 0;
        for(int j = 0; j < size; j++)
        {
            if((temp & nums[j]) == 0)//(temp & nums[j])注意要加括号
            {
                res1 ^= nums[j];
            }
            else
            {
                res2 ^= nums[j];
            }
        }
        return {res1, res2};

    }
};

位运算求最小的2的n次方

 方法一：

int lowPower(int n)
{
    int temp = 1;
    while(n > temp)
    {
       temp <<= 1;
    }
    return temp;
}

方法二：利用位运算

举例：

 所 以 一 种 最 简 单 的 方 式 就 是 通 过 移 位 运 算 ， 把 53 最 左 边 的 1 全 部 往 右 边 铺 开 ， 就 变 成 了00111111，然后再加1就变成了了01000000。

但 是 这 里 有 个 小 问 题 就 是 ， 如 果 x 本 来 就 是 2 的 n 次 方 ， 比 如 x 是 16 ， 运 算 的 结 果 就 会 变成 32 ， 而我 们 实 际 要 求 的结果应该是16 。 所 以 这 里 我 们 可 以 先 让 x-1 ， 然 后 再 进 行 运 算。

int lowPower(int n)
{
    n = n - 1;
    //将最高位1之后的都变为1
    n |= (n>>1);
    n |= (n>>2);
    n |= (n>>4);
    n |= (n>>8);
    n |= (n>>16);
    return n+1;
}

不使用“+”,“-”实现四则运算
(1) 加法 leetcode371：https://leetcode-cn.com/problems/sum-of-two-integers/

a = 3  011

b = 5 101    a&b = 001   a&b<<1 表示有进位      a^b = 110  表示除了进位剩下的 位的数

（a&b<<1）  + (a^b) = a + b = 8 又不能使用+ ，因此可以利用递归实现。

方法一：递归的写法存在问题：

如果是负数 leetcode左移时报错 runtime error: left shift of negative value
具体原因是运行时库的问题？
可以转换成无符号整型进行左移

注意：为了解决上述问题，要负数转化为unsigned int类型，因此 ((unsigned int)a&b)<<1

class Solution {
public:
    int getSum(int a, int b) {
        if(a == 0 ||b == 0) 
            return a^b;
        return getSum(a^b, ((unsigned int)a&b)<<1);
    }
};

 方法二： 

class Solution {
public:
    int getSum(int a, int b) {
        while(b)
        {
            unsigned int temp = ((unsigned int)(a&b))<<1;
            a ^= b; 
            b = temp;
        }
        return a;
    }
};

（2）不用 “--”号 实现减法

方法一：利用递归

//实现 a - b
int substract(int a, int b)
{
   if(b == 0) return a;
   int c = a&b; //找到a和b 相同位的1
   a ^= c;      //去除a中 与b相同的部分
   b ^= c;      //去除b中 与a相同的部分
   substract(a|b, b<<1); 
}

方法二：

//实现 a - b
int substract(int a, int b)
{
   
   while(b)
   {
       int temp = a^b;
       a ^= temp;
       b ^= temp;
       
       a |= b;
       b <<= 1;    
   }
  return a;
}

leetcode 693. 交替位二进制数 https://leetcode-cn.com/problems/binary-number-with-alternating-bits/

注意：加上long 是为了避免当 n为2^31 -1时， n+1会越界

class Solution {
public:
    bool hasAlternatingBits(int n) {
        n ^= (n>>1);
        return (n&((long)n+1)) == 0;
    }
};

这篇关于专题复习：位运算的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！