常用位操作

191. 位1的个数 - 力扣（LeetCode）

231. 2 的幂 - 力扣（LeetCode）

136. 只出现一次的数字 - 力扣（LeetCode）

268. 丢失的数字 - 力扣（LeetCode）

常用位操作： 与（&）、 或（ | ）、 异或（ ^ ）  

原理：ASCII码

1.利用或操作 | 和空格将英文字符转换为小写

( 'a' | ' ' ) = 'a';
( 'A' | ' ' ) = 'a';

2.利用与操作 & 和下划线将英文字符转换为大写 

( 'b' & '_' ) = 'B'
( 'B' & '_' ) = 'B'

3.利用异或操作 ^ 和空格进行英文字符大小写互换 

( 'd' ^ ' ' ) = 'D'
( 'D' ^ ' ' ) = 'd'

4.判断两个数是否异号

原理：补码的符号位，负数是1，正数是0，异号数相与是负数，同号数相与是正数）

int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
 
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false

5.不用临时变量来交换两个数

int a=1,b=2;
a^=b;
b^=a;
a^=b;//现在a=2，b=1

 

191.位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

原理：n&( n-1)，可以消除n的二进制表示中的最后一个1

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res=0;
        while(n!=0)//循环至n为0
        {
            n=n&(n-1);//n与n-1，可以消除n的二进制表示中的最后一个1
            res++;
        }
        return res;
    }
};

231.2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：2^0 = 1
示例 2：

输入：n = 16
输出：true
解释：2^4 = 16

原理：n&(n-1)可以消除n的二进制表示的最后一个1，2的幂次方的二进制表示有且只有一个1

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0)//n<=0时，肯定不是2的幂次方
            return false;
        //n&(n-1)可以消除n的二级制表示中的最后一个1
        n=n&(n-1);//因为2的幂次方的二级制表示只有一个1，所以操作一次后判断是否为0
        return n==0?true:false;
    }
};

136.只出现一次的数字

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

原理：a ^ a = 0，a ^ 0 = a（奇数个a异或等于它本身，偶数个a异或等于0）

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(int i:nums)//数组内所有数做异或，出现两次的异或成0，出现一次的最后和0做异或，等于它本身
        {
            res=res^i;//a异或a=0，a异或0=a（奇数次的a异或等于它本身，偶数次的a异或等于0）
        }
        return res;
    }
};

286.丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

思路一：求出1~n的总和，再减去nums中所有元素的总和，就得到了丢失的那个数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        int sum=(1+n)*n/2;//利用求和公式对1~n求和
        int acu=accumulate(nums.begin(),nums.end(),0);
        return sum-acu;
    }
};

思路二：a ^ a = 0，a ^ 0 = a（奇数个a异或等于它本身，偶数个a异或等于0）

res和元素个数n异或，然后再和nums中的每个元素及其下标异或，最后就得到了缺的那个

例子：

nums=[3,0,1] , n=3 , res=0

res = res ^ 3 ^ 3 ^ 0 ^ 0 ^ 1 ^ 2 ^ 1 = res ^ 3 ^ 3 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 = 0 ^ 2 = 2 

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