C++面试基础系列-bit_operation

1.bit_operation定义

位操作也叫位运算，计算机底层基于二进制计算，所以位运算的运算效率更高，速度更快。

对于正数来说，其反码和原码一致。对负数来说，反码就是对除去最高符号位之外的所有二进制位取反。
对于正数来说，其补码与反码一致。对负数来说，补码就是对反码做通常意义上的加一操作（含进位）。
整数在计算机中是以补码的形式储存的，这就是为什么我们要介绍原码、反码和补码。
补码的好处：
- 其一是明确了整数「0」的表示（否则可以有 0000 0000 和 1000 0000 两种方式表示），
- 其二是对整数的加法只需要统一的一套电路来处理即可。

1
2
 20 = 0001 0100(原码Source code) = 0001 0100(反码Inverse code) = 0001 0100(补码complement)
-20 = 1001 0100(原码Source code) = 1110 1011(反码Inverse code) = 1110 1100(补码complement)

2.bit_operation位运算符号类型

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
\|	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
«	左移	各二进位全部左移若干位，高位丢弃，低位补0
»	右移	各二进位全部右移若干位，高位补0或符号位补齐

3.位运算的常用操作总结

功能	位运算	示例
方法一：提取最右边的1出来	`x & (~x + 1)`	`100101000 -> 000001000`
方法二：提取最右边的1出来	`x & (-x)`	`100101000 -> 000001000`
从右边开始，把最后一个 $1$ 改写成 $0$	`x & (x - 1)`	`100101000 -> 100100000`
去掉右边起第一个 $1$ 的左边	`x & (x ^ (x - 1))` 或 `x & (-x)`	`100101000 -> 1000`
去掉最后一位	`x >> 1`	`101101 -> 10110`
取右数第 $k$ 位	`x >> (k - 1) & 1`	`1101101 -> 1, k = 4`
取末尾 $3$ 位	`x & 7`	`1101101 -> 101`
取末尾 $k$ 位	`x & 15`	`1101101 -> 1101, k = 4`
只保留右边连续的 $1$	`(x ^ (x + 1)) >> 1`	`100101111 -> 1111`
右数第 $k$ 位取反	`x ^ (1 << (k - 1))`	`101001 -> 101101, k = 3`
在最后加一个 $0$	`x << 1`	`101101 -> 1011010`
在最后加一个 $1$	`(x << 1) + 1`	`101101 -> 1011011`
把右数第 $k$ 位变成 $0$	`x & ~(1 << (k - 1))`	`101101 -> 101001, k = 3`
把右数第 $k$ 位变成 $1$	`x \| (1 << (k - 1))`	`101001 -> 101101, k = 3`
把右边起第一个 $0$ 变成 $1$	`x \| (x + 1)`	`100101111 -> 100111111`
把右边连续的 $0$ 变成 $1$	`x \| (x - 1)`	`11011000 -> 11011111`
把右边连续的 $1$ 变成 $0$	`x & (x + 1)`	`100101111 -> 100100000`
把最后一位变成 $0$	`x \| 1 - 1`	`101101 -> 101100`
把最后一位变成 $1$	`x \| 1`	`101100 -> 101101`
把末尾 $k$ 位变成 $1$	`x \| (1 << k - 1)`	`101001 -> 101111, k = 4`
最后一位取反	`x ^ 1`	`101101 -> 101100`
末尾 $k$ 位取反	`x ^ (1 << k - 1)`	`101001 -> 100110, k = 4`

4.位运算与宏定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#define bitRead(value, bit) (((value) >> (bit)) & 0x01)
#define bitSet(value, bit) ((value) |= (1UL << (bit)))
#define bitClear(value, bit) ((value) &= ~(1UL << (bit)))
#define bitReverse(value, bit) ((value) ^= (1UL << (bit)))
#define bitWrite(value, bit, bitvalue) ((bitvalue) ? bitSet(value, bit) : bitClear(value, bit))

#define lowByte(w) ((w) & 0xff)
#define highByte(w) ((w) >> 8)

#define bitRigthmostGet(value) ((value) & (-value))
#define bitRigthmostClear(value) ((value) & (value-1))

//嵌入式中位操作
#define SET_BIT(REG, BIT) ((REG) |= (BIT))
#define CLEAR_BIT(REG, BIT) ((REG) &= ~(BIT))
#define READ_BIT(REG, BIT) ((REG) & (BIT))

