Untitled
# 位运算
----------------------------------------------------------------------------------------
Operator Description Example
----------------------------------------------------------------------------------------
|= bitwise inclusive OR and assignment operator C |= 2 is same as C = C | 2
^= bitwise exclusive OR and assignment operator C ^= 2 is same as C = C ^ 2
&= Bitwise AND assignment operator C &= 2 is same as C = C & 2
<<= Left shift AND assignment operator C <<= 2 is same as C = C << 2
>>= Right shift AND assignment operator C >>= 2 is same as C = C >> 2
----------------------------------------------------------------------------------------
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# NOT (~)
- 位运算 NOT 非 位运算 NOT 由否定号（~）表示
- 位运算 NOT 是三步的处理过程：
- 把运算数转换成 32 位数字 把二进制数转换成它的二进制反码 把二进制数转换成浮点数
- 简单来说就是 取反 -1
- console.log(10 == ~-11) true console.log(-10 == 9)
# AND (&)
- 位运算 AND 与 位运算 AND 由和号（&）表示，直接对数字的二进制形式进行运算。它把每个数字中的数位对齐，然后用下面的规则对同一位置上的两个数位进行 AND 运算： 1 1 1 1 0 0 0 1 0 0 0 0
# OR (|)
- 位运算 OR 或 位运算 OR 由符号（|）表示，也是直接对数字的二进制形式进行运算。在计算每位时，OR 运算符采用下列规则： 1 1 1 1 0 1 0 1 1 0 0 0
# XOR (^)
- 位运算 XOR 异或 位运算 XOR 由符号（^）表示，当然，也是直接对二进制形式进行运算。XOR 不同于 OR，当只有一个数位存放的是 1 时，它才返回 1。真值表如下：
- 1 1 0 1 0 1 0 1 1 0 0 0
# <<
- 左移运算 左移运算由两个小于号表示（<<）。它把数字中的所有数位向左移动指定的数量。例如，把数字 2（等于二进制中的 10）左移 5 位，结果为 64（等于二进制中的 1000000）： var iOld = 2; //等于二进制 10 var iNew = iOld << 5; //等于二进制 1000000 十进制 64
# >>
有符号右移运算 有符号右移运算符由两个大于号表示（>>）。它把 32 位数字中的所有数位整体右移，同时保留该数的符号（正号或负号）。有符号右移运算符恰好与左移运算相反。例如，把 64 右移 5 位，将变为 2：
var iOld = 64; //等于二进制 1000000 var iNew = iOld >> 5; //等于二进制 10 十进制 2
# >>>
- is bitwise operator in Java that is called Unsigned shift
# 剑指 Offer 14- I. 剪绳子
动态规划：
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
dp[i] = Math.max(dp[i], Math.max(dp[i-j] * j, (i-j)*j));
return dp[n];
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 剑指 Offer 15. 二进制中 1 的个数
题目描述
- 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
1
2
3
2
3
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
1
2
3
2
3
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
1
2
3
2
3
- 注意：本题与主站 191 题 相同
**思路 1**
- 标签：位运算
- 整体思路：通过与 1 进行与运算，可以判断末位是不是 1，然后将数字进行无符号右移，最终当数字变成 0 时结束判断 n 表示数字的位数，时间复杂度：O(n)，空间复杂度：O(1)
算法流程 1
- 首先注意力扣在代码模板中标注了 n 是一个无符号数，如果 n 可能是负数还需要另行讨论
- 初始化计数器 count 为 0
- 无符号数 n 与 1 进行与运算，如果 n & 1 == 1，说明 n 的末位为 1，则 count 加一，如果 n & 1 == 0，说明 n 的末位为 0，则 count 不变
- 判断完末位之后，将 n = n >>> 1 进行无符号右移，更新末位
- 当 n == 0 时，结束判断
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n != 0) {
count += n & 1;
n = n >>> 1;
}
return count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
思路 2
- 标签：位运算
- 整体思路：通过与 n = n & (n - 1) 的运算直接获取最后一位为 1 的位置，减少时间复杂度 n 表示数字中包含 1 的位数，时间复杂度：O(n)，空间复杂度：O(1)
算法流程 2
- 首先注意力扣在代码模板中标注了 n 是一个无符号数，如果 n 可能是负数还需要另行讨论
- 初始化计数器 count 为 0
- n = n & (n - 1) 的运算可以直接获取到当前数字最后一位为 1 的位置，同时更新 n
- 当 n == 0 时，结束判断
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n != 0) {
count++;
n = n & (n - 1);
}
return count;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 剑指 Offer 16. 数值的整数次方
题目描述
- 实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
1
2
2
示例 2:
输入: 2.10000, 3
输出: 9.26100
1
2
2
示例 3:
输入: 2.00000, -2
输出: 0.25000
1
2
2
解释: $ 2^{-2} = 1/2^2 = 1/4 = 0.25 $
**思路**
- 标签：快速幂
- 整体思路：
- 直接求 x 的 n 次方是通过循环将 n 个 x 做乘积，时间复杂度为 O(n)，快速幂法 可将时间复杂度降低至 O(log n)
- 利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。
- 复杂度：
- 时间复杂度：O(log n)
- 空间复杂度：
算法流程
- 对于认可十进制正整数 n，设其二进制位
(
为二进制某位值，
)，则有：
- 二进制转十进制：
- 幂的二进制展开：
- 二进制转十进制：
- 根据以上推导，可把计算
转化为解决以下两个问题：
- 计算
的值：循环赋值操作
- 获取二进制各位的值：循环
- 判断二进制最右一位是否为 1；
- n 右移一位；
- 计算
class Solution {
public double myPow(double x, int n) {
if(x == 0.0f) return 0.0d;
// // n=−2147483648, n= -n会溢出。用long接受n即可
long b = n;
double result = 1.0;
// // n为负数时,转换x和取整数n
if(b < 0) {
x = 1 / x;
b = -b;
}
// b每次都右移算当前二进制最右边的数,所以b每次搜缩小1/2
// 当缩小到(1>>1)=0时,循环结束
while(b > 0) {
// 判断二进制最右一位是否为 1
if((b & 1) == 1)
result *= x;
// 无论b最右边是几,都要计算下一轮的xi=x^2
x *= x;
// b二进制位右移一位,因为此时b=|b|,有符号右移还是无符号右移都行
b >>= 1;
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 剑指 Offer 56 - I. 数组中数字出现的次数
题目描述
- 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
1
2
2
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
1
2
2
限制：
- 2 <= nums.length <= 10000
**思路**
- 标签：位运算
- 整体思路：
- 求解一个只出现一次的数字是非常容易的，只需要将所有数字进行一次异或运算即可，这个是求解这道题的前置知识，如果不了解可以查看 136. 只出现一次的数字
- 如果程序中存在两个只出现一次的数字，那么进行所有数字的异或运算之后，就会剩下这两个数字的异或结果
- 异或运算上某一位如果为 1，则说明这两个值在这一位上是不同的，那么可以根据这个特性，将数组中的数字分成 2 组，分别进行异或运算就可以得到最终的两个数字
- 复杂度：
- 时间复杂度：O(n)。第一次异或需要遍历一次数组，第二次分组需要遍历一次数组
- 空间复杂度：O(1)。只需要保存第一次的数组和还有异或位即可
算法流程
- 首先初始化异或结果 tmp，进行数组遍历，完成所有数字的异或运算
- 初始化异或位 div，从最低位开始，找到第一位为1的结果
- 再次遍历数组，根据 div & num 运算进行数字分组，组内进行异或运算，最终得到两组的结果 a、b 即为最终的结果
class Solution {
public int[] singleNumbers(int[] nums) {
int tmp = 0;
// 进行数组遍历，完成所有数字的异或运算
for (int num: nums) {
tmp ^= num;
}
int div = 1;
// 从最低位开始，找到第一位为1的结果
// div 表示 tmp 中最低的为 1 的位置
while ((div & tmp) == 0) {
div <<= 1; // 左移
}
int a = 0;
int b = 0;
// 再次遍历数组，根据 div & num 运算进行数字分组
for (int num: nums) {
// 组内进行异或运算，最终得到两组的结果 a、b 即为最终的结果
if ((div & num) == 0) {
a ^= num;
}
else {
b ^= num;
}
}
return new int[]{a, b};
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 136. 只出现一次的数字 (opens new window)
- 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
- 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
1
2
2
示例 2:
输入: [4,1,2,1,2]
输出: 4
1
2
2
思路
如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种。
- 使用集合 （Set）存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
- 使用哈希表 （HashTable）存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
- 使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。
上述三种解法都需要额外使用 O(n) 的空间，其中 nn 是数组长度。
如何才能做到线性时间复杂度和常数空间复杂度呢？
答案是使用位运算。对于这道题，可使用异或运算
。异或运算有以下三个性质。
- 任何数和 0 做异或运算，结果仍然是原来的数，即
。
- 任何数和其自身做异或运算，结果是 0，即
。
- 异或运算满足交换律和结合律，即
。
- 任何数和 0 做异或运算，结果仍然是原来的数，即
假设数组中有 2m+1 个数，其中有 m 个数各出现两次，一个数出现一次。令
为出现两次的 m 个数，
为出现一次的数。根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：
根据性质 2 和性质 1，上式可化简和计算得到如下结果：
因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
- 空间复杂度：O(1)。
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int num : nums) {
single ^= num;
}
return single;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 剑指 Offer 65. 不用加减乘除做加法
题目描述
- 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
1
2
2
提示：
- a, b 均可能是负数或 0
- 结果不会溢出 32 位整数
**思路**
- 标签：位运算
- 整体思路：
- 这道题在不让用四则基础运算的基础上把结果算出来，说明只能利用二进制的位运算来求解
- 其中无进位和用 n 表示，进位用 carry 表示，sum = a + b = n + carry，位运算可以分别计算出来这两个
- 以 2 个 1 位的二进制数字求和为例，共有 4 种情况，观察下规律，进行位运算求和公式推导
- 从表中可以看出来，无进位和
，进位 carry = a & b << 1 (
)
- 在 sum = n + carry 的计算中，还是使用了加法，进而这种加法运算可以再次使用位运算来解决，这里就是一个循环的思路
- 循环结束的条件是carry = 0，因为当carry = 0 时，sum = n + carry = n + 0 = n 的，所以 n 就是最终的结果
| a | b | 无进位和 n ( | 进位 carry (carry = a & b << 1) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 10 |
- 复杂度：
- 时间复杂度：O(1)。因为题目中提到结果不会溢出 32 位整数，所以最多进行 32 次循环
- 空间复杂度：O(1)。只需要存储无进位和和进位即可
算法流程
- 当进位不为 0 时进行循环
- 使用公式 c = a & b << 1 计算出进位值
- 根据公式
求出无进位和
- 无进位和和进位值依次放到 a、b 中，进行下一次循环
class Solution {
public int add(int a, int b) {
while(b != 0) {
int carry = (a & b) << 1;
int n = a ^ b;
a = n;
b = carry;
}
return a;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 剑指 Offer 44. 数字序列中某一位的数字
题目描述
数字以 0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第 5 位（从下标 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。
请写一个函数，求任意第 n 位对应的数字。
示例 1:
输入：n = 3
输出：3
1
2
2
示例 2:
输入：n = 11
输出：0
1
2
2
**思路**
- 标签：迭代，取余
- 整体思路：
- 根据初始字符串很容易找到数学规律：
- 123456789:是 9 个 1 位数字
- 1011121314...9899:是 90 个 2 位数字
- 100...999:是 900 个 3 位数字
- 根据初始字符串很容易找到数学规律：
- 复杂度：
- 时间复杂度：
。 所求数位 n 对应数字 num 的位数 digit 最大为
- 空间复杂度：
- 时间复杂度：
算法流程
- 先找到输入的数字对应的是几位数 digit
- 然后确定这个数的数值 num
- 最后找到是该数值的第几位数
- 返回结果
class Solution {
public int findNthDigit(int n) {
int digit = 1;
long start = 1; //每个位数的起始数字
long count = 9;
// 先找到输入的数字对应的是几位数 digit
while (n > count) {
n -= count; // 减去之前的 count
digit += 1; // 数字位数加 01
start *= 10;// 起始数字乘 10
count = digit * start * 9; // 数字位数 * 起始数字 = 当前位数的数字所占的最大长度。e.g. 90 个 二位数 占 180 个数字
}
// 确定这个数的数值
long num = start + (n - 1) / digit;
// 最后找到是该数值的第几位数
return Long.toString(num).charAt((n - 1) % digit) - '0';
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
上次更新: 2022/07/21, 12:07:30