🌺位运算

🍁什么是位运算

🍀位运算的定义

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

🍀位运算的优点

位运算可以很好的节约内存，在对内存要求苛刻的地方使用，其次位运算的执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。

🍁位运算符

🍀位运算符&

Q：什么是位运算符&

A：只有对应位置上的数都为1时，结果才等于1，只要有一个0，结果就是0

Q：位运算符&的作用

A：&运算通常用于二进制的取位操作。例如一个数 & 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数。

🍀位运算符|

Q：什么是位运算符 |

A：只有对应位置上的数都为0时，结果才等于0，只要有一个1，结果就是1

Q：位运算符|的作用

A：| 运算通常用于二进制特定位上的无条件赋值。例如一个数 | 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数 | 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。

🍀位运算符^

Q：什么是位运算符 ^

A：如果对应位置上的数不同则该位为1, 否则该位为0，简单来说就是相同为0，不同为1

Q：位运算符^的作用

A：变量交换

交换变量a与b的值
a = a ^ b;  // a = 3 ^ 7
b = a ^ b;  // b = (3 ^ 7) ^ 7 = 3 ^ (7 ^ 7) = 3
a = a ^ b;  // a = (3 ^ 7) ^ 3 = (3 ^ 3) ^ 7 = 7

🍀位运算符~

Q：什么是位运算符 ~

A：取反运算把二进制数中的0和1全部取反

🍀位运算符<<

Q：什么是位运算符 <<

A：a << b就表示把a转为二进制后左移b位（在后面添b个0）

例如100的二进制为1100100，而110010000转成十进制是400，那么100 << 2 = 400。可以看出，a << b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2

Q：位运算符<<的作用

A：通常认为a << 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。

🍀位运算符>>

Q：什么是位运算符 >>

A：和<<相似，a >> b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。和上面一样的例子，那么400>>2 = 100

🍁位运算符优先级

📜习题练习

🍁排除偶次重复数字(1)

🍀题目描述

在一个整数数组中，仅存在一个不重复的数字，其余数字均出现偶数次，找出不重复数字。

🍀题目思路

将所有整数异或，出现偶数次的整数会被抵消，最终留下不重复整数。

💬代码演示

int eor = 0;
for (int i = 0; i < numArray.length; i++) 
{
    eor = eor ^ numArray[i];
}
return eor;

🍁排除偶次重复数字(2)

🍀题目描述

在一个整数数组中，存在两个不重复的数字，其余数字均出现偶数次，找出这两个数字。

🍀题目思路

不妨假设这两个数是a与b，通过异或运算我们可以得到【a ^ b】

int eor = 0;
for (int i = 0; i < numArray.length; i++) 
{
    eor = eor ^ numArray[i];
}
//eor = a ^ b

因为a与b是不同的数字，所以eor的二进制数肯定有一位为1，我们假设在第c位上为1，这就说明a与b在第c位上不同。

我们定义一个ans1，异或所有第c位是1的数就得到了a，eor1^eor就得到了b。那我们怎么找到c的具体的值？

int c = eor & (~eor+1);//提取出最右边的1

提取最右边 1 实现原理

eor ~eor ~eor+1 eor & (~eor+1) 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 1 0 0

当第c位为1时，我们进行异或运算，就能得到a的值

💬代码演示

int eor1 = 0;
int rightOne= eor & (~eor+1);
for (int i = 0; i < numArray.length; i++) 
{
  if(numArray[i] & rightOne == 1)
     eor1 = eor1 ^ numArray[i];
}
a = eor1;
b = eor ^ eor1;

🍁371. 两整数之和

🍀题目描述

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2

输出：3

示例 2：

输入：a = 2, b = 3

输出：5

提示：

   -1000 <= a, b <= 1000

🍀题目思路

       先求出两个数的二进制数，然后相加。就像小学加法一样，第一步先只加每一位对应的数，第二步看看有哪几位需要进位，然后把第一步计算的结果和第二步的再相加，如果有进位了再相加，如此往复，就能得出最后的结果。

     因为异或运算相同为0，不同为1，当两位都为0时，相加应该为0；当有一位是1，有一位是0时，相加为1；当两位都为1时，相加应该为0

通过分析不难得出：异或运算可看做是相加但是不显现进位

       因为与运算相同位的两个数字都为1，则为1；若有一个不为1，则为0。我们就可以统计出哪几位需要进位，他们需要进位到前一位，也就是需要进行<<1。

       我们通过两个结果相加就能得到最终答案吗？答案是肯定的。但是题目要求我们不能用加法，这怎么办呢？

       我们写了一个函数不用加法计算两数和，可以使用递归来得到这两个新数之和，就这样一直递归到不需要进位就是最终答案了。

💬代码演示

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            unsigned int c = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = c;
        }
        return a;
    }
};

本人不才，如有错误，欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】，不行的话我再努努力💪💪💪