LeetCoding Challenge Oct. 5: Complement of Base 10 Integer

1 min read読了の目安(約800字

LeetCode October Challenge の 5 日目。

今日は Complement of Base 10 Integer

問題の概要

  • 与えられた 0 以上の整数 (10^9 未満) を 2 進数で表現したときの 1 の補数を求める
    • 32 ビット整数の 1 の補数を求める、 というわけではない

実装の手順・考え方

  • 整数 N を 2 進数で表現するのに必要な (= 先頭のゼロを取り除いた) ビット数だけ、ビット XOR すればいいだけの簡単な問題ですね!
    • もうちょっと具体的にすると、N を 2 進数表現したときの先頭の 0 を数え上げて c とする → 下位 32 - c ビットの部分だけ XOR する、となる
  • 先頭のビット 0 の個数を数えるのはみんな大好き lzcnt ですね!
    • Java だと Integer.numberOfLeadingZeros() メソッドになる
  • さくっと実装して submit → ああっ! N = 0 のケースを考慮してなかった 😱
    • 分岐なしの実装でいけるかと思ったが、ちょっと思いつかなかったので仕方なく Math.min() を使う方法で妥協する
  • N = 0 を考慮して submit → runtime 0ms 達成 🎉

コード

class Solution {
    public int bitwiseComplement(int N) {
        return N ^ (0xffff_ffff >>> Math.min(Integer.numberOfLeadingZeros(N), 31));
    }
}