LeetCode: Number Complementを解く

問題

LeetCode 30-Day LeetCoding Challengeが終わり May Leetcoding Challange Complementが始まりました。 （まさかの1ヵ月延長です...）

leetcode.com

ビット演算の問題です。

解き方

与えられた数字(num)を以下の数式を用いて、二進数時のビット長を計算します。

そして、ビット長の分だけある1だけのビットマスクを作りそこからnumを引けば、ビット反転が得られます。 以下のような形です。

1111 - 0111(7) = 1000

ビット長の分だけある1だけのビットマスクは、ビット長の分だけ左にビットシフトし 1を引いてあげれば作れます。以下が雑な図

回答

from math import log2

class Solution:
    def findComplement(self, num: int) -> int:
        bitLength = floor(log2(num)) + 1
        return (1 << bitLength) - 1 - num

LeetCode上の解答は、1のビットマスクを作ってXORを取っていました。

from math import log2

class Solution:
    def findComplement(self, num: int) -> int:
        bitLength = floor(log2(num)) + 1
        return ((1 << bitLength) - 1 ) ^ num

計算量

時間計算量: O(1) 空間計算量: O(1)