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.
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