数学与位运算 (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