登录以参加训练计划

本节内容需要先复习下，二进制，进制转化，原码，反码，补码等概念。

除了算术运算，关系运算，逻辑运算外。在计算机编程语言中还有位运算，位运算是直接对整数在内存中的二进制位进行操作的运算。位运算的速度要比加减乘除要快。以下列出常见的位运算符：

1，"<<" 左移运算：

n = n << m 相当于把数字n乘了m次

2，">>"右移运算：

n = n >> m 相当于把数字n除了m次

3，"&"按位与：

n = x&y 把x和y转换成2进制以后，按照每一位进行与运算。（每一位当中都为 1的时候目标位的数字才是1否则都为 0

4，"|" 按位或：

n = x|y 把x和y转换成2进制以后，按照每一位进行或运算。（每一位当中只要有一个 1的时候目标位的数字就是1，否则为0。

5，“~ ”按位取反：

n = ~n 把数字转换成二进制以后进行取反。

6，“^ ”按位异或：

n=x^y 把x和y转换成2进制以后，按照每一位进行异或运算。（每一位当中两个数字不相同的时候为1，相同为0。）

位运算符的简写，与其它算术运算符一样，位运算符也可以简写。如下：

a &= b 相当于 a = a & b a |= b 相当于 a = a | b a >>= b 相当于 a = a >> b a <<= b 相当于 a = a << b a ^= b 相当于 a = a ^ b

运算优先级别：由高到低分别为，* / % + - << >> < <= > >= != & ^ | ~ && || ，为了代码的可读性，适当添加括号。

常用位运算举例：

1 ，异或（XOR）运算符^被用来找出一组整数中缺失的那个数。

异或运算有以下特性：

交换律：a ^ b = b ^ a 结合律：(a ^ b) ^ c = a ^ (b ^ c) 恒等性：任何数与0进行异或操作，结果是其本身，即 a ^ 0 = a 自反性：任何数与其自身进行异或操作，结果为0，即 a ^ a = 0

2，lowbit 是一个常用的位运算技巧，它用于获取一个整数的二进制表示中最右边的1及其后面的0构成的数值。

具体来说，lowbit(n) 返回的是 n 的二进制表示中最低位的1所对应的值。

lowbit 通常使用以下公式计算：

int lowbit(int n) {
    return n & -n;
}

这个公式的原理如下：

1.在计算机中，负数通常以补码形式存储。对于一个整数 n，其补码 -n 可以通过将 n 的每一位取反后加1得到。

2.当 n 中最右边的1出现时，从该位置到最低位（包括该位置）的所有位在 -n 中都会变成0，而该位置左边的所有位保持不变。

3.因此，n & -n 就会保留 n 中最右边的那个1，并将其右边所有的0也保留下来，而其他所有位都变为0。

例如，如果 n = 12，其二进制表示为 1100，那么：

n 的二进制是 1100 -n 的二进制是 0100（因为 -12 的补码是 1100 的每一位取反再加1，即 0011 + 0001 = 0100） n & -n 的结果就是 0100，也就是十进制的4 所以 lowbit(12) 的结果是 4。

lowbit 函数在很多算法和数据结构中有重要应用，比如树状数组（Fenwick Tree），它可以高效地进行区间求和、更新等操作。