LeetCoding Challenge Oct. 5: Complement of Base 10 Integer

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));
    }
}