格雷码生成 - n 位格雷码

Question

这个问题是由hackerrank提出的，我得到了解决方案，但是在最后的测试用例中，解决方案中存在问题。

问题如下。

1 <= $n <= 65

以下是 1 位序列 (n = 1)

0 1

输出

1

以下是 2 位序列 (n = 2)

00 01 11 10

输出

11 10

以下是 3 位序列 (n = 3)

000 001 011 010 110 111 101 100

输出

111 101 100

以下是 4 位序列 (n = 4)

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 
1110 1010 1011 1001 1000

输出

1010 1011 1001 1000

解决方案示例

以下是从 2 位格雷码列表生成 3 位格雷码列表的步骤。

• L1 = {00， 01， 11， 10} (2 位格雷码列表)
• L2 = {10， 11， 01， 00} (L1 的反面)
在 L1
• 的所有条目前面加上"0"，L1 变为 {000， 001， 011， 010}
在 L2
• 的所有条目前面加上"1"，L2 变为 {110， 111， 101， 100}
• 连接 L1 和 L2，我们得到 {000， 001， 011， 010， 110， 111， 101， 100}

下面给出了第一个解决方案。基于上面的解决方案示例)

但是下面的给定解决方案在 22,23 个数字之后将不起作用。 发生内存分配错误。

<?php
$input = 2;
$list_array = ["0","1"];
$reverse_array = array_reverse($list_array);
for($i = 1; $i < $input; $i++ )
{
for($j = 0; $j < sizeof($list_array); $j++)
{
$list_array[$j] = "0".$list_array[$j];
}
for($k = 0; $k < sizeof($reverse_array); $k++)
{
$reverse_array[$k] = "1".$reverse_array[$k];
}
$list_array = array_merge($list_array,$reverse_array);
$reverse_array = array_reverse($list_array);
}
for($l = sizeof($list_array) - $input; $l < sizeof($list_array); $l++)  
{
print_r($list_array[$l]);
echo "<br />";
}
?>

下面给出了第二个解决方案

此解决方案将工作到 63。在 63 之后，将显示超时错误。

当 64 位 php 在 64 位操作系统上运行时，这将工作到 63 位。 如果是在 64 位操作系统上运行的 32 位 php，则在 31 位操作系统之后将不起作用。

<?php
$n = 59;
$intial = pow(2, $n) - $n;
$length = pow(2, $n) - 1;
for($i= $intial; $i <= $length; $i++)
{
$decimal = ($i >> 1) ^ $i;
print_r(decbin($decimal));
echo "<br />";
}
?>

请帮助我找到此解决方案。

问题：如何解决上述包括$n = 64和$n = 65

参考资料： https://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-bit/

Answer 1

这应该适合您：

<?php
print_r( getResult( 4 ) );
function getResult ( $n ) {
$result = [];
for ( $i = 0; $i < $n; $i++ ) {
$result[] = arr_xor(
str_split( str_pad( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), $n, '1', STR_PAD_LEFT ) ),
str_split( '0' . str_pad( substr( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), -1-(int)ceil(log($n - $i - 1, 2)), -1), $n - 1, '1', STR_PAD_LEFT ) )
);
}
return $result;
}
function arr_xor( $a, $b ) {
$result = [];
for ( $i = 0; $i < count( $a ); $i++ )
$result[] = (int)$a[$i] ^ (int)$b[$i];
return implode( '', $result );
}

它只使用第二个解决方案(($i >> 1) ^ $i)中的公式，但由于你不能将其用于大于PHP_INT_MAX的整数，它使用一个数组，每个元素代表一个位。这不是最有效的解决方案，但可以轻松超过 65。$n = 1000似乎没有问题。

Answer 2

另一个答案，它与@paulpro相似，与我在第二个解决方案中应用的想法相同。($i >> 1) ^ $i

<?php
$n = 65;
for ( $i = 0; $i < $n; $i++ ) 
{
$decimal = decbin($n - $i - 1);
$replace = strtr( $decimal, '01', '10' );
$cast = (int)ceil(log($n - $i - 1, 2));
$padding = str_pad( $replace , $cast , '0', STR_PAD_LEFT );
$a_string = str_pad( $padding, $n, '1', STR_PAD_LEFT );
//shifting the bit to right
$substring = substr( $a_string , 0 , -1);
$b_string = str_pad( $substring , $n, '0', STR_PAD_LEFT );
$a = str_split( $a_string );
$b = str_split( $b_string );
for ( $j = 0; $j < count( $a ); $j++ )
{
print_r((int)$a[$j] ^ (int)$b[$j]);
}
echo "n";
}
?>