Vorzeichenlose Rechtsverschiebung/Nullfüllung Rechtsverschiebung in PHP (Java/JavaScript gleichwertig)

Question

Bevor Sie dies als Duplikat markieren, lesen Sie bitte unten und überprüfen Sie my code * my updated code!

Also mein Problem ist, dass ich Java/JavaScript ">>>" (Unsigned Rechts Shift/Zero-Fill Rechts Shift) implementieren muss, aber ich kann es nicht genau so funktionieren.

Ich habe die 11 vielversprechendsten Implementierungen ausgewählt, die ich auf SO und im Internet gefunden habe (Links werden als Kommentare im Code hinzugefügt), und ein paar Testfälle hinzugefügt. Leider KEINE der Funktionen gab die gleiche Antwort wie Java/JS für alle Tests zurück. (einige von ihnen arbeiten nur auf 32-Bit-Systeme Vielleicht)

Live Code + JS + PHP Demo führt (auf Ausführen):
http://phpfiddle.org/main/code/bcv7-bs2q *
http://phpfiddle.org/main/code/dpkw-rxfe

Die nächsten Funktionen sind:

// http://stackoverflow.com/a/27263298 
function shr9($a,$b) { 
    if($a>=0) return $a>>$b; 
    if($b==0) return (($a>>1)&0x7fffffff)*2+(($a>>$b)&1); 
    return ((~$a)>>$b)^(0x7fffffff>>($b-1)); 
} 

und

// http://stackoverflow.com/a/25467712 
function shr11($a, $b) { 
    if ($b > 32 || $b < -32) { 
     $m = (int)($b/32); 
     $b = $b-($m*32); 
    } 

    if ($b < 0) 
     $b = 32 + $b; 

    if ($a < 0) 
    { 
     $a = ($a >> 1); 
     $a &= 2147483647; 
     $a |= 0x40000000; 
     $a = ($a >> ($b - 1)); 
    } else { 
     $a = ($a >> $b); 
    } 
    return $a; 
} 

Leider scheitert shr9 an (-10 >>> -3) und * (32 >> 32), aber ist die nur zu übergeben (-3 >>> 0); und shr11 scheitert an (-3 >>> 0) und auch (32 >>> 32).

Testfälle:

  0 >>> 3 == 0 
     3 >>> 0 == 3 
     0 >>> -3 == 0 
     -3 >>> 0 == 4294967293 (in JS); -3 (in Java) 
     10 >>> 3 == 1 
     10 >>> -3 == 0 
     -10 >>> 3 == 536870910 
     -10 >>> -3 == 7 
-672461345 >>> 25 == 107 
     32 >>> 32 == 32 
     128 >>> 128 == 128 

Edit: Ich fand, dass -3 >>> 0 ist gleich 4294967293 nur in JavaScript , aber in Java, entspricht es -3 (warum?). Leider ändert dies nichts an der Tatsache, dass ich immer noch keine Funktion bekomme, alle Tests zu bestehen.

---

* BIG UPDATE:

Da PHP 7, Bitverschiebung durch eine negative Zahl wird als ungültig angesehen und führt zu: "Fatal error: Uncaught ArithmeticError: Bit Verschiebung um negative Zahl" . Daher denke ich, dass wir diese Tests nicht bestehen müssen, also habe ich die Frage und die Codes aktualisiert.

Answer 1

Nachdem ich die beiden Funktionen aus der Frage ("shr9" und "shr11") untersucht und die guten Teile zusammengeführt habe, fand ich endlich die Lösung. Alle Tests bestanden (ich habe sogar mehr in der Demo hinzugefügt), und es funktioniert auch für Verschiebungen um eine negative Zahl.

[Live Demo]

function unsignedRightShift($a, $b) { 
    if ($b >= 32 || $b < -32) { 
     $m = (int)($b/32); 
     $b = $b-($m*32); 
    } 

    if ($b < 0) { 
     $b = 32 + $b; 
    } 

    if ($b == 0) { 
     return (($a>>1)&0x7fffffff)*2+(($a>>$b)&1); 
    } 

    if ($a < 0) 
    { 
     $a = ($a >> 1); 
     $a &= 2147483647; 
     $a |= 0x40000000; 
     $a = ($a >> ($b - 1)); 
    } else { 
     $a = ($a >> $b); 
    } 
    return $a; 
} 

Dieser Code nicht nur genau, sondern auch schnell ist.
Benchmark-Ergebnisse: 100000 Schleifen in: 0.25 sec
Benchmark-Test: http://phpfiddle.org/main/code/mj68-1s7e

Answer 2

