文章目录
- 前言
- 一、预备知识
- 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