文章目录
- 前言
- 一、预备知识
- 1.位运算
- 二、解题思路
- 1.位运算
- 136.single-number
- 268.missing-number
- 191.number-of-1-bits
- 338.counting-bits
- 190.reverse-bits
- 371.sum-of-two-integers
- 7.reverse-integer
前言
整理力扣刷题思路。
- 语言：python
- 题库：来自neetcode: link
一、预备知识
1.位运算
位运算是一种在整数的二进制表示上操作单个位的运算。在大多数编程语言中，包括Python，有7种基本的位运算：与（AND）、或（OR）、异或（XOR）、取反（NOT）、左移（LSHIFT）、右移（RSHIFT）以及无符号右移（无符号 RSHIFT，不过这在Python中并不直接支持）。下面是每种位运算的特性和示例：
-
与（AND）：
- 特性：对位进行AND运算，当两个相应的二进位都为1时，结果位才为1，否则为0。
- 示例：
5 & 3（0101 & 0011 -> 0001, 结果为1）
-
或（OR）：
- 特性：对位进行OR运算，当两个相应的二进位都为0时，结果位才为0，否则为1。
- 示例：
5 | 3（0101 | 0011 -> 0111, 结果为7）
-
异或（XOR）：
- 特性：对位进行XOR运算，当两个相应的二进位相异时，结果位才为1。
- 示例：
5 ^ 3（0101 ^ 0011 -> 0110, 结果为6）
-
取反（NOT）：
- 特性：对位进行NOT运算，将1变成0，0变成1。
- 示例：
~5（~0101 -> 1010, 在8位整数上结果为-6，因为位模式表示的是补码）
-
左移（LSHIFT）：
- 特性：将一个数的所有位都向左移动指定的位数，高位丢弃，低位补0。
- 示例：
5 << 1（0101 << 1 -> 1010, 结果为10）
-
右移（RSHIFT）：
- 特性：将一个数的所有位都向右移动指定的位数。对于无符号数，低位丢弃，高位补0；对于有符号数，低位丢弃，高位补符号位（这取决于语言和系统，称之为算数右移）。
- 示例：
5 >> 1（0101 >> 1 -> 0010, 结果为2）
注意，Python中的右移是算数右移。
Python不直接支持无符号右移，但这在一些其他语言如Java中是存在的，其特性为：
- 无符号右移（无符号 RSHIFT）（不适用于Python）：
- 特性：与标准的右移（有符号右移）不同，无论正负，高位都补0。
- 示例：在支持无符号右移的语言中，
-5 >>> 1结果会把符号位视为普通位一样右移，并且高位补0。
位运算在计算机编程中非常有用，尤其是在需要直接操作整数的二进制表示时。它们通常用于图形编程、加密算法、优化代码性能、内存管理等领域，以及许多需要低层操作的系统编程任务。
二、解题思路
1.位运算
136.single-number
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
link
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for num in nums:
ans ^= num
return ans
268.missing-number
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
link
class Solution:
def missingNumber(self, nums: List[int]) -> int:
ans = len(nums)
#相同的数异或结果为0，最后的结果即为数组中未出现的数
for i,n in enumerate(nums):
ans ^= i^n
return ans
跟上一题其实是一样的
191.number-of-1-bits
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中
设置位的个数（也被称为汉明重量）。
link
#解法1:
class Solution:
def hammingWeight(self, n: int) -> int:
cnt = 0
while n:
cnt += n&1
n >>= 1
return cnt
#解法2:
class Solution:
def hammingWeight(self, n: int) -> int:
cnt = 0
while n:
cnt += 1
n &= n-1
return cnt
参考：link
338.counting-bits
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
link
class Solution:
def countBits(self, n: int) -> List[int]:
cnt = [0]*(n+1)
for i in range(1,n+1):
cnt[i] = cnt[i>>1] + (i&1)
return cnt
190.reverse-bits
颠倒给定的 32 位无符号整数的二进制位。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
link
#解法1
class Solution:
def reverseBits(self, n: int) -> int:
res = ''
for _ in range(32):
#倒序加入二进制的每一位
res += str(n&1)
n >>= 1
return int(res,2)
#解法2
class Solution:
def reverseBits(self, n):
n = (n >> 16) | (n << 16);
#f:1111,c:1100,3:0011,a:1010,5:0101
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
return n
参考：link
371.sum-of-two-integers
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
link
class Solution:
def getSum(self, a: int, b: int) -> int:
a &= 0xffffffff
b &= 0xffffffff
while b:
#按位加法，a保存对应位置为0、1的相加结果，也即1
#b保存两者皆为1的相加结果，进位1
a,b = a^b, (a&b) << 1 &0xffffffff
return a if a<=0x7fffffff else ~(a^0xffffffff)
link
7.reverse-integer
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
link
class Solution:
def reverse(self, x: int) -> int:
y,ans = abs(x),0
check = 0x7fffffff if x>0 else 0x80000000
while y:
ans = ans*10 + y%10
y //= 10
if ans > check:
return 0
return ans if x>0 else -ans
link
