位运算

C++ 几种常用位运算简介

按位与 a & b (AND)

法则：两者相同位都为$1$，则结果中改为为$1$；否则结果中改位为$0$

1
2
3
4
例： 12 & 6 = 4
  12: 1 1 0 0
   6: 0 1 1 0
   4: 0 1 0 0

按位或 a | b (OR)

法则：两者相同位中有一个为$1$，则结果中该位为$1$；否则结果中该位为$0$

1
2
3
4
例： 12 & 6 = 14
  12: 1 1 0 0
   6: 0 1 1 0
  14: 1 1 1 0

按位异或 a ^ b (XOR)

法则：两者相同位的值若不同，则结果中该位为$1$；否则结果中该位为$0$

1
2
3
4
例： 12 & 6 = 10
  12: 1 1 0 0
   6: 0 1 1 0
   4: 1 0 1 0

按位取反~a (NOT)

法则：该书中$0$的位置变为$1$，$1$的位置变为$0$

1
2
3
4
例： 
  12: 1 1 0 0
 ~12: 0 0 1 1

按位左移 a << b

法则：将该数$a$左移$b$位，正数左移变为正数，负数左移变为负数

1
2
3
例： 3 << 2 = 12
   3: 0 0 1 1
  12: 1 1 0 0

$a \ << \ b \ = \ a \ * \ 2^b$

按位右移a >> b

法则：将该数$a$右移$b$位，正数左移变为正数，负数左移变为负数。不论正负，都下取整

**

1
2
3
例： 13 >> 2 = 3
   3: 1 1 0 1
  12: 0 0 1 1

$a \ >> \ b \ = \ a \ / \ 2^b$

非!a

法则：该数是$0$则为$1$；否则为$0$

1
2
3
例： !0 = 1
    !1 = 0
    !2 = 0

负数表示

用补码表示负数：

1
2
3
4
5
6
7
8
9
10
∵ -1 = 0 - 1
    0 = 000...00
    1 = 000...01
   -1 = 111...11
同理：
    -2 = 111...110
    -3 = 111...101
    -4 = 111...100
    ...
    -x = ~x + 1

八进制与十六进制

八进制数每一位用$0 \ $~$ \ 7$表示，每一位占二进制中的$3$位

在$C ++$中，前面加0表示八进制数，例：

1
2
printf("%d\n", 015);
// 输出：13

十六进制数每一位用$0 \ $~$ \ f$表示（$a \ - \ f$分别表示$10 \ - \ 15$），每一位占二进制中的$4$位

在$C++$中，前面加0x表示十六进制数，例：

1
2
printf("%d\n", 0xd);
// 输出：13

字节

一个字节为8位二进制数，也是2位十六进制数，即$00000000 \ $~ $ \ 11111111$

一个int占$4$个字节，即32位二进制数

一个long long占8个字节，即64位二进制数

memset按字节复制，故当f为int类数组时，memset(f, 0x3f, sizeof f)是将f赋值为0x3f3f3f3f

位运算常用技巧

$(多用于状压DP)$

将$ \ x \ $第$ \ i \ $位取反：x ^= 1 << i

将$ \ x \ $第$ \ i \ $位制成$\ 1$：x |= 1 << i

将$ \ x \ $第$ \ i \ $位制成0： x &= -1 ^ 1 << i或x &= ~(1 << i)

取$ \ x \ $对$ \ 2 \ $取模的结果：x & 1

取$ \ x \ $第$ \ i \ $位是否为$1$：x & 1 << i或x >> i & 1

取$ \ x \ $的最后一位：x & -x