Bit Manipulation
相关概念
位运算符
Bitwise Operators
A & B == 0
It means that A and B never have a 1 bit in the same place.
(n & (n-1)) == 0
n and (n - 1) must have no 1s in common
n 的最低有效位为 0，减去 1 时，必须向高位借1。
It checks if n is a power of 2
移位运算符
Shift operators
左移运算符
a<<b：把 a 转为二进制后左移 b 位（在后面添 b 个0），实际值等于
右移运算符
a>>b：把 a 转为二进制后右移 b 位（在前面添 b 个0），实际值等于
算法应用
幂运算
前提不能使用Math.pow()
ㅤ | ㅤ | ㅤ | ㅤ |
1 | 1 | 0 | 1 |
✔️ | ✔️ | ❌ | ✔️ |
- n= 110
1
- n = 011
0
- n = 001
1
- n = 000
1
递归解法
所有子数组
- 记原序列中元素的总数为 ，原序列中的每个数字 的状态可能有两种，即「在子集中」和「不在子集中」。
- 用 1 表示「在子集中」，0 表示「不在子集中」，那么每一个子集可以对应一个长度为 的 0/1 序列，第 i 位表示 是否在子集中。
- 0/1 序列对应的二进制从 0 到
1<<j
- 表示二进制1（0001）的所有位向左平移 j 个单位后的数，
即将原来的数乘上 （
Math.pow(2,j)）
- 只有第 j 个位置（从右往左数）上的数是1，其余位置上的数是0
- 若 j=1，平移后的结果是0010，得到2
- 若 j=2，平移后的结果是0100，得到8
i & (1<<j)
- 表示 i 和1<<j 进行按位与操作后的数
- a =3 & 5 011 & 101 = 001 = 1