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

1. 按位与 a & b
   法则：两者相同位都为 $1$，则结果中该位为 $1$；否则结果中该位为 $0$

   • 例：12 & 6 = 4
     12：1 1 0 0
     $\ \ $6：0 1 1 0
     $\ \ $4：0 1 0 0

2. 按位或 a | b
   法则：两者相同位中有一个为 $1$，则结果中该位为 $1$；否则结果中该位为 $0$

   • 例：12 | 6 = 14
     12：1 1 0 0
     $\ \ $6：0 1 1 0
     14：1 1 1 0

3. 按位异或 a ^ b
   法则：两者相同位的值若不同，则结果中该位为 $1$；否则结果中该位为 $0$

   • 例：12 ^ 6 = 10
     12：1 1 0 0
     $\ \ $6：0 1 1 0
     10：1 0 1 0

4. 按位取反 ~a
   法则：该数中 $0$ 的位置变为 $1$；$1$ 的位置变为 $0$
   （这个涉及二进制补码，先不例）

5. 按位左移 a << b
   法则：将该数 $a$ 左移 $b$ 位，正数左移后为正数，负数左移后为负数

   • 例：3 << 2 = 12
     $\ \ $3：0 0 1 1
     12：1 1 0 0
     $a << b = a \times 2 ^ b$

6. 按位右移 a >> b
   法则：将该数 $a$ 右移 $b$ 位，正数右移后为正数，负数右移后为负数。不论正负，都下取整

   • 例：13 >> 2 = 3
     13：1 1 0 1
     $\ \ $3：0 0 1 1
     $a >> b = a / 2 ^ b$

7. 非 !a
   法则：该数是 $0$ 则为 $1$；否则为 $0$

   • 例：!0 = 1
     $\ \ \ \ \ \ \ $!1 = 0
     $\ \ \ \ \ \ \ $!2 = 0

各种运算符优先级

-,!,~ $>$ *,/,% $>$ >>,<< $>$ >,<,>=,<= $>$ ==,!= $>$ & $>$ ^ $>$ | $>$ && $>$ || $>$ 问号表达式 $>$ 赋值语句

负数表示

用补码表示负数：

• $\because -1 = 0 - 1$
  $\ \ \ \ \ \ \ 0 = 000 \cdots 00$
  $\ \ \ \ \ \ \ 1 = 000 \cdots 01$
  $\therefore -1 = 111 \cdots 11$

同理：

• $-2 = 111 \cdots 110$
  $-3 = 111 \cdots 101$
  $-4 = 111 \cdots 100$
  $\cdots$
  -x = ~x + 1

算补上上面那个例了8

八进制与十六进制

八进制数每一位用 $0 \sim 7$ 表示，每一位占二进制中的 $3$ 位
在 $C++$ 中，前面加 0 表示八进制数，例：

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

十六进制数每一位用 $0 \sim f$ 表示（$a \sim f$ 分别表示 $10 \sim 15$），每一位占二进制中的 $4$ 位
在 $C++$ 中，前面加 0x 表示十六进制数，例：

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

字节

一个字节为 $8$ 位二进制数，也是$2$ 位十六进制数，即 $00000000 \sim 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
取 $x$ 的绝对值：(x ^ x >> 31) - (x >> 31) （int 型）
判断 $x$ 是否不为 $2$ 的整次方幂：x & x - 1
判断 $a$ 是否不等于 $b$：a != b,a - b,a ^ b
判断 $x$ 是否不等于 $-1$：x != -1,x ^ -1,x + 1,~x

应用

枚举子集

• 枚举一个集合 $S$ 的子集 $O(2 ^ {|S|})$ （$|S|$ 表示 $S$ 中的元素个数）

// S 是一个二进制数，表示一个集合，i 枚举 S 的所有子集
for (int i = S; i; i = S & i - 1)
    // blablabla

• 枚举集合 ${0, 1, \cdots, n - 1}$ 的所有子集的子集 $O(3 ^ n)$

for (int S = 0; S < 1 << n; S ++ ) // 枚举集合 {0, ..., n - 1} 的所有子集
    for (int i = S; i; i = S & i - 1) // 枚举子集 S 的子集
        // blablabla

交换两个数字

void swap(int &a, int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

求二进制中数字 $1$ 的个数

• 暴力 $O(\log x)$

int count(int x)
{
    int res = 0;
    while (x) res += x & 1, x >>= 1;
    return res;
}

• 针对 1 较稀疏的情况的优化 $O(\log x)$

int count(int x)
{
    int res = 0;
    while (x) x &= x - 1, res ++ ;
    return res;
}

• 位运算 $O(1)$

int count(int x)
{
    x = (x >> 1 & 0x55555555) + (x & 0x55555555);
    x = (x >> 2 & 0x33333333) + (x & 0x33333333);
    x = (x >> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
    return x % 255;
}

求 $\log _ 2 x$

• 暴力 $O(\log x)$

int log_2(int x)
{
    int res = 0;
    while (x >> 1) res ++ , x >>= 1;
    return res;
}

• 二分 $O(\log\log x)$

int log_2(int x)
{
    int l = 0, r = 31, mid;
    while (l < r)
    {
        mid = l + r + 1 >> 1;
        if (x >> mid) l = mid;
        else    r = mid - 1;
    }
    return r;
}

• 位运算（二分展开）$O(1)$

int log_2(int x)
{
    int res = 0;
    if (x & 0xffff0000) res += 16, x >>= 16;
    if (x & 0xff00) res += 8, x >>= 8;
    if (x & 0xf0) res += 4, x >>= 4;
    if (x & 0xc) res += 2, x >>= 2;
    if (x & 2) res ++ ;
    return res;
}

求一遍从 $1$ 到 $10 ^ 7$ 的 $\log _ 2 x$，暴力要 $470ms$，二分要 $177ms$，位运算要 $70ms$，<cmath> 库的那个要 $307ms$当然人家那是带精度的咱不能跟它比

预处理 $1 \sim n$ 中所有数 $\log$ 后的结果 $O(n)$

方法一

int log_2[N];   // 存 log2(i) 的结果
void init(int n)
{
    for (int i = 0; 1 << i <= n; i ++ )
        log_2[1 << i] = i;
    for (int i = 1; i <= n; i ++ )
        if (!log_2[i])
            log_2[i] = log_2[i - 1];
}

方法二

int log_2[N];   // 存 log2(i) 的结果
void init(int n)
{
    for (int i = 1; i <= n; i ++ )
        log_2[i] = log_2[i - 1] + ((1 << log_2[i - 1]) == i);
    for (int i = 1; i <= n; i ++ )
        log_2[i] -- ;
}

快读优化

inline int read()
{
   int x = 0; bool f = false; char ch = getchar();
   while (ch < 48 || ch > 57) {f |= (ch == 45); ch = getchar();}
   while (ch > 47 && ch < 58) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
   return f ? ~x + 1 : x;
}

龟速加

int add(int a, int b)
{
    while (b)
    {
        int x = a ^ b;
        b = (a & b) << 1;
        a = x;
    }
    return a;
}

例题

状态压缩$DP$$\ \ \ \ $AcWing 91. 最短$Hamilton$路径$\ \ \ \ $题解
位运算性质$\ \ \ \ $AcWing 998. 起床困难综合征$\ \ \ \ $题解
二进制枚举$\ \ \ \ $AcWing 116. 飞行员兄弟$\ \ \ \ $题解（挂份秦大佬的先）