Прежде чем отмечать это как дубликат, прочитайте ниже, и проверьте мой код * мой обновленный код !
Поэтому моя проблема заключается в том, что я должен реализовать Java / JavaScript '>>>' (Беззнаковый правый сдвиг / нулевой-заполняющий правый сдвиг), но я не могу заставить его работать точно так же.
Я выбрал 11 наиболее перспективных реализаций, которые я нашел в SO и в Интернете (ссылки добавлены в виде комментариев в коде) и добавил несколько тестовых примеров. К сожалению, NONE из функций возвратил тот же ответ, что и Java / JS, ко всем испытаниям. (Возможно, некоторые из них работают только на 32-битных системах)
Демо-версия Live Code + JS + PHP (нажмите «Выполнить»):
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 сдвиг бита отрицательным числом считается недействительным и вызывает: « Неустранимая ошибка: не показано ArithmeticError: сдвиг бит по отрицательному числу ». В соответствии с этим, я думаю, нам не нужно проходить эти тесты, поэтому я обновил вопрос и коды.
Поскольку у меня действительно были идеи, я клонировал двигатель Chromium V8 и центральный репозиторий Mozilla Central для получения SpiderMonkey. Я начал искать оператор JS >>> и, наконец, в коде Mozilla, я нашел почти 20-летний файл (с 1997 года), js / src / tests / ecma / Expressions / 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.33s с 110 000 циклов, функции заканчиваются ~ 0.04 с 110 000 циклов), и, возможно, в этом фрагменте есть даже ненужные функции , но в настоящее время я только успел реализовать его по строкам. Если у кого-то есть лучшее решение, более высокая производительность или более чистый код, я более чем счастлив увидеть его.
Изучив две функции из вопроса («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 &= 2147483647; $a |= 0x40000000; $a = ($a >> ($b - 1)); } else { $a = ($a >> $b); } return $a; }
Этот код не только точный, но и быстрый.
Результаты тестов: 100000 циклов в: 0,25 сек.
Тест производительности: http://phpfiddle.org/main/code/mj68-1s7e