Leetcode--位运算

  小伙伴们，大家好。今天给大家介绍一下位运算。

  首先给大家介绍一下常用的位运算符号：

  &（按位与）  |（按位或） ^（按位异或） <<（左移） >>（右移）

  以a=4，b=6为例：

  4的二进制为100，6的二进制为110（假设前名的0省略）

  a&b=100（每一位进行运算时如果均为1则该位为1否则为0）

  a|b=110（每一位进行运算时如果有一位为1则该位为1否则为0）

  a^b=010（相同为0不同为1）

  <<（左移一位原数扩大两倍）

  >>（右移一位原数缩小两倍）

  接下来给大家介绍一下比较简单的位运算情景：

（1）取模

  a%b，b=2^n（b是2的倍数注意这里不是异或符号）。那么a%b=a&(2^n-1)

（2）判断奇偶

  直接运用（1）的结论，如果a是偶数那么a&1=0，否则a&1=1

  (3)数字翻倍或减半

  使用<<和>>

（4）交换两数

  a=a^b

  b=a^b（b=(a^b)^b=a^(b^b)=a^0=a)

  a=a^b（a=(a^b)^a=(a^a)^b=0^b=b)

接下来是具体应用：

Leetcode--只出现一次的数字

  题目如下：

   我们在刚才的学习中已经知道：a^a=0。也就是说，如果我们对数组的所有元素进行按位异或运算，那么最终得到的结果一定是只出现一次的数字。

  例如，数组的元素为41212，result开始时为0，进行异或运0^4^1^2^1^2=4^(1^1)^(2^2)=4^0^0=4

注意result初始为0，这样第一次异或就会得到数组的第一个元素。

  给出代码：

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

Leetcode--比特位计数

  题目如下：

  首先告诉大家一个公式：X&(X-1)能够消去X的最低位1。例如：21=10101，21&20=10100=20，我们可以看见最低位1消失。 20&19=10100&10011=10000=16，最低位1消失。16&15=0，最低位1消失。大家可以很轻松的发现一个递推关系：f(n)=f(n&n-1)+1。

  据此我们给出代码：

vector<int> countBits(int n) {
        vector<int>nums(n+1);
        nums[0]=0;
        for(int i=1;i<=n;i++){
            nums[i]=nums[i&i-1]+1;
        }
        return nums;
    }

  除此之外，还有另一种方法，那就是根据奇数偶数来判断。一个奇数的1的个数比它的上一个偶数中1的个数多1个。比如6=110，7=111。比如9=1001，8=1000。一个偶数的1的个数与它的1/2中1的个数相同。例如，8=1000，它的一半4=100，4也是偶数它的一半为2=10，2也是偶数它的一半1=1，1为奇数它的1的个数比0多一个为1个。

  据此我们给出代码：

 vector<int> countBits(int n) {
        vector<int>nums(n+1);
        nums[0]=0;
        for(int i=1;i<=n;i++){
            if(i&1==1){//奇数
                nums[i]=nums[i-1]+1;
            }
            else{
                nums[i]=nums[i>>1];
            }
        }
        return nums;
    }

Leetcode--汉明距离

  题目描述如下：   

   分析这道题目：思路很容易，x^y最终结果中1的位置就是二者不同的位置。我们只需要计算出1的个数即可。哦？这不是上一道题的应用吗！！直接给出代码：

int hammingDistance(int x, int y) {
        int result=x^y,count=0;
        while(result){
            result=result&(result-1);
            count++;
        }
        return count;
    }

  今天的位运算应用就到这里，感谢大家支持！！多多点赞！