位运算

位运算基础概念以及题目：

概念

位与

符号：&

12&10—->1100&1010（转换为二进制）

从低到高按位运算，当两个数字都为1，结果才为1，否则为0，因此结果为1000，也就是8

位或

符号：|

12|10——->1100|1010

从低到高按位运算，当两个数字都为0，结果才为0，否则为1，因此结果为1110，也就是14

小概念：相同的数异或为0，任何数与0异或为它本身，满足交换律和结合律

异或

符号：^

12\^10——->1100^1010

从低到高按位运算，当两个数字都不同，结果才为1，否则为0，因此结果为0110，也就是6。

从结果来看，异或可以看作不进位的加法

左移

符号：<<

12<<3----->1100<<3

想左移三位，末尾补零，因此结果为1100000.另外，左移一位可以看作该数字乘二。

右移

符号: >>

12>>3——->1100>>3=1

右移三位，右移一位可看作除二向下取整

例题

2的幂

https://leetcode.cn/problems/power-of-two/

bool isPowerOfTwo(int n){
    if (n>0&&(n&(n-1))==0) return true;
    else return false;
}

解析：当一个数为2的幂时，他的表达方式一定为100000….，这个数n表达方式固定，n-1则确定为0111111….。因此对n和n-1取位与，结果一定为1，因此可判断。

4的幂

https://leetcode.cn/problems/power-of-four/

解析：分析可知：$2^{2x}mod 3=1$ 且 $2^{2x+1}mod 3=2$ 因此可以得出结论$4^xmod3=1$ 。因此，当一个数n是2的幂，同时模3为1，则他一定是4的幂

bool isPowerOfFour(int n){
    return (n>0)&&(n&(n-1))==0&&n % 3==1;
}

位1的个数

https://leetcode.cn/problems/number-of-1-bits/

解析：任何一个数字的二进制表示必然可以表示为0，1的组合，当一个数字的二进制形式为….1000时我们把它减去1，则变为形式…..0111,当我们把这两个数进行位与运算，得到的结果为…..0000。我们发现最末尾的1被我们消除了，当我们重复这个过程，在这个过程中记录进行的次数，当最后n变为0时，计数结果就为1的个数。

int hammingWeight(uint32_t n) {
    int count=0;
    while(n!=0)
    {
        count++;
        int ans=n&(n-1);
        n=ans;
    }
    return count;
}

交换数字

https://leetcode.cn/problems/swap-numbers-lcci/

解法：

• a=a\^b
• b=a\^b=a\^b\^b=a\^0=a
• a=a\^b=a\^a\^b=b

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* swapNumbers(int* a, int aSize, int* returnSize){
    a[0]=a[1]^a[0];
    a[1]=a[1]^a[0];
    a[0]=a[1]^a[0];
    *returnSize=2;
    return a;
}

只出现一次的数字

https://leetcode.cn/problems/single-number/

int singleNumber(int* nums, int numsSize){
    int sum=0;
    for(int i=0;i<numsSize;i++)
    {
        sum=sum^nums[i];
    }
    return sum;
}

解法：很巧妙的解法，根据异或的性质，我们发现当我们从头开始循环异或，出现两次的数必然可以结合异或结果为0，最后只剩下异或结果为本身的数，这个数就是出现一次的数。(草，真的牛逼)

汉明距离

https://leetcode.cn/problems/hamming-distance/

解析：把两个数字异或，我们发现结果为1的位上就是两个数字对应二进制位不同的位置，因此我们把异或后的结果进行1消去，同时统计1的个数，答案就是汉明距离。

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

交替位二进制数

https://leetcode.cn/problems/binary-number-with-alternating-bits/

解析：题目意思可以视为判断数字n的二进制表达形式是否为01连续出现，我们判断当00和11出现时对应的十进制数字为0和3，因此我们将数字n与3位与，如果符合题意，得到的结果只能是10或者01，即为1，2，如果出现0，3，则说明n中出现了00，11的组合，则返回false。

bool hasAlternatingBits(int n){
    while(n)
    {
        if((n&3)==0||(n&3)==3) return false;
        n=n>>1;
    }
    return true;
}

找出所有子集的异或总和再求和

https://leetcode.cn/problems/sum-of-all-subset-xor-totals/

解析：这个题我搞了半天（md我怎么这么菜），首先是我们要明白一个数组的子集个数是2的元素个数的次方，因此第一个循环是为了找到所有的子集，当我们找到所有子集之后，我们要对每一个子集进行分析，因为集合中的元素在子集中只会有两种状态，0（未出现）和1（出现），因此，每个子集都可以表示为一个二进制数字，比如数组[2,3,4]的子集之一[2,3]，用相对应的二进制数字来表示就是110。这样表示完每一个子集后，我们对每一个二进制数进行分析，当我们在二进制数中寻找到1时，说明对应的数组nums[i]在子集中存在，就可以进行异或操作了，而寻找二进制数中的1可以用一个表达式来解决:i&(1<<j)。意思是寻找二进制数i在第j位是否为1。当第二次循环遍历二进制数位数之后，我们就可以确定存在的元素，就可以进行必要的异或和相加的操作了。

int subsetXORSum(int* nums, int numsSize){
    int i,j,ans;
    int sum=0;
    for(int i=0;i<(1<<numsSize);i++)
    {
        ans=0;
        for(int j=0;j<numsSize;j++)
        {
            if(i&(1<<j)) ans^=nums[j];
        }
        sum+=ans;
    }
    return sum;
}

两整数之和

阴间题目，要求不能用+，-完成两数求和。

https://leetcode.cn/problems/sum-of-two-integers/

int getSum(int a, int b){
    return b==0?a:getSum(a^b,(unsigned int)(a&b)<<1);
}

分析：首先已知a\^b可以表示为不考虑a和b的情况下a和b的加和，因此我们要找到进位情况下进的位的那个数字，是(a&b)<<1，因此呢我们只要递归运算a\^b和(a&b)<<1的和即可。每次当我们进行(a&b)<<1时，产生的结果0，1分别代表着不进位，进位。因此，如果不进位，结果就是a\^b，即返回函数参数“a”。而当结果不为0，即连个数字都为1时，需要进位，进位则表示着这一个1在后一位相加，而后一位的相加同样可以表示为上述过程，仔细思考可以发现，递归出口在函数参数”b”为0的时候，这个时候进位完毕，输出结果a\^b就是最后答案。

插入

https://leetcode.cn/problems/insert-into-bits-lcci/

int insertBits(int N, int M, int i, int j){
    for(int k=i;k<=j;k++)
    {
        N&=~((long long)1<<k);
    }
    return N|(M<<i);
}

解析：博主摆烂了…