Complement ของจำนวนฐานสิบใน Python

ให้จำนวนฐานสิบ หา complement ในรูปฐานสอง (กลับบิต 0↔1) แล้วแปลงกลับเป็นฐานสิบ

ตัวอย่าง: 20 → binary 10100 → complement 01011 → decimal 11

ขั้นตอนการแก้ปัญหา

1. แปลงเป็นสตริง binary ด้วย bin(N) (ได้ prefix "0b")
2. วนอ่านจากท้ายไปหน้า:
   • เจอ 'b' (จาก "0b") หยุดคืนผลลัพธ์
   • เจอ '0' บวกกำลังสองปัจจุบันเข้าผลรวม
   • คูณกำลังสองด้วย 2 ทุกรอบ

ตัวอย่างโค้ด

class Solution(object):
    def bitwiseComplement(self, N):
        s = str(bin(N))
        sum = 0
        num = 1
        for i in s[::-1]:
            if i == "b":
                return sum
            elif i == "0":
                sum += num
            num *= 2

ob1 = Solution()
print(ob1.bitwiseComplement(20))

อินพุต

20

เอาต์พุต

11

วิธีแก้แบบมีประสิทธิภาพมากกว่า

def bitwiseComplement(N):
    if N == 0:
        return 1
    # หา mask ที่เป็น 1 ทุกบิตถึงบิตสูงสุดของ N
    mask = (1 << N.bit_length()) - 1
    return mask ^ N

# หรือใช้ XOR กับ mask
def bitwiseComplement(N):
    if N == 0: return 1
    return ((1 << N.bit_length()) - 1) ^ N

อธิบาย: N.bit_length() ให้จำนวนบิตของ N mask = 2^bits - 1 (บิตทั้งหมดเป็น 1) XOR กับ N จะได้ complement