CODEWITHSUNDEEP
javascriptphpbit-manipulation
Nathan Jones
Nathan Jones

Reputation: 5174

Unsigned right shift function not working for negative input

I'm looking for a way to use the >>> function from JavaScript in the 64-bit version of PHP 5.5.14. I found this function in my googling:

function uRShift($a, $b) 
{ 
    $z = hexdec(80000000); 
    if ($z & $a) 
    { 
        $a = ($a >> 1); 
        $a &= (~$z); 
        $a |= 0x40000000; 
        $a = ($a >> ($b - 1)); 
    } else { 
        $a = ($a >> $b); 
    } 
    return $a; 
}

This function seems to work fine for positive numbers, but I get differing results when passing in negative numbers.

For example:

PHP:

In: echo uRShift(-672461345, 25);
Out: -149

JavaScript (Chrome 35):

In: -672461345 >>> 25
Out: 107

EDIT:

I also tried the other function mentioned in the answer linked above.

function uRShift($a, $b)
{
    if($b == 0) return $a;
    return ($a >> $b) & ~(1<<(8*PHP_INT_SIZE-1)>>($b-1));
}

PHP:

In: echo uRShift(-672461345, 25);
Out: 549755813867

Runnable

Upvotes: 1

Views: 385

Answers (1)

voithos
voithos

Reputation: 70582

The constant 0x80000000 (it's written as a call to hexdec and stored in the $z variable in this example) represents the lowest signed two's complement negative integer (100000.... in binary). The expression ~$z should give the bitwise NOT of this, namely, the highest signed positive integer (which ends up being 2147483647).

The original number (positive 0x80000000, that is, 2147483648) cannot be stored as a signed 32-bit integer, so normally it would be stored as a float of some kind. Unfortunately, PHP 5.5 thinks that ~(2147483648) is equal to -2147483649, which would be correct if we were dealing with e.g. 64-bit integers.

And indeed, echoing out PHP_INT_SIZE in runnable indicates that integers are 8 bytes, which is 64 bits. Thus, the arithmetic isn't working out right in PHP 5.5.

To remedy this, just replace the ~$z with a static constant, as follows:

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

This function still has some weaknesses; for example, shifting by 0 doesn't work properly.

Upvotes: 2

Related Questions