29. Divide Two Integers

https://leetcode.com/problems/divide-two-integers/description/

solution

• 位运算 bit shift

"""
以31 / 3为例
-> temp = 3, divided = 28, num = 1, res = 1
-> temp = 6, divided = 22, num = 2, res = 1+2
-> temp = 12, divided = 10, num = 4, res = 1+2+4
-> （回到第一个while）
-> temp = 3, divided = 7, num = 1, res = 1+2+4+1
-> temp = 6, divided = 1, num = 2, res = 1+2+4+1+1
"""

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign = -1 if (dividend >= 0 and divisor < 0) or (dividend < 0 and divisor >= 0) else 1
        dividend = abs(dividend)  # 不要忘记转为正数
        divisor = abs(divisor)

        res = 0
        while dividend >= divisor:  # x里面还能分出y
            temp = divisor
            num = 1  # 注意初始化为1
            while dividend >= temp:  # 开始比较x是否大于y的倍数，一次从x里面减去最大的2^n*y
                dividend -= temp
                res += num  # res代表temp里面有多少个y，所以在x减去temp后，res也要加在result里
                temp = temp << 1
                num = num << 1
        if sign == -1:
            res = -res
        return min(max(-2147483648, res), 2147483647)  # 32-bit integer limitations

时间复杂度：O(log(n^2)) 空间复杂度：O(1)

follow up-位运算

67. Add Binary

136. Single Number

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res = res ^ num
        return res

时间复杂度：O(n) 空间复杂度：O(1)

371. Sum of Two Integers

class Solution:
    def getSum(self, a: int, b: int) -> int:
        carry = 0
        mask = 0xffffffff
        while b & mask != 0:
            carry = (a & b) << 1
            a = a ^ b
            b = carry
        return a & mask if b > mask else a

时间复杂度：O() 空间复杂度：O()

7. Reverse Integer

190. Reverse Bits