位运算相关

一、求1的个数

二进制中1的个数
法一：逐位判断

根据与&运算 n&1=0，说明n的最右边一位为0 n&1=1，说明n的最右边一位为1
所以思路就是，将n右移再与1按位与

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

时间复杂度：O(logn)
逐位判断需循环log2n次，其中log2n代表数字n最高位1的所在位数（例如log2 4 = 2,log2 16 = 4)
右移一位的操作相当于除2
空间复杂度：O(1)

法二：利用n&(n-1)

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

时间复杂度：O(m) m为二进制中1的个数
空间复杂度：O(1)

二、另类加法

不用加减号的加法
与：同时为1，才为1
异或：相同为0，相异为1

class Solution {
public:int add(int a, int b) {
//因为不允许用+号，所以求出异或部分和进位部分依然不能用+ 号，所以只能循环到没有进位为止        while(b!=0){
//保存进位值，下次循环用int c=(unsigned int)(a&b)<<1;//C++中负数不支持左移位，因为结果是不定的
//保存不进位值，下次循环用，a^=b;
//如果还有进位，再循环，如果没有，则直接输出没有进位部分即可。b=c;   }return a;}
};

/*
把a+b转换成非进位和+进位，由于不能用加法，因此要一直转换直到第二个加数变成0。 
用递归的写法比循环更容易一下子看懂
*/
class Solution {public int add(int a, int b) {if (b == 0) {return a;}// 转换成非进位和 + 进位return add(a ^ b, (a & b) << 1);}
};

三、数组中出现一次的数字

传送门

class Solution {
public:vector<int> singleNumbers(vector<int>& nums) {int res=0;//相同取0，相异取1，因此0^0=0,0^1=1,0异或任何数都为本身，可理解为没影响for (int n: nums) {res ^=n;//假设两个只出现一次的数分别为a和b，获得a异或b的结果}//找到ab第一个不相同的二进制位，用位与&操作（两个都为1才为1，其余为0，因此可理解0和任何数相与都还是本身）//理解：位与，就是0可以掩盖掉所有数字，0遇0为0，遇1还为0（子网掩码）//通过1的位置变化找出首个不一样的二进制位int m=1;while((m&res)==0){//m=000001，当第一位不是1时，结果为0，则m左移一位，000010类推直到找出m<<=1;}//找到m以后，用m划分数组，两个相同的数字，在m位一定相同，即其与m位与的结果一定是相同的，因此按m&n==0划分，就一定能保证：//（1）原来相同的元素还在一组//（2）不同的两个元素被分到了不同组int a=0,b=0;for (int n:nums) {if ((n&m)==0) a^=n;else b^=n;}return {a,b};}
};

四、数组中出现一次的数字变形

传送门
法一：哈西最简单的方法

class Solution {
public:int singleNumber(vector<int>& nums) {map<int,int> m;for(auto e: nums){m[e]++;}for(auto e: m){if(e.second==1) return e.first;}return 0;}
};

法二：位运算

 7 : 0B0111 7 : 0B01117 : 0B0111^^^|||出现数  333 // 从上向下，可以发现[3个7]每位都出次了 3 次那这样时再增加一个数。7 : 0B0111 7 : 0B01117 : 0B01114 : 0B0100^^^|||出现数  433 // 从上向下，只有第 3位bit 出现了 4次%%%333 // 接下来，把现各个位出现的次数，按 3取余‖‖‖100 // 取余结果刚好100对应的就是4

class Solution {
public:int singleNumber(vector<int>& nums) {int res = 0;for (int i = 0, sub = 0; i < 32; ++i, sub = 0) {for (auto &n : nums) sub += ((n >> i) & 1);if (sub % 3) res |= (1 << i);}return res;}
};