【优选算法系列】【专题五位运算】第一节.常见的位运算（面试题 01.01. 判定字符是否唯一和268. 丢失的数字）

文章目录

• 前言
• 常见的位运算
• 一、判定字符是否唯一
•       1.1 题目描述
•       1.2 题目解析
•              1.2.1 算法原理
•              1.2.2 代码编写
• 二、丢失的数字
•       2.1 题目描述
•       2.2 题目解析
•              2.2.1 算法原理
•              2.2.2 代码编写
• 总结

---

前言

常见的位运算

1.基础位运算：

---

2.给一个数n，确定它的二进制表示中的第x位是0还是1；

通过让这个n先向右移x位，再&上1即可；

即( n >> x ) & 1;

图示示例：

---

3.将一个数n的二进制表示的第x位修改成1；

通过先让1<< x位，然后让n |= 上前面的1<< x；

即：n |= （1<< x）

图示示例：

---

4.将一个数n的二进制表示的第x位修改成0；

通过先让1<< x位，再取其反，然后让n &= 上前面的 ~（1<< x）；

即 n &=    （~（1<< x））；

图示示例：

---

5.位图思想

---

6.提取一个数（n）二进制表示中最右侧的1；

即：n & ~n；

~n：将最右侧的1，左边的区域全部变成相反。

图示说明：

---

7.干掉一个数（n）二进制表示中最右侧的1；

即：n & （n - 1）；

~n：将最右侧的1（包含1），右边的区域全部变成相反。

图示示例：

---

8.运算符的优先级

能加括号加括号即可

---

9.异或（^）运算的运算律

（1）a ^ 0 = a

（2）a ^ a = 0 （消xiao）

（3）a ^ b ^ c = a ^ （b ^ c）

---

一、判定字符是否唯一

1.1 题目描述

描述：

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

---

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

---

示例1：

---

示例2：

---

1.2 题目解析

2.2.1 算法原理

---

2.2.2 代码编写

---

二、丢失的数字

2.1 题目描述

描述：
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

---

提示：

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

---

示例1：

---

示例2：

---

示例3：

---

示例4：

---

2.2 题目解析

2.2.1 算法原理

---

2.2.2 代码编写

总结