跳到主要内容

7 - 位运算

准备春招，算法题冲冲冲！

位运算​

基本运算​

与 或 非 异或​

AND OR NOT XNOR

其中，有关异或运算有个原理： 0 ^ n => n，n ^ n => 0，使用这个原理可以快速找到 136. 只出现一次的数字 - 力扣（LeetCode）。

右移​

a >> k，等价于 a2k\dfrac{a}{2^k}。

左移​

a << k, 等价于 a×2k a\times2^k 。

常用操作​

看a二进制的k位数字​

  1. 先把第 k 位移到最后一位，即 n >> k。
  2. 看个位是几，即 x & 1。

二者综合起来如下：

// 看13的十位数的二进制数字
int a = 13;
cout << (a >> 2 & 1);    //1

lowbit运算​

lowbit (n) 定义为非负整数 n 在二进制表示下 “ 最低位的 1 及其后面的所有的 0 ” 的二进制构成的数值。

lowbit: (a) & (-a)

其中，-a = ~a + 1 。

练习题​

参考资料​