アーカイブ

LeetCode 461. ハミング距離

旧アーカイブから保存した技術記事: LeetCode 461. ハミング距離。

· Record · Code · Code Block · Code Snippet · Java · Algorithm · Coding Interview · LeetCode · Hamming Distance

image

問題へのリンク

XOR は、x と y の同じ位置のビットが異なるとき、その位置を 1 にします。そのため x ^ y は異なるビット位置をすべて示し、Integer.bitCount はその 1 の個数、つまりハミング距離を数えます。

Java の整数幅は常に 32 ビットなので、時間計算量と追加領域の計算量はいずれも O(1)O(1) です。

class Solution {
    public int hammingDistance(int x, int y) {
        // XOR は入力間で異なるビット位置を 1 にする。
        // bitCount はその位置の数を数える。
        return Integer.bitCount(x ^ y);
    }
}