Have Geek Brain

How to calculate the humming distance of two binary sequences in PHP?

hamming('10101010','01010101')

The result should be higher 8

.

How to implement it?

+2


a source to share


7 replies


no GMP established here's a simple solution for any binary strings of the same length



function HammingDistance($bin1, $bin2) {
    $a1 = str_split($bin1);
    $a2 = str_split($bin2);
    $dh = 0;
    for ($i = 0; $i < count($a1); $i++) 
        if($a1[$i] != $a2[$i]) $dh++;
    return $dh;
}

echo HammingDistance('10101010','01010101'); //returns 8
+5


a source


You don't need to implement it as it already exists: http://php.net/manual/en/function.gmp-hamdist.php



(If you have GMP support)

+2


a source


If you don't have GMP support, there is always something like this. At the bottom, it only works with binary strings up to 32 bits long.

function hamdist($x, $y){
  for($dist = 0, $val = $x ^ $y; $val; ++$dist){ 
      $val &= $val - 1;
  }
  return $dist;
}

function hamdist_str($x, $y){
    return hamdist(bindec($x), bindec($y));
}


echo hamdist_str('10101010','01010101'); //8
+1


a source


The following function works with hexadecimal strings (equal to length) that are more than 32 bits long.

function hamming($hash1, $hash2) {
        $dh = 0;

        $len1 = strlen($hash1);
        $len2 = strlen($hash2);
        $len = 0;

        do {
            $h1 = hexdec(substr($hash1, $len, 8));
            $h2 = hexdec(substr($hash2, $len, 8));
            $len += 8;
            for ($i = 0; $i < 32; $i++) {
                $k = (1 << $i);
                if (($h1 & $k) !== ($h2 & $k)) {
                    $dh++;
                }
            }
        } while ($len < $len1);

        return $dh;
    }
+1


a source


Try:

echo gmp_hamdist('10101010','01010101')
0


a source


Try this function:

function hamming($b1, $b2) {
    $b1 = ltrim($b1, '0');
    $b2 = ltrim($b2, '0');
    $l1 = strlen($b1);
    $l2 = strlen($b2);
    $n = min($l1, $l2);
    $d = max($l1, $l2) - $n;
    for ($i=0; $i<$n; ++$i) {
        if ($b1[$l1-$i] != $b2[$l2-$i]) {
            ++$d;
        }
    }
    return $d;
}
0


a source


With help substr_count()

and code provided in this PHP manual comment .

/* hamdist is equivilent to: */
echo gmp_popcount(gmp_xor($ham1, $ham2)) . "\n";
0


a source






More articles:


All Articles