java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

刷题过程中，用到什么关于位运算的知识点，就补充什么知识点到这里

1. 异或相关

1. 异或

1. 两数相同异或为0，两数不相同异或为1
2. 任何数a异或0，都等于a本身。0 ⊕ a = a
3. 两个相同的数异或必然为0。a ⊕ a = 0;
4. 异或具有结合律和交换律。

1. 结合律0⊕1⊕2⊕2 = (0⊕1)⊕(2⊕2) = 1 ⊕ 0 = 1;
2. 交换律0⊕1⊕2⊕2 = 2⊕1⊕2⊕0

2. 与

1. 两个数都是1，相与为1. 1&1=1
2. 两个数有一个是0，相与为0,1&0=0

3. 补码

1. C，C++，java等编程语言中，为了更好的和硬件交互，数字以补码形式存储。
2. 各种码的转换关系如下，了解即可，我们只需要统一用补码进行计算即可。（看不懂没关系，继续看下面）
   
   

2. 补码

补码（了解即可）

1. 真值：我们通过除基取余法得到的二进制代码，统一称为真值。例如十进制数8的二进制位1000，这个1000就是一个真值。
2. 原码：那么如何区分真值是正数还是负数呢？我们只需要用掉开头的一个二进制位，0表示正数，1表示负数。例如8的原码就是0000 … 1000 标红的那位就是符号为，剩下的都是数值位. -8的原码就是1000 … 1000负数的符号位为1.
3. 补码，方便计算机运算的一种码，它不方便人类理解，但是方便计算机。它可以通过原码来推导

1. 正数的补码 = 原码
2. 负数的补码 = 符号位不变，其余位取反，然后末位+1。当然我们有一个口诀，就是从右向左找到第一个1，然后将符号位和这个1之间所有元素按位取反即可（图解如下）
   

不妨做道题：🏆LeetCode645. 错误的集合(位运算解法需要重点掌握)https://blog.csdn.net/grd_java/article/details/135757934

这道题，需要你知道关于补码的什么呢？

1. 集合中保存的都是1~n的正数，计算机保存也都是补码，也就是符号位为0表示正数
2. 正数的补码和源码是一样的，例如1 = 0,000 0000 0000 0000 0000 0000 0000 0001 （以32位进行保存）
3. 负数的补码和源码的区别是，符号位和最右边的1不变，这两个不变的二进制位中间的其余数值位全部取反

1. 原码：例如-1= 1,000 0000 0000 0000 0000 0000 0000 0001
2. 补码：例如-1= 1,111 1111 1111 1111 1111 1111 1111 1111

4. 我们现在有了1和-1的补码。

1. 1 = 0,000 0000 0000 0000 0000 0000 0000 0001
2. -1= 1,111 1111 1111 1111 1111 1111 1111 1111
3. 我们发现，除了最右边的1以外，这个1左边所有的数，都是不同的。

5. 如果此时我执行1与-1 也就是 1 & （-1）

我会得到0,000 0000 0000 0000 0000 0000 0000 0001，也就是除了最右边的1以外，其余全是0. 这样我就得到了这个数的最低位的那个1.也就是我得到了这个数，最右边的一个二进制1的位置。并且其余二进制位全是0

6. 得到它有什么用呢？作用就是简化判断条件，让我们只需要用if考虑两种情况，而不是无数种。

1. 0 & 任何数都是0，只有1 & 1 才能唯一的 = 1. 这就是它的作用。对于最终得到的只有最右1，其余全为0的二进制串lowbit = 0,000 0000 0000 0000 0000 0000 0000 0001来说，只有遇到一个同样1在最右边的数才会不为0，否则它必然为0.
2. 它让任何数与其相与只有两种结果，要么为1，要么为0.而不是各种值。

1. 例如 8 = 0,000 0000 0000 0000 0000 0000 0000 1000
2. 和lowbit相与0,000 0000 0000 0000 0000 0000 0000 0001
3. 结果为==0,000 0000 0000 0000 0000 0000 0000 0000

3. 如果不进行只取最右边1的操作，直接随便两个数呢？

8的二进制补码为：0000 … 1000
9的二进制补码为：0000 … 1001
异或结果为：==== 0000 … 1000 这个值=8，不同的数，还有无穷多种结果
请你告诉我，我该如何写if语句，描述这大量的结果呢？我们当然希望只有0或者1两种状态，以方便我们写if语句。所以这就是只保留最右边的1，其余全部为0的作用。