Tony Feng

M.Sc. in Computer Science

Brown University

Leetcode Python

[剑指Offer] Day 21: Bit Operation

Authored by Tony Feng

Created on May 2st, 2022

Last Modified on May 2st, 2022

Task 1 - Q15. 二进制中1的个数

Question

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量).）。

Solution 1

1
2
3
4
5
6
7
8


class Solution: # Recursion
    def hammingWeight(self, n: int) -> int:
        if n == 0:
            return 0
        elif n & 1 == 0:
            return self.hammingWeight(n >> 1)
        else:
            return 1 + self.hammingWeight(n >> 1)

Solution 2

1
2
3
4
5
6
7


class Solution: # Iteration 
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n = n & (n-1) # Remove leftest 1 in each loop
        return res

Explanation

Solution 1
- Time Complexity: O(log(n)), i.e., log(n) means the rightest position of 1 in n
- Space Complexity: O(log(n))
Solution 2
- Time Complexity: O(M), i.e., it depends on how many 1 in the binary string.
- Space Complexity: O(1)

Task 2 - Q65. 不用加减乘除做加法

Question

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。a, b 均可能是负数或 0，并且结果不会溢出 32 位整数

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def add(self, a, b):
        x = 0xffffffff
        a, b = a & x, b & x
        while b:
            carry = (a & b) << 1 & x
            total = a ^ b
            a = total
            b = carry
        return a if a <= 0x7fffffff else ~(a ^ x)

Explanation

Time Complexity: O(1), i.e., maximum number of iterations is 32
Space Complexity: O(1)
sum = a + b => sum = n + c.
- We progressively calculate n and c until c == 0. And return n.

a(i)	b(i)	无进位和 n(i)	进位 c(i+1)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1