Da ich wirklich keine Ideen mehr hatte, klonte ich die Chromium V8 Engine und das Mozilla Central Repo, um SpiderMonkey zu bekommen. Ich begann nach dem JS >>> -Operator zu suchen, und schließlich in Mozillas Code, fand ich eine fast 20 Jahre alte Datei (von 1997), js/src/tests/ecma/Expressions/11.7.3.js, die den Operator-less-Code zum Testen "Null-Füllung bitweise rechts Verschiebung Operation enthielt ". Nach dem Umschreiben in PHP hat dieser Code alle Tests bestanden.

[LiveDemo]

<?php 

function ToInteger($n) { 
    $sign = ($n < 0) ? -1 : 1; 

    if ($n != $n) { 
    return 0; 
    } 
    if (abs($n) == 0 || abs($n) == INF) { 
    return $n; 
    } 
    return intval($sign * floor(abs($n))); 
} 

function ToInt32($n) { 
    $sign = ($n < 0) ? -1 : 1; 

    if (abs($n) == 0 || abs($n) == INF) { 
    return 0; 
    } 

    $n = ($sign * floor(abs($n))) % pow(2,32); 
    $n = ($n >= pow(2,31)) ? $n - pow(2,32) : $n; 

    return ($n); 
} 

function ToUint32($n) { 
    $sign = ($n < 0) ? -1 : 1; 

    if (abs($n) == 0 || abs($n) == INF) { 
    return 0; 
    } 

    $n = $sign * floor(abs($n)); 
    $n = $n % pow(2,32); 

    if ($n < 0){ 
    $n += pow(2,32); 
    } 

    return ($n); 
} 

function ToUint16($n) { 
    $sign = ($n < 0) ? -1 : 1; 

    if (abs($n) == 0 || abs($n) == INF) { 
    return 0; 
    } 

    $n = ($sign * floor(abs($n))) % pow(2,16); 

    if ($n <0) { 
    $n += pow(2,16); 
    } 

    return ($n); 
} 

function Mask($b, $n) { 
    $b = ToUint32BitString($b); 
    $b = substr($b, strlen($b) - $n); 
    $b = ToUint32Decimal($b); 
    return ($b); 
} 

function ToUint32BitString($n) { 
    $b = ""; 
    for ($p = 31; $p >=0; $p--) { 
    if ($n >= pow(2,$p)) { 
     $b .= "1"; 
     $n -= pow(2,$p); 
    } else { 
     $b .= "0"; 
    } 
    } 
    return $b; 
} 

function ToInt32BitString($n) { 
    $b = ""; 
    $sign = ($n < 0) ? -1 : 1; 

    $b .= ($sign == 1) ? "0" : "1"; 

    for ($p = 30; $p >=0; $p--) { 
    if (($sign == 1) ? $sign * $n >= pow(2, $p) : $sign * $n > pow(2,$p)) { 
     $b .= ($sign == 1) ? "1" : "0"; 
     $n -= $sign * pow(2, $p); 
    } else { 
     $b .= ($sign == 1) ? "0" : "1"; 
    } 
    } 

    return $b; 
} 

function ToInt32Decimal($bin) { 
    $r = 0; 
    $sign; 

    if (intval($bin[0]) == 0) { 
    $sign = 1; 
    $r = 0; 
    } else { 
    $sign = -1; 
    $r = -(pow(2,31)); 
    } 

    for ($j = 0; $j < 31; $j++) { 
    $r += pow(2, $j) * intval($bin[31-$j]); 
    } 

    return $r; 
} 

function ToUint32Decimal($bin) { 
    $r = 0; 


    for ($l = strlen($bin); $l < 32; $l++) { 
    $bin = "0" . $bin; 
    } 

    for ($j = 0; $j < 32; $j++) { 
    $r += pow(2, $j) * intval($bin[31-$j]); 

    } 

    return $r; 
} 

function RShift($s, $a) { 
    $s = ToUint32BitString($s); 
    for ($z = 0; $z < $a; $z++) { 
    $s = "0" . $s; 
    } 
    $s = substr($s, 0, strlen($s) - $a); 

    return ToUint32Decimal($s); 
} 

function UnsignedRightShift($s, $a) { 
    $s = ToUint32($s); 
    $a = ToUint32($a); 
    $a = Mask($a, 5); 
    return (RShift($s, $a)); 
} 

Anwendungsbeispiel: UnsignedRightShift(10, 3); (= 10 >>> 3)

Haftungsausschluss: Ich weiß, dass dies zu einer "professionellen" Lösung nicht einmal in der Nähe ist, ist die Leistung schlecht (4,33s mit 110,000 Loops; Funktionen in Frage fertig ~ 0,04s mit 110,000 Loops), und vielleicht gibt es sogar unnötige Funktionen in diesem Snippet, aber zur Zeit hatte ich nur Zeit, es Zeile für Zeile zu implementieren. Wenn jemand eine bessere Lösung, bessere Leistung oder saubereren Code hat, bin ich mehr als glücklich, es zu sehen.