LeetCode_461. Hamming Distance
3136 ワード
/*The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.*/
xとyのバイナリビットの中で、異なる個数を見つける.
自分の考えでx,yをバイナリストレージに変換し、比較した結果、タイムアウトしました.
正しい方法はビット演算,x異あるいはyを用いて得られたzである.
肝心なのはzがどれだけの1があるかを計算することで、方法:zとz-1で演算します;このような和演算は毎回右端の1を0に変え、最後にzが0になるまで行われる.
Given two integers x and y, calculate the Hamming distance.*/
xとyのバイナリビットの中で、異なる個数を見つける.
自分の考えでx,yをバイナリストレージに変換し、比較した結果、タイムアウトしました.
var hammingDistance = function(x, y) {
var MAX = Math.pow(2, 32);
if (x < 0 || y < 0 || x > MAX || y > MAX) {
console.log("max");
return false
}
var arr1 = revertTobit(x);
var arr2 = revertTobit(y);
while (arr1.length != arr2.length) {
if (arr1.length < arr2.length) {
arr1.unshift(0);
} else {
arr2.unshift(0)
}
}
var count = 0;
for (var i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
count++;
}
}
return count;
};
/* */
var revertTobit = function(x) {
var arr = [];
while (x != 1) {
var bit = x % 2;
x = Math.floor(x / 2);
arr.unshift(bit);
}
arr.unshift(1);
return arr;
}
正しい方法はビット演算,x異あるいはyを用いて得られたzである.
肝心なのはzがどれだけの1があるかを計算することで、方法:zとz-1で演算します;このような和演算は毎回右端の1を0に変え、最後にzが0になるまで行われる.
var hammingDistance = function(x, y) {
var count = 0;
var n = x ^ y;
while (n) {
++count;
n = (n - 1) & n;
}
return count;
};