位运算
一、概念
程序中的所有数在计算机中都是以二进制的形式存储的，位运算就是直接对整数在内存中的二进制位进行操作。
二、常见位运算操作
常见位运算操作包括： 左移（<<），右移（>>），按位或（|），按位与（&），按位取反（~），按位异或（^）(相同为0，不同为1)
三、位运算应用
1、判断奇偶性
2、交换两个数
3、取余
4、生成第一个大于a的满足2^n的数
5、求相反数
6、求绝对值
7、获取int型变量的第K位
8、某个数的二进制里面1的个数
9、比较两个数的大小
10、使用异或对明文进行加密
四、常见面试题
例题1：
190. 颠倒二进制位 https://leetcode-cn.com/problems/reverse-bits/
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
思路：
位运算， &1 判断最后一位的奇偶性，每次判断完之后，右移一位，即判断下一位
时间复杂度： O（1）
空间复杂度： O（1）
代码实现：
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(31, -1, -1):
res += (n&1) << i
n >>= 1
return res
例题2：922. 按奇偶排序数组 II https://leetcode-cn.com/problems/sort-array-by-parity-ii/
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
思路：
思路：按位与，如果结果是1，则说明是奇数，如果是0，则说明是偶数
时间复杂度： O（n）
空间复杂度： O（1）
代码实现：
class Solution:
def sortArrayByParityII(self, A: List[int]) -> List[int]:
even, odd = 0, 1
res = [0] * len(A)
for i in range(len(A)):
if A[i] & 1 == 0:
res[even] = A[i]
even += 2
else:
res[odd] = A[i]
odd += 2
return res
例题3： 389. 找不同https://leetcode-cn.com/problems/find-the-difference/
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1：
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。
示例 2：
输入：s = "", t = "y"
输出："y"
示例 3：
输入：s = "a", t = "aa"
输出："a"
示例 4：
输入：s = "ae", t = "aea"
输出："a"
思路：
位运算
时间复杂度： O（n）
空间复杂度： O（1）
代码实现：
# 思路一：位运算
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
ans = 0
for i in s:
ans ^= ord(i)
for i in t:
ans ^= ord(i)
return chr(ans)
# 思路二：位运算求和
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
add_s = 0
add_t = 0
# 计算 s 中各个字符的 ASCII 值和
for ch in s:
add_s += ord(ch)
# 计算 t 中各个字符的 ASCII 值和
for ch in t:
add_t += ord(ch)
# 计算差值，转换为 ASCII 字符
return chr(add_t - add_s)
撰写记录
2020.12.28-06:55:01-第一次撰写
2021.01.10-06:58:10-第二次撰写
2021.02.15-00:12:00-第三次撰写
网友评论