1. 剑指 Offer 15. 二进制中1的个数

1
2
3
4
5
6
7
class Solution:
    def hammingWeight1(self, n: int) -> int:
        res = 0
        while n:
            res+=n&1
            n>>=1
        return res


1
2
3
4
5
6
7
class Solution:
    def hammingWeight2(self, n: int) -> int:
        res = 0
        while n:
            res+=1
            n&=(n-1)
        return res

2. 剑指 Offer 16. 数值的整数次方

1
2
3
4
5
6
7
8
9
10
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x==0:return 0
        res = 1
        if n<0:x,n=1/x,-n
        while(n):
            if n&1:res*=x #n为奇数时单分一个x出来
            x*=x
            n>>=1 #n除以2向下取整
        return res

3. 剑指 Offer 56 - I. 数组中数字出现的次数


1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        x, y, n, m = 0, 0, 0, 1
        for num in nums:         # 1. 遍历异或
            n ^= num
        while n & m == 0:        # 2. 循环左移，计算 m
            m <<= 1       
        for num in nums:         # 3. 遍历 nums 分组
            if num & m: x ^= num # 4. 当 num & m != 0
            else: y ^= num       # 4. 当 num & m == 0
        return x, y              # 5. 返回出现一次的数字

4. 剑指 Offer 65. 不用加减乘除做加法

1
2
3
4
5
6
7
class Solution:
    def add(self, a: int, b: int) -> int:
        x = 0xffffffff
        a, b = a & x, b & x
        while b != 0:
            a, b = (a ^ b), (a & b) << 1 & x
        return a if a <= 0x7fffffff else ~(a ^ x)