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 R

Solution 1:

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

Solution 2:

As I was really out of ideas, I cloned the Chromium V8 engine and the Mozilla Central repo for getting SpiderMonkey. I started searching for the JS >>> operator, and finally in Mozilla's code, I found an almost 20 years old file (from 1997), js/src/tests/ecma/Expressions/11.7.3.js, which contained the operator-less code for testing "zero-filling bitwise right shift operation". After rewriting this in PHP, this code passed all the tests.

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

Usage example: UnsignedRightShift(10, 3); ( = 10 >>> 3 )

Disclaimer: I know that this is not even close to a "professional" solution, the performance is bad (4.33s with 110,000 loops; functions in question finish ~0.04s with 110,000 loops), and maybe there are even unnecessary functions in this snippet, but currently I only had time to implement it line by line. If anyone has a better solution, better performance or cleaner code, I'm more than happy to see it.