下面是一个递归的PHP函数用于计算所需的步骤数。它操作时会注意到有两种可能的要求：
- 将字符串转换为
0s（总体要求）；和
- 将字符串转换为
1后跟一串 0s（以允许翻转前一个数字）
第二个要求显然是第一个要求的扩展，因此可以编写一个递归函数来同时执行这两个操作。它有一个单个数字长度字符串的特殊情况，只需检查是否需要翻转即可。
function reduce($bits, $value = '0') {
if (strlen($bits) == 1) {
return ($bits[0] == $value) ? 0 : 1;
}
if ($bits[0] == $value) {
return reduce(substr($bits, 1));
}
return reduce(substr($bits, 1), '1') + 1 + reduce(str_pad('1', strlen($bits) - 1, '0'));
}
在3v4l.org上的演示
这个函数可以被改进，以存储实际采取的步骤，那么步骤数就是该数组的计数（减1，因为我们也将原始值放入了数组中）。为了存储步骤，我们需要跟踪字符串的前半部分（下面代码中的$prefix）以及我们正在缩短的部分：
function reduce($bits, $prefix, $value = '0') {
if (strlen($bits) == 1) {
return array($prefix . ($bits[0] == '0' ? '1' : '0'));
}
if ($bits[0] == $value) {
$prefix .= $bits[0];
return reduce(substr($bits, 1), $prefix);
}
$prefix .= $bits[0];
$steps = reduce(substr($bits, 1), $prefix, '1');
$prefix = substr($prefix, 0, -1) . ($bits[0] == '0' ? '1' : '0');
$steps[] = $prefix . str_pad('1', strlen($bits) - 1, '0');
$steps = array_merge($steps, reduce(str_pad('1', strlen($bits) - 1, '0'), $prefix));
return $steps;
}
您可以这样运行：
$bin = decbin($i);
$steps = array_merge(array($bin), reduce($bin, ''));
echo "$i ($bin) takes " . (count($steps) - 1) . " steps\n";
print_r($steps);
输入 8 的输出为：
8 (1000) takes 15 steps
Array
(
[0] => 1000
[1] => 1001
[2] => 1011
[3] => 1010
[4] => 1110
[5] => 1111
[6] => 1101
[7] => 1100
[8] => 0100
[9] => 0101
[10] => 0111
[11] => 0110
[12] => 0010
[13] => 0011
[14] => 0001
[15] => 0000
)
3v4l.org的演示
格雷码
观察这些步骤，我们可以看出这实际上是一种从原始值倒数到0的格雷码（反射二进制码）。因此，如果我们生成一个足够覆盖起始值的代码列表，我们可以简单地在该列表中查找起始值的二进制表示，这将给出我们回到0所需的步骤数：
function gray_code($bits) {
if ($bits == 1) {
return array('0', '1');
}
else {
$codes = gray_code($bits - 1);
return array_merge(array_map(function ($v) { return '0' . $v; }, $codes),
array_map(function ($v) { return '1' . $v; }, array_reverse($codes))
);
}
}
$value = 8;
$bin = decbin($value);
$gray_codes = gray_code(strlen($bin));
$codes = array_flip($gray_codes);
echo "$bin takes {$codes[$bin]} steps to reduce to 0\n";
for ($i = $codes[$bin]; $i >= 0; $i--) {
echo $gray_codes[$i] . PHP_EOL;
}
点击此处查看3v4l.org上的演示
如果您不需要单独的步骤，可以使用Gray码转二进制转换器来查找步骤数量。这非常快：
function gray_to_binary($value) {
$dec = $value;
for ($i = 1; $i < strlen($value); $i++) {
$dec[$i] = (int)$dec[$i-1] ^ (int)$value[$i];
}
return $dec;
}
echo bindec(gray_to_binary(decbin(115)));
输出：
93
3v4l.org上的演示
格雷码生成器
我们可以使用迭代的格雷码生成器来从原始代码中递减步骤。优点是它不会消耗任何内存来存储代码，因此可以处理非常大的数字。这个版本使用一个将格雷码转换为二进制的整数转换器，而不像上面那个使用字符串。
function gray_to_binary($value) {
$dec = 0;
$bits = floor(log($value, 2));
for ($i = $bits; $i >= 0; $i--) {
$dec = $dec | (((($dec >> ($i + 1)) ^ ($value >> $i)) & 1) << $i);
}
return $dec;
}
function iterate_gray($value) {
$code = decbin($value);
yield $code;
$len = strlen($code);
$count = gray_to_binary($value);
while ($count > 0) {
$xor = 1;
while (($count & $xor) == 0) $xor <<= 1;
$value ^= $xor;
yield sprintf("%0{$len}b", $value);
$count--;
}
}
foreach (iterate_gray(8) as $code) {
echo $code . PHP_EOL;
}
输出：
1000
1001
1011
1010
1110
1111
1101
1100
0100
0101
0111
0110
0010
0011
0001
0000
在 3v4l.org 上的演示
