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

class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        
        for i in range(32):
            if n >> i & 1:
                ans |= 1 << 31 - i
        return ans

201. Bitwise AND of Numbers Range

# 从m到n，每次+1，在最低那些位，都经历了0和1的反复变化，对应最终结果都是零。
# 只有m和n的相同的高位，才最终保留在结果里。我们每次向右移动m和n，直到结果m == n。用counter记录移动的次数，然后把当前的m或者n再向左移动counter位就是最终结果

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        counter = 0
        while left != right:
            left >>= 1
            right >>= 1

            counter += 1
        
        return left << counter