蓝桥杯算法|练习记录

位运算

• 按位与运算符（&）

  • 运算规则：两位同时为1，结果才为1，否则结果为0。例如， -3（在计算机中表示为1101）&5（0101） = 0101（即十进制的1），这里负数在计算机中用补码表示2。结果不会变大。
  • 应用示例：
    • 取指定位：比如取数X = 10101110的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0（即Y = 00001111），然后将X与Y进行按位与运算（X&Y = 00001110）即可得到X的指定位。
    • 判断奇偶：可以根据一个数与1进行按位与运算的结果判断奇偶性，因为奇数的二进制最后一位为1，偶数最后一位为0，例如，5（101）&1（001） = 1，所以5是奇数。

• 按位或运算符（|）

  • 运算规则：将两个操作数化为二进制后并将对应的每一位分别进行逻辑或操作，只要有一个为1结果就为1，即0|0 = 0；0|1 = 1；1|0 = 1；1|1 = 1。结果不会变小。
  • 应用示例：常用于对一个数据的某些位设置为1。

• 按位异或运算符（^）

  • 运算规则：对应位相同则运算结果为0，否则为1，即0^0 = 0；0^1 = 1；1^0 = 1；1^1 = 0。例如，任何二进制数与零异或，都会等于其本身，即A^0 = A。不会进位。
  • 应用示例：
    • 翻转指定位：比如将数X = 10101110的低4位进行翻转，只需要找到一个数Y，令Y的低4位为1，其余位为0（即Y = 00001111），然后将X与Y进行异或运算（X^Y = 10100001）即可得到。
    • 具有自反性：A^B^B = A（由结合律可推：A^B^B = A^(B^B)=A^0 = A）。

• 按位取反运算符（~）

  • 运算规则：对每一位进行取反。例如，求x的相反数可以用x = (~x + 1)。

• 左移运算符（<<）

  • 运算规则：将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。例如，设a = 10101110，a = a << 2将a的二进制位左移2位、右补0，即得a = 10111000。若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

• 右移运算符（>>）

  • 运算规则：将一个运算对象的各二进制位全部右移若干位，左补0或者左补1得看被移数是正还是负。例如，12（00001100）右移2位变为00000011（即3）。