ACM资料 位运算技巧

"ACM资料 位运算技巧" 位运算是计算机科学中的一种基本操作，直接对整数在内存中的二进制位进行操作。位运算可以用于各种实际应用，例如判断奇偶数、取二进制的最末位、对二进制的特定一位进行取反操作等。 在Pascal和C语言中，位运算符号不同。Pascal语言使用and、or、xor、not等关键字，而C语言使用&、|、^、~等符号。 下面是常见的位运算技巧： 1. and 运算：and 运算通常用于二进制取位操作，例如一个数 and 1 的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为 0 表示该数为偶数，最末位为 1表示该数为奇数。 2. or 运算：or 运算通常用于二进制特定位上的无条件赋值，例如一个数 or 1 的结果就是把二进制最末位强行变成 1。如果需要把二进制最末位变成 0，对这个数 or 1 之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。 3. xor 运算：xor 运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0 和 1 异或 0 都不变，异或 1 则取反。xor 运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a xor b) xor b = a。 4. not 运算：not 运算的定义是把内存中的 0 和 1 全部取反。使用 not 运算时要格外小心，你需要注意整数类型有没有符号。如果 not 的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用补码表示的。 位运算可以用于加密和解密。例如，使用 xor 运算可以对消息进行加密和解密。假设我们想对一条消息进行加密，可以使用一个密钥对该消息进行 xor 运算。然后，接收方可以使用同样的密钥对该消息进行 xor 运算，以恢复原始消息。 此外，位运算还可以用于交换两个变量的值。通常情况下，我们需要使用一个临时变量来实现交换变量的值。但是，使用 xor 运算可以实现不需要临时变量的 swap 过程。 位运算是一种非常实用的技术，可以应用于各种实际问题中。掌握位运算技巧可以帮助我们编写更加高效和简洁的代码。