Bổ Sung Cơ Sở 10 (Complement of Base 10 Integer) Trong Python

Cho số nguyên N (cơ số 10). Chuyển sang nhị phân, đảo bit (0→1, 1→0), chuyển lại thập phân. Ví dụ: 20 = 10100₂ → đảo 01011₂ = 11₁₀.

Thuật toán

1. Tìm số bit cần thiết: bits = N.bit_length() (Python 3) hoặc floor(log2(N)) + 1
2. Tạo mask toàn bit 1: mask = (1 << bits) - 1
3. Kết quả = N ^ mask (XOR với mask = đảo bit)

Trường hợp đặc biệt: N = 0 → 1 (vì "0" đảo thành "1")

Ví dụ (Python)

class Solution(object):
    def bitwiseComplement(self, N):
        if N == 0:
            return 1
        # Tạo mask: 111...1 (số bit = N.bit_length())
        mask = (1 << N.bit_length()) - 1
        return N ^ mask

ob1 = Solution()
print(ob1.bitwiseComplement(20))  # 11
print(ob1.bitwiseComplement(5))   # 2 (101 → 010)
print(ob1.bitwiseComplement(0))   # 1
print(ob1.bitwiseComplement(7))   # 0 (111 → 000)

Cách khác (String manipulation)

def bitwiseComplement_str(N):
    if N == 0:
        return 1
    binary = bin(N)[2:]  # bỏ '0b'
    flipped = ''.join('1' if c == '0' else '0' for c in binary)
    return int(flipped, 2)

Độ phức tạp

• Bitwise: O(1) time, O(1) space
• String: O(log N) time, O(log N) space

Đầu vào / Đầu ra

Input:  20
Output: 11