Смещение вправо без знака / Сдвиг вправо с нулевым заполнением / & gt; & gt; & gt; в PHP (эквивалент Java / JavaScript)

Прежде чем пометить это как дубликат, пожалуйста, прочитайте ниже, и проверьте мой код * мой обновленный код!

Так что моя проблема в том, что я должен реализовать Java / JavaScript ‘>>>’ (беззнаковое правое смещение / нулевое заполнение правого смещения), но я не могу заставить его работать точно так же.

Я выбрал 11 наиболее многообещающих реализаций, которые я нашел в SO и в Интернете (ссылки добавляются как комментарии в коде), и добавил несколько тестовых случаев. к несчастью НИКТО из всех функций вернул тот же ответ, что и Java / JS. (Может быть, некоторые из них работают только на 32-битных системах)

Демонстрация результатов Live Code + JS + PHP (нажмите Run):
http://phpfiddle.org/main/code/bcv7-bs2q *
http://phpfiddle.org/main/code/dpkw-rxfe

Ближайшие функции:

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

а также

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

К сожалению shr9 не работает (-10 >>> -3) и * (32 >> 32), но это только пройти (-3 >>> 0); и shr11 не срабатывает (-3 >>> 0), а также (32 >>> 32).

Тестовые случаи:

         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

Изменить: я обнаружил, что -3 >>> 0 равно 4294967293 только в JavaScript (Зачем?), но в Java это равно -3, К сожалению, это не меняет того факта, что я до сих пор не могу заставить любую функцию пройти все тесты.


* БОЛЬШОЕ ОБНОВЛЕНИЕ:

Начиная с PHP 7, битовое смещение на отрицательное число считается недействительным и вызывает: «Неустранимая ошибка: Uncaught ArithmeticError: сдвиг бита на отрицательное число«В соответствии с этим, я думаю, что мы не должны проходить эти тесты, поэтому я обновил вопрос и коды.

6

Решение

Изучив две функции из этого вопроса («shr9» и «shr11») и объединив / настроив хорошие части, я наконец нашел решение. Все тесты пройдены (я даже добавил больше в демо), и это также работает для сдвигов на отрицательное число.

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

Этот код не только точный, но и быстрый.
Результаты теста: 100000 циклов за 0,25 сек.
Контрольный тест: http://phpfiddle.org/main/code/mj68-1s7e

4

Другие решения

Поскольку у меня действительно не было идей, я клонировал движок Chromium V8 и репозиторий Mozilla Central для получения SpiderMonkey. Я начал поиск оператора JS >>> и, наконец, в коде Mozilla я нашел файл почти 20 лет (с 1997 года), JS / SRC / тесты / ECMA / Выражение / 11.7.3.js, который содержал безоператорский код для тестирования «битовая операция правого сдвига с нулевым заполнением». После переписывания этого на PHP этот код прошел все тесты.

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

Пример использования:
UnsignedRightShift(10, 3); (= 10 >>> 3)

Отказ от ответственности: я знаю, что это даже не близко к «профессиональному» решению, производительность плохая (4,33 с 110 000 циклов; рассматриваемые функции заканчивают ~ 0,04 с 110 000 циклов), и, возможно, в этом фрагменте есть даже ненужные функции , но в настоящее время я только успел реализовать это построчно. Если у кого-то есть лучшее решение, лучшая производительность или более чистый код, я более чем рад его видеть.

2