//嵌入式中寄存器操作
#define CLEAR_REG(REG) ((REG) = (0x0))
#define WRITE_REG(REG, VAL) ((REG) = (VAL))
#define READ_REG(REG) ((REG))
#define MODIFY_REG(REG, CLEARMASK, SETMASK) WRITE_REG((REG), (((READ_REG(REG)) & (~(CLEARMASK))) | (SETMASK)))

5.二进制枚举子集

除了上面的这些常见操作，我们经常常使用二进制数第 $1 \sim n$ 位上 $0$ 或 $1$ 的状态来表示一个由 $1 \sim n$ 组成的集合。也就是说通过二进制来枚举子集。

5.1.二进制枚举子集简介

先来介绍一下「子集」的概念。

子集：如果集合 $A$ 的任意一个元素都是集合 $S$ 的元素，则称集合 $A$ 是集合 $S$ 的子集。可以记为 $A \in S$。

有时候我们会遇到这样的问题：给定一个集合 $S$，枚举其所有可能的子集。

枚举子集的方法有很多，这里介绍一种简单有效的枚举方法：「二进制枚举子集算法」。

对于一个元素个数为 $n$ 的集合 $S$ 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 $1$ 来表示选取该元素，用数字 $0$ 来表示不选取该元素。

那么我们就可以用一个长度为 $n$ 的二进制数来表示集合 $S$ 或者表示 $S$ 的子集。其中二进制的每一个二进位都对应了集合中某一个元素的选取状态。对于集合中第 $i$ 个元素来说，二进制对应位置上的 $1$ 代表该元素被选取，$0$ 代表该元素未被选取。

举个例子，比如长度为 $5$ 的集合 $S = \lbrace 5, 4, 3, 2, 1 \rbrace$，我们可以用一个长度为 $5$ 的二进制数来表示该集合。

比如二进制数 $11111_{(2)}$ 就表示选取集合的第 $1$ 位、第 $2$ 位、第 $3$ 位、第 $4$ 位、第 $5$ 位元素，也就是集合 $\lbrace 5, 4, 3, 2, 1 \rbrace$，即集合 $S$ 本身。如下表所示：

集合 S 中元素位置	5	4	3	2	1
二进位对应值	1	1	1	1	1
对应选取状态	选取	选取	选取	选取	选取

再比如二进制数 $10101_{(2)}$ 就表示选取集合的第 $1$ 位、第 $3$ 位、第 $5$ 位元素，也就是集合 $\lbrace 5, 3, 1 \rbrace$。如下表所示：

集合 S 中元素位置	5	4	3	2	1
二进位对应值	1	0	1	0	1
对应选取状态	选取	未选取	选取	未选取	选取

再比如二进制数 $01001_{(2)}$ 就表示选取集合的第 $1$ 位、第 $4$ 位元素，也就是集合 $\lbrace 4, 1 \rbrace$。如下标所示：

集合 S 中元素位置	5	4	3	2	1
二进位对应值	0	1	0	0	1
对应选取状态	未选取	选取	未选取	未选取	选取

通过上面的例子我们可以得到启发：对于长度为 $5$ 的集合 $S$ 来说，我们只需要从 $00000 \sim 11111$ 枚举一次（对应十进制为 $0 \sim 2^5 - 1$）即可得到长度为 $5$ 的集合 $S$ 的所有子集。

我们将上面的例子拓展到长度为 $n$ 的集合 $S$。可以总结为：

对于长度为 $n$ 的集合 $S$ 来说，只需要枚举 $0 \sim 2^n - 1$（共 $2^n$ 种情况），即可得到集合 $S$ 的所有子集。

5.2 二进制枚举子集代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def subsets(self, S):                   # 返回集合 S 的所有子集
        n = len(S)                          # n 为集合 S 的元素个数
        sub_sets = []                       # sub_sets 用于保存所有子集
        for i in range(1 << n):             # 枚举 0 ~ 2^n - 1
            sub_set = []                    # sub_set 用于保存当前子集
            for j in range(n):              # 枚举第 i 位元素
                if i >> j & 1:              # 如果第 i 为元素对应二进位删改为 1，则表示选取该元素
                    sub_set.append(S[j])    # 将选取的元素加入到子集 sub_set 中
            sub_sets.append(sub_set)        # 将子集 sub_set 加入到所有子集数组 sub_sets 中
        return sub_sets                     # 返回所有子集

(https://liam.page/2015/10/02/how-to-get-the-last-1-bit-of-an-integer/

https://github.com/itcharge/LeetCode-Py

关于作者

微信公众号:WeSiGJ
GitHub:https://github.com/wesigj/cplusplusboys
CSDN:https://blog.csdn.net/wesigj
微博:
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。