位运算

从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。

位运算概览

按位与(&)

按位与常用于清零、取比特位、判断奇偶、

// 清零
char c = 'a';
c &= 0x00;

// 获取最后两位比特数据
char block='a';
char tmp=block & 0x03;

// 判断偶数
int n=100;
if(n&1==0){

}

按位或(|)

按位或常用于设置比特位数据

// 将最后两位设置为0
c |= 0x03;

异或(^)

参加运算的两个对象，如果两个相应位相同为0，相异为1，性质：

• 交换律
• 结合律 (a^b)^c == a^(b^c)
• 对于任何数x，都有 x^x=0，x^0=x
• 自反性: a^b^b=a^0=a;

应用：

// 翻转指定位
// 翻转后4位
c ^= 0x0f;

// 与0相异或值不变
c ^ 0x00 == c;

// 交换两个数
a ^= b;
b ^= a;
a ^= b;

取反运算符(~)

对一个二进制数按位取反，即将0变1，1变0。

算法应用

只出现一次的数字

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

• ① 哈希表，时间复杂度O(n)，空间复杂度O(n)
• ② 位运算，因为相同数字异或等于0，任何数字与0异或均为本身，故对所有数字异或一遍，最终数字即为所求。时间复杂度O(n)，空间复杂度O(1)

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

只出现一次的数字 II

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

• ① 哈希表，时间复杂度O(n)，空间复杂度O(n)
• ② 依次确定每一个二进制位。考虑答案的第i个二进制位，它可能为0或1。对于数组中非答案的元素，每一个元素都出现了3次，对应着第i个二进制位的 3个0或3个1，无论是哪一种情况，它们的和都是3的倍数（即和为0或3）。因此：答案的第i个二进制位就是数组中所有元素的第i个二进制位之和除以3的余数。时间复杂度O(nlogc)，c是数字位数，空间复杂度O(1)

  int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int i = 0; i < 32; ++i) {
        int total = 0;
        for (int num: nums) {
            total += ((num >> i) & 1);
        }
        if (total % 3) {
            ans |= (1 << i);
        }
    }
    return ans;
  }
  

参考

位运算（&、|、^、~、»、«）

只出现一次的数字 II