Back to course home
0% completed
Vote For New Content
Another approach
Miguel
May 6, 2024
Adding this here in a case a slightly different approach clicks for someone. The basic idea is that when you xor a bit with 1, you get the compliment (0^1 = 1; 1^1 = 0). To take advantage of this, we apply XOR to every bit of number to get the total complement:
import math class Solution: def bitwiseComplement(self, num): # Idea: xor every bit of num with 1 complement = 0 place_bit = 1 #start at place 1 places = math.ceil(math.log2(num)) # determine number of bits in num for _ in range(places): num_at_place_bit = place_bit & num #gives you the num's bit at the place_bit bit complement |= num_at_place_bit ^ place_bit #xor-ing with 1 gives you the complimentary bit; |= accumulates the result with previous results place_bit = place_bit << 1 #shift place bit to the next position return complement
From here, you can see that we are essentially applying XOR to every bit in our original number with 1. We can save ourselves some time by instead applying XOR by 1 to every bit at the same time. This is essentially the all_bit_set number and strategy mentioned in the official solution.
0
0
Comments
Comments
P
Pete Stengera year ago
bit = 1 res = 0 while num >= bit: if num & bit == 0: res += bit bit <<= 1 return res
On this page