数学与位运算 (Math & Bit Manipulation)
数学与位运算
数学与位运算题型考查数论、排列组合、位操作、进制转换等。
典型例题
1. 只出现一次的数字(位运算)
def singleNumber(nums):
res = 0
for num in nums:
res ^= num
return res
print(singleNumber([4,1,2,1,2])) # 输出: 4
2. 计数质数(数学)
def countPrimes(n):
if n < 2: return 0
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5)+1):
if is_prime[i]:
for j in range(i*i, n, i):
is_prime[j] = False
return sum(is_prime)
print(countPrimes(10)) # 输出: 4
3. 汉明距离(位运算)
def hammingDistance(x, y):
return bin(x ^ y).count('1')
print(hammingDistance(1, 4)) # 输出: 2