位操作运算符进行刷题,一篇笔记拿下位运算操作

/* 1s代表的是一堆的二进制1 1.首先是异或操作: 用的很多 ^ 同为0 异为1 x^1s=~x x和一堆的二进制1进行异或得到的结果就是~x 因为0^1=1 1^1=0 (解释:二进制和1异或操作相当于取~) x^(~x)=1s(1s代表的还是一堆的二进制1) 当然啦,每一位都是和自己的~异或操作,最后就是一堆的1 x^x=0 //重要的操作 当然很好理解,相同的二进制位异或起来就是0 异或实现swap(a,b) a^=b;b^=a;a^=b; 实现了a和b的值的交换,经典的交换两个整形数据 a^b^c=a^(b^c)=(a^b)^c //associative 交换结合律 */ 位操作运算符是编程中非常基础且强大的工具，尤其在C++和其他低级语言中，它们经常被用来优化性能和解决复杂问题。本篇笔记主要关注位操作中的异或（^）和与（&）运算符，以及如何利用它们解决实际问题。 1. **异或操作**： 异或操作符（^）遵循“同为0，异为1”的原则。当两个位相同，异或结果为0；当两个位不同，结果为1。例如，x^1s等价于~x，因为0^1=1，1^1=0。x^(~x)将每个位都与自己的反码异或，最终得到全1的位模式（1s）。同样，x^x总是等于0，因为相同位的异或结果是0。 异或在交换两个变量的值时特别有用。经典的例子是： ```cpp a^=b; b^=a; a^=b; ``` 这个序列实现了a和b值的互换，而不需要额外的存储空间。 2. **结合律**： 异或操作具有交换结合律，即a^b^c等价于a^(b^c)，这是因为异或的顺序不影响结果。 3. **与操作**： 与操作符（&）用于按位逻辑与。例如，x&1可以判断x是否为奇数，因为x的末尾1表示它是奇数，0表示偶数。类似地，x&3可以替代x%4，x&7可以替代x%8，以此类推。这个规则可以扩展为x&2^n-1等效于x%2^n。 `X &= (X - 1)` 用于清除X的最后一个1，这在位操作中非常有用。例如： ```cpp X: 111100000 X-1: 111011111 X&(X-1): 111000000 ``` 这种操作可以减少计算次数，特别是处理二进制位统计时。 4. **获取最低位1**： 利用`X & (-X)`可以得到X的最低位1，其余位为0。例如： ```cpp 1: 0000 0000 0000 0001 -1: 1111 1111 1111 1111 1 & (-1): 0000 0000 0000 0001 ``` 同样适用于其他数值。 5. **汉明重量**： 汉明重量是指一个整数二进制表示中1的个数。通过`X & (X - 1)`的迭代应用，可以高效地计算出汉明重量，例如在上述的`hammingWeight`函数中。 6. **2的幂次方判断**： 判断一个整数是否为2的幂次方，可以观察其二进制形式，一定是1后面跟着若干0。`X & (X - 1)`应用一次后，如果X变为0，则表明X是2的幂次方。例如在`isPowerOfTwo`函数中。 位操作在算法和数据结构中扮演着重要角色，特别是在优化内存使用、提高执行效率和解决特定问题时。理解和熟练掌握这些操作可以显著提升编程技能，特别是在面试和实际项目中。通过练习和应用，我们可以更好地利用位操作来解决各种复杂问题。