Bit Manipulation

def addBinary(a: str, b: str) -> str:
    ia, ib, carry = len(a) - 1, len(b) - 1, 0
    answer = []

    # Loop backwords through both strings
    while ia >= 0 or ib >= 0:
        # digit can be 0, 1, 2, or 3
        digit = carry
        digit += int(a[ia]) if ia >= 0 else 0
        digit += int(b[ib]) if ib >= 0 else 0

        # If digit == 1 or 3, append 1
        answer.append(str(digit % 2))
        # If digit == 2 or 3, carry = 1
        carry = digit // 2
        ia -= 1
        ib -= 1

    if carry:
        answer.append("1")
    return "".join(reversed(answer))

Time: O(max(a, b))

Space: O(max(a, b))

def reverseBits(n: int) -> int:
    answer = 0

    # Build 32 bit answer
    for _ in range(32):
        # Shift left once (add space for next bit)
        answer <<= 1

        # Last bit in answer is now 0 after shifting left
        # If last bit in n == 1, set last bit in answer to 1
        if n & 1:
            answer += 1

        # Shift n right once (remove last bit)
        n >>= 1
    return answer

Time: O(1)

Space: O(1)

def hammingWeight(n: int) -> int:
    count = 0

    # Shift right while checking last bit
    while n > 0:
        if n & 1:
            count += 1
        n >>= 1
    return count

Time: O(log n) or O(1) assuming 32 bits

Space: O(1)

def singleNumber(nums: List[int]) -> int:
    answer = 0
    for n in nums:
        # Bitwise exclusive OR
        answer ^= n
    return answer

Time: O(n)

Space: O(1)