位运算，由于它直接操作在最底层速度快、内存消耗少、效率高，很多大厂的面试题也层出不穷，leetcode 上也有很多题是关于位运算的。
1.常用位运算的分类
| 符号 | 意义 |
|---|---|
| & | 按位与 |
| | | 按位或 |
| ~ | 按位取反 |
| ^ | 异或 |
| << | 左移 |
| >> | 右移 |
2.位操作符介绍
- &运算：两个相同时，才为1，否则为0
1 1 0 1
1 0 1 0
-------------
1 0 0 1 - | 运算：任意一个为1，则运算结果为1
- ~ 运算：~1 = 0，~0 = 1
- ^ 运算：相异为1，相同为0
- << 将数据左移一位
- >> 将数据右移一位
3. 位运算所蕴含的意义
3.1 位运算交换两数值
a = 1;b = 2
a ^= b
b ^= a
a ^= b
这样便用位操作实现了交换两数值，而不需要开辟额外的内存空间（pyhton不需要开辟额外的空间，但其他常见语言需要），速度与效率皆大大提高。
3.2.位运算实现乘除
a = 4
a << 2 #结果为16
a >> 2 #结果为1
- 左移n位，就相当于原数2*n,低位补零，高位丢弃，有符号带符号（计算机以数据的补码保存数据，至于补码原码的知识，可以看看博主的这篇文章）
- 右移n位，相当于原数// 2**n,高位补零，有符号带符号。
3.3 判断奇偶
只需要将该数与1进行&操作
3.4 位操作实现高低位交换
只需将其数据左移8位、右移8位即可
a = 0b10001101
b = (a << 8)|(a >> 8)
3.5 异或的骚操作
以下内容基于力扣题目解答
+ 只出现一次的数字
异或有一个性质：
a^b^b = a
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
class Solution:
def singleNumber(self, nums: List[int]) -> int:
num = 0
for i in nums:
num = num^i
return num
+ 找出重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次
+ 找不同
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例:
输入：
s = "abcd"
t = "abcde"
输出：
e
解释：
'e' 是那个被添加的字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
异或运算骚操作比较多，由于本人理解也不够深刻，只能前往leetcode 加深印象。
网友评论