Skip to content
Advertisement

Unsigned Right Shift / Zero-fill Right Shift / >>> in PHP (Java/JavaScript equivalent)

Before flagging this as a duplicate, please read below, and check my code * my updated code!

So my problem is that, I have to implement Java/JavaScript ‘>>>’ (Unsigned Right Shift / Zero-fill Right Shift), but I can’t get it work exactly the same way.

I’ve selected the 11 most promising implementations I’ve found on SO and on the web (links are added as comments in the code) and added a few test cases. Unfortunately NONE of the functions returned the same response as Java/JS to ALL of the tests. (Maybe some of them are only working on 32bit systems)

Live Code + JS+PHP results demo (click Run):
http://phpfiddle.org/main/code/bcv7-bs2q *
http://phpfiddle.org/main/code/dpkw-rxfe

The closest functions are:

// 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)); 
}

and

// 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; 
}

Unfortunately shr9 fails on (-10 >>> -3) and * (32 >> 32), but is the only to pass (-3 >>> 0); and shr11 fails on (-3 >>> 0) and also (32 >>> 32).

Test cases:

         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: I found that -3 >>> 0 is equals 4294967293 only in JavaScript (why?), but in Java, it equals -3. Unfortunately, this doesn’t change the fact that I still can’t get any function to pass all tests.


*BIG UPDATE:

Since PHP 7, bit shift by a negative number is considered to be invalid and causes: “Fatal error: Uncaught ArithmeticError: Bit shift by negative number“. According to this, I think we don’t have to pass those tests, so I’ve updated the question and the codes.

Advertisement

Answer

After looking into the two functions from the question (“shr9” and “shr11”) and merging/tweaking the good parts, I finally found the solution. All tests passed (I even added more in the demo), and it also works for shifts by a negative number.

[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 &= 0x7fffffff; 
        $a |= 0x40000000; 
        $a = ($a >> ($b - 1)); 
    } else { 
        $a = ($a >> $b); 
    } 
    return $a; 
}

This code is not just accurate, but fast too.
Benchmark results: 100000 loops in: 0.25 sec
Benchmark test: http://phpfiddle.org/main/code/mj68-1s7e

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement