位运算总结
文章目录
- 🍈1. 基础位运算
- 🍌2. 给一个数`n`，确定它的二进制表示中的第`x`位是`0`还是`1`
- 🍏3. 将一个数`n`的二进制表示的第`x`位修改成`1`
- 🍓4. 将一个数的`n`的二进制表示的第`x`位修改成`0`
- 🥔5. 位图的思想
- 🫒6. 提前一个数`n`二进制中最右侧的`1`
- 🫑7. 干掉一个数`n`二进制表示中最右侧的`1`
- 🧄8. 运算符优先级
- 🫘9. 异或`^`运算符的运算律
🍈1. 基础位运算
>>：右移操作符——二进制补码右移<<：左移操作符——二进制补码左移~：按位取反操作符——二进制补码按位取反&：按位与——有假则假(有0则0)|：按位或——全真为真(全1则1)^：按位异或/无进位相加——相同为0，不同为1
不是很了解的可查看此篇文章：C语言——操作符（上）
🍌2. 给一个数n，确定它的二进制表示中的第x位是0还是1
我们先做一个约定：
计算几位几位的时候，从最低位开始（最右侧）
这样的好处就是当我们要左移操作到最低位的时候，直接移动对应的第几位即可
那我们要确定这一位是0还是1，只需要让这个位置& 1即可，这里有两种方法：
- 让
1左移到这个对应的位置，再按位与，这个不常见 - 让这个位右移到最低位，然后
& 1即可
(n>>x) & 1
🍏3. 将一个数n的二进制表示的第x位修改成1
这里我们让这个一位按位或| 1即可，然后其他位按位或| 0。想要这样，我们只需要将1左移x位即可1<<x
🍓4. 将一个数的n的二进制表示的第x位修改成0
让当前位置按位与上& 0，只需要将1左移到对应位置，然后按位取反，即其他位置全是1，此时这个位置为0
🥔5. 位图的思想
位图的本质其实就是一个哈希表，在大多数情况下都是一个数组，而位图则是用int的二进制位来记录信息。
那这样我们就经常要用到上面的三个思想，来查看或者修改这个二进制位。
关于位图的具体内容，可以查看此篇文章：位图bitset及其应用——【C++实现】
🫒6. 提前一个数n二进制中最右侧的1
这里直接让n & -n即可
-n就是按位取反再+1
我们发现这个
-n的操作，本质上其实就是将最右侧的1左边的区域全部变成相反然后我们按位与下，那么这前面的区域就全部变为
0了，这样就实现了将最右侧的1给提取出来了
🫑7. 干掉一个数n二进制表示中最右侧的1
这里的意思就是将最右侧的二进制1变为0，这里只需将n & (n-1)即可
这里
n-1的本质就是如果后面是连续的0，则需要一直借位，直到借到1为止，借完之后要-1
所有就是让最右侧的
1作为分界线，右边的区域全部变成相反
🧄8. 运算符优先级
能加括号就加括号！这样一定不会错！
能加括号就加括号！这样一定不会错！
能加括号就加括号！这样一定不会错！
🫘9. 异或^运算符的运算律
a^0= aa^a = 0(消消乐)a ^ b ^ c = a ^ (b ^ c)