Given a positive integer num, find its complement by flipping all bits in its binary representation. For example, 5 is 101 in binary, and its complement is 010 which is 2. We create a bitmask of all 1s with the same bit length as num, then XOR num with the mask to flip every bit.
Instead of building the full mask at once, iterate through each bit position of num and flip each bit individually by XORing with a shifting 1-bit.
""" 0476.1 - Solution 1 - Bit Mask XOR """
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findComplement(self, num: int) -> int:
"""Number Complement Function"""
# Create a mask of all 1s with the same bit length as num
mask = (1 << num.bit_length()) - 1
return num ^ mask
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findComplement(5)) # Expected: 2
print(Solution().findComplement(1)) # Expected: 0
print(Solution().findComplement(7)) # Expected: 0
print(Solution().findComplement(10)) # Expected: 5
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0476.2 - Solution 2 - Bit Flip Loop """
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findComplement(self, num: int) -> int:
"""Number Complement Function"""
result = num
bit = 1
while bit <= num:
result ^= bit
bit <<= 1
return result
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findComplement(5)) # Expected: 2
print(Solution().findComplement(1)) # Expected: 0
print(Solution().findComplement(7)) # Expected: 0
print(Solution().findComplement(10)) # Expected: 5
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()