LoginSignup
0

More than 5 years have passed since last update.

[checkio] The hamming distance

Last updated at Posted at 2017-07-01

どうしても解けない問題があってなかなか更新できずついに先へ進むことを決めたワイ将。悲しい

今回の問題は引数として与えられた2つの10進数の数値のハミング距離を求める。そもそもハミング距離とはなんぞや。
wiki先生によると

情報理論において、ハミング距離(ハミングきょり)とは、等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。別の言い方をすれば、ハミング距離は、ある文字列を別の文字列に変形する際に必要な置換回数を計測したものである。この用語は、リチャード・ハミング(Richard Wesley Hamming)にちなんで命名されたもので、鼻歌(humming)ではない。 https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2

とのこと。うむわからん。エラーの概算を数えたりするのにこの考え方が必要らしい。ひとまず内容としては同じ長さの文字列または数列を比べて、相対位置の違う箇所を数える。今回の問題では10進数を2進数に直した上で差分を数える。

自分の回答

function hammingDistance(n, m){
    let na = dmake(n);
    let ma = dmake(m); 
    let distance = 0;
    alignLength(na,ma);


    for (let i=0; i<na.length; i++) {
        if (na[i] != ma[i]) {
            distance += 1;
        }
    }



    //make it decimal 
    function dmake(num) {
        let array = [];
        let tarnum = 1;
        while ((num/2)>=tarnum && num!=1) {
            tarnum *= 2;
        }
        console.log("num is "+num);
        console.log("tarnum is "+tarnum);
        while(num!=0) {
            if(num >= tarnum) {
                num -= tarnum;
                array.push(1);
                if (num==0&&tarnum!=1) {
                    while (tarnum!=1) {
                        array.push(0);
                        tarnum /= 2;
                    }
                }
            } else {
                array.push(0);
            }
            tarnum/=2;
        }
        return array
    }

    //aling the array length
    function alignLength(a, b) {
        if (a.length != b.length) {
            let lengDiff = Math.abs(a.length-b.length);
            if (a.length > b.length) {
                for (let i = 0; i<lengDiff; i ++) {
                    b.unshift(0);
                }
            }
            else if (b.length > a.length) {
                for (let i = 0; i<lengDiff; i ++) {
                    a.unshift(0);
                }
            }
        }
    }

    console.log(na);
    console.log(ma);

    return distance
}

だいぶ長くなってしまった。探せば2進数に直すメソッドとかあるんだろうけど自分で書いてみた。意外と考えなければいけないパターンは隠れている。

すごいとおもったかいとう

function hammingDistance(n, m){
    var h = n ^ m;
    var count=0;
        while (h) {
            h = h&(h-1);
            count++;
}
return count;
}

うむ、全くわからん。
2行目では排他的論理和をhに格納。
3行目ではcount upするための変数を定義。
4-6のwhileブロックでは、
hとh-1のビットごとの論理積を出して、最終的にhが1になり、論理積の値が0になってwhileが止まるまで続ける。
この式を繰り返すことがなぜ2進数でのhの1を数えるのと同じになるのかはわからん。時間のある時にブール関数を勉強してみよう。

学び

number.toString()

  • 引数として受け取った数値を基準とし、numberを表す文字列を返す。引数を指定しなければ文字列オブジェクトに変換するだけ。

^ (排他的論理和)

  • ビット演算子の一つ。10進数の数値に使うと、右辺左辺それぞれを2進数に直した上で、差分の数値を10進数として返してくれる。

& (論理積)

  • ビット演算子の一つ。2つのオペランドの論理積を返す。

反省

ブール関数を勉強してみる。
全くわからん。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0