系列文章目录

总目录链接

C++面试基础系列-bit_operation

1.bit_operation定义

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

• 对于正数来说，其反码和原码一致。对负数来说，反码就是对除去最高符号位之外的所有二进制位取反。

• 对于正数来说，其补码与反码一致。对负数来说，补码就是对反码做通常意义上的加一操作（含进位）。

• 整数在计算机中是以补码的形式储存的，这就是为什么我们要介绍原码、反码和补码。

• 补码的好处：

  • 其一是明确了整数「0」的表示（否则可以有 0000 0000 和 1000 0000 两种方式表示），
  • 其二是对整数的加法只需要统一的一套电路来处理即可。

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

• 1
• 2

2.bit_operation位运算符号类型

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

4.位运算与宏定义

#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))

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

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 = { 5 , 4 , 3 , 2 , 1 } S = \lbrace 5, 4, 3, 2, 1 \rbrace S={5,4,3,2,1}，我们可以用一个长度为 $5$ 的二进制数来表示该集合。

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

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

再比如二进制数 $01001_{(2)}$ 就表示选取集合的第 $1$ 位、第 $4$ 位元素，也就是集合 { 4 , 1 } \lbrace 4, 1 \rbrace {4,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 二进制枚举子集代码

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                     # 返回所有子集

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

(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 版权协议，转载请附上原文出处链接和本声明。