rog*_*hat 4 java algorithm bit-manipulation
正在从事编程工作，并被困于找出正确的算法。这是问题所在：
给定一个十进制数，需要多少个最小可能的步骤才能将其转换为零：
- 如果下一位i + 1为'1'，则更改位i，其余所有其他位i + 2及更高版本为0。
- 无限制地更改最后一位
例如：
如果输入为（8）Base10 =（1000）Base2，则采取的步骤为：
1000?1001?1011?1010?1110?1111?1101?1100?0100?0101?0111?0110?0010?0011?0001?0000
总共需要15个步骤。
完成以下定义：
int minStepsRequired(long number)
可以获取伪代码或仅获取算法。这不是家庭作业或作业。
起初，我试图用递归深度优先函数（在 NodeJS 中）来解决它，但它只适用于小数字 -10^5由于堆栈中递归调用的数量，输入值会产生运行时错误。
然后我试图看看如何将问题简化为较小问题的总和，并发现 N 的步数，即 N 的 2 的幂，是
N * 2 - 1
（例如：2 的步数是 3，32 是 63，256 是 511，依此类推）。
然后我找到了如何处理任何其他数字（不是 2 的幂），并且由于任何整数都是 2 的不同幂的总和（因此是二进制表示），我只需要看看步数是否会加起来也是......但事实并非如此。但是，我确实发现我不仅要从 2 的每一次幂中添加步数，还要
从最高位数字开始，以交替方式减去和添加步骤
给定数字42（101010二进制）
让我们首先应用规则#1
1 0 1 0 1 0
^ ^ ^ ^ ^ ^
| | | | | |_ 0 steps
| | | | |___ 2*2-1 = 3 steps
| | | |_____ 0 steps
| | |_______ 2*8-1 = 15 steps
| |_________ 0 steps
|___________ 2*32-1 = 63 steps
其次，应用规则#2：
63 - 15 + 3 = 51
总步数为51
1 0 1 0 1 0
^ ^ ^ ^ ^ ^
| | | | | |_ 0 steps
| | | | |___ 2*2-1 = 3 steps
| | | |_____ 0 steps
| | |_______ 2*8-1 = 15 steps
| |_________ 0 steps
|___________ 2*32-1 = 63 steps
这是一个递归 PHP 函数，用于计算所需的步骤数。它通过注意到有两个可能的要求来运作：
0s（总体要求）；和1后跟0s的字符串（以允许翻转前面的数字）第二个要求显然是第一个要求的扩展，因此可以编写一个递归函数来实现两者。它对单个数字长度字符串有一个特殊情况，只是检查它是否需要翻转。
function reduce($bits, $value = '0') {
if (strlen($bits) == 1) {
// a single bit can be flipped as needed
return ($bits[0] == $value) ? 0 : 1;
}
if ($bits[0] == $value) {
// nothing to do with this bit, flip the remainder
return reduce(substr($bits, 1));
}
// need to convert balance of string to 1 followed by 0's
// then we can flip this bit, and then reduce the new string to 0
return reduce(substr($bits, 1), '1') + 1 + reduce(str_pad('1', strlen($bits) - 1, '0'));
}
这个函数可以用来存储实际采取的步数，那么步数就是该数组的计数（-1，因为我们也将原始值放入了数组中）。为了存储步骤，我们需要跟踪字符串的第一部分（$prefix在下面的代码中）以及我们正在减少的部分：
function reduce($bits, $prefix, $value = '0') {
if (strlen($bits) == 1) {
// a single bit can be flipped as needed
return array($prefix . ($bits[0] == '0' ? '1' : '0'));
}
if ($bits[0] == $value) {
// nothing to do with this bit, flip the remainder
$prefix .= $bits[0];
return reduce(substr($bits, 1), $prefix);
}
// need to convert balance of string to 1 followed by 0's
$prefix .= $bits[0];
$steps = reduce(substr($bits, 1), $prefix, '1');
// now we can flip this bit
$prefix = substr($prefix, 0, -1) . ($bits[0] == '0' ? '1' : '0');
$steps[] = $prefix . str_pad('1', strlen($bits) - 1, '0');
// now reduce the new string to 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
)
格雷码
查看步骤我们可以看到这实际上是一个格雷码（反射二进制码）从原始值向下计数到 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);
// get sufficient gray codes to cover the input
$gray_codes = gray_code(strlen($bin));
$codes = array_flip($gray_codes);
echo "$bin takes {$codes[$bin]} steps to reduce to 0\n";
// echo the steps
for ($i = $codes[$bin]; $i >= 0; $i--) {
echo $gray_codes[$i] . PHP_EOL;
}
如果您不需要单独的步骤，您可以使用格雷码到二进制转换器来查找步骤数。这是超快的：
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
格雷码生成器
我们可以使用迭代格雷码生成器从原始代码中计算步骤。这样做的好处是它不消耗任何内存来存储代码，因此它可以用于非常大的数字。此版本使用格雷码到二进制转换器，可以像上面那样处理整数而不是字符串：
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) {
// get the equivalent starting binary value
$code = decbin($value);
yield $code;
$len = strlen($code);
$count = gray_to_binary($value);
while ($count > 0) {
// flip the bit which corresponds to the least significant 1 bit in $count
$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
对于递归算法来说，这是一个奇妙的问题。
如果二进制表示的长度为0，则您已经可以说出答案了。或者，如果不允许长度为0，则如果长度为1，则根据该位是0还是1来告诉答案。
如果长度大于1：
该算法可能需要很长时间。它实际上是在计算步数，因此所花费的时间与步数成正比，我认为这大致与输入数成正比。您的方法带有一个long参数，但是使用我的算法来获取较大的long值时，它可能不会在运行计算机的生命周期内终止。同样，步数可能会溢出一个int甚至一个long（如果输入为负值long）。
快乐的编码。如果那是我，我将实际编码并运行它以验证我是否正确。
以下解决方案不需要递归，并且可以在恒定时间内运行。我无法正确解释它是如何工作的，如果我们想将其用于某些东西，这是一个严重的问题。我玩了一些示例，看到了一个模式并对其进行了概括。相比之下，恕我直言，上述递归解决方案的某些优点在于它易于理解（如果您了解递归）。
示例：输入8或1000二进制。结果15或1111二进制。模式是：结果的每个位是结果的前一个位与输入中相同位置的位的异或。因此，1000仅复制前一位1。下一位是1 XOR 0 = 1，其中1是结果的前位，而0则取自输入。其余两位的计算方法相同。
一个更长的示例，因此您可以检查您是否了解：
Input: 115 = 1110011
Result: 1011101 = 93
或在代码中：
static BigInteger calculateStepsRequired(long number) {
// Take sign bit
int bit = number < 0 ? 1 : 0;
BigInteger result = BigInteger.valueOf(bit);
for (int i = 0; i < 63; i++) {
number = number << 1;
int sign = number < 0 ? 1 : 0;
bit = (bit + sign) % 2;
result = result.shiftLeft(1).add(BigInteger.valueOf(bit));
}
return result;
}
我已经根据我自己对上面第一个算法的实现（使用高达100000000的各种输入）检查了该方法，并且他们始终同意，因此我相信快速方法也是正确的。