将一个整数转换为另一个整数的最少步骤数

Question

最近遇到一个问题，给定两个整数A和B，我们需要用最少的步数将A转换为B。我们可以对A进行如下操作：

如果A是奇数，减1
如果A是偶数，则增加1
将 A（偶数或奇数）乘以 2
如果A是偶数，除以2

同样，我们必须找到将 A 转换为 B 所需的最少步骤数。

约束是0 < A, B < 10^18

我的做法：我尝试使用广度优先搜索来解决问题，将步骤中所有可能的可达数字添加到队列中，但它在更高的约束条件下失败，即超时。

谁能推荐一个更快的替代方案？

编辑：A 不一定小于 B

Answer 1

基本上你有以下操作：

翻转最低位
向左或向右移动位

假设，你有A == 0，你会如何构造B？对，你把低位一位一位翻转，把数字左移，比如B == 5，就是0x0101，你需要翻转2次，移位2次。

现在，我们必须处理 A != 0 的情况——在这种情况下，您必须将低位变为 0 并右移以清理混乱。比如你有A == 32，也就是0x0100000，你想得到5（0x0101），就得向右移三位，然后翻转低位就大功告成了。

所以，您所要做的就是：

数一数你需要做多少次flips/r-shifts，直到A的最高位等于B的最高位。
然后数一数flips/r-shifts你需要清理剩下的
数一数flips/left-shifts重建B的下半部分

好的，几个小时过去了，这是解决方案。首先是一个有用的函数，它说明我们需要多少次操作来创建一个数字：

def bit_count(num) :
    # the number of non-zero bits in a number
    return bin(num).count('1')

def num_ops(num) :
    # number of shifts + number of flips
    return num.bit_length() + bit_count(num)

现在，假设 A > B，否则我们可以交换它们，同时保持操作数不变。这是我们必须将 A 移动多远才能使其从与 B:

相同的位开始

needed_shifts = A.bit_length() - B.bit_length()

在这样做的同时，我们需要翻转一些位：

mask = (1 << (needed_shifts+1)) - 1
needed_flips = bit_count(A & mask)

现在我们计算清理 A 和重建 B 需要多少操作：

A >>= needed_shifts
clean_shifts = (A & ~B).bit_length()
clean_flips = bit_count(A & ~B)
rebuild_shifts = (B & ~A).bit_length()
rebuild.flips = bit_count(B & ~A)

最后大家一起总结一下：

result_ops = needed_shifts + needed_flips + max(clean_shifts,rebuild_shifts) * 2 + clean_flips + rebuils_flips

就这些了，伙计们！ =)

Answer 2

这个问题可以用动态规划优化。

我写了下面的代码，考虑了一些事情：

应该通过设置基本条件来小心避免无限递归。例如：如果 A=0 且 B<0，则不存在答案。
如果函数convert(A, B)在递归中被调用超过1次并且状态(A,B)的答案之前没有计算过，那么递归会因为不存在答案而终止对于这种情况。例如：(80, 100) -> (160, 100) -> (80->100) -> (160, 100) -> .......

这是通过将每个状态的计数维护到映射中并为 DP 的相同状态定义最大递归调用限制（以下程序中为 3）来完成的。

映射 dp 维护每个状态 (A, B) 的答案，映射 iterationsCount 维护调用相同状态 (A, B) 的次数计数。

看看下面的实现：

#include <utility> 
#include <iterator> 
#include <map>
#include <set> 
#include <iostream>
#include <climits>

typedef long long int LL;

std::map<std::pair<LL, LL>, LL> dp;

std::map<std::pair<LL, LL>, int > iterationsCount;

LL IMPOSSIBLE = (LL)1e9;

LL MAX_RECURSION_LIMIT = 3;

LL convert(LL a, LL b) 
{ 
//std::cout<<a<<" "<<b<<std::endl;

    // To avoid infinite recursion:
        if(iterationsCount.find(std::make_pair(a, b))!=iterationsCount.end() &&
        iterationsCount[std::make_pair(a,b)] > MAX_RECURSION_LIMIT &&
        dp.find(std::make_pair(a,b))==dp.end()){
            return IMPOSSIBLE;
        }

    // Maintaining count of each state(A, B)
        iterationsCount[std::make_pair(a, b)]++;

    LL value1, value2, value3, value4, value5;

    value1 = value2 = value3 = value4 = value5 = IMPOSSIBLE;

    if(dp.find(std::make_pair(a,b)) != dp.end()){
        return dp[std::make_pair(a, b)];
    }

    // Base Case 
    if(a==0 && b<0){
        return IMPOSSIBLE;
    }

    // Base Case 
    if (a == b) 
        return 0; 

    //Conditions
    if (a%2 == 1){

        if(a < b){

            value1 = 1 + convert(2*a, b);

        }

        else if(a > b){

            value2 = 1 + convert(a-1, b); 

        }
    }
    else{

        if(a < b){


            value3 = 1 + convert(a*2, b);



            value4 = 1 + convert(a+1, b);

        }

        else if(a > b){

            value5 = 1 + convert(a/2, b);

        }
    }

    LL ans = std::min(value1, std::min(value2, std::min(value3, std::min(value4, value5))));

    dp[std::make_pair(a, b)] = ans;

    return ans;
} 

int main(){

    LL ans = convert(10, 95);
    if(ans == IMPOSSIBLE){
        std::cout<<"Impossible";
    }else{
        std::cout<<ans;
    }
    return 0;
}

Answer 3

可用操作列表是对称的：2 组操作，每组相反：

最后一位可以翻转
如果低位为0，则可以左移一位或右移一位。

因此，从 A 到 B 或从 B 到 A 需要相同数量的操作。

从 A 到 B 最多需要从 A 到 0 的操作数加上从 [=13 的操作数=] 到 0。这些操作严格减少 A 和 B 的值。如果沿途可以从 A 和 B 达到中间值，则无需一直走到 0.

这是一个简单的函数，它在 A 和 B 上执行各个步骤，并在找到这个公共数字后立即停止：

def num_ops(a, b):
    # compute the number of ops to transform a into b
    # by symmetry, the same number of ops is needed to transform b into a
    count = 0
    while a != b:
        if a > b:
            if (a & 1) != 0:
                a -= 1
            else:
                a >>= 1
        else:
            if (b & 1) != 0:
                b -= 1
            else:
                b >>= 1
        count += 1
    return count

将一个整数转换为另一个整数的最少步骤数

Minimum number of steps to convert one integer to another

python

algorithm

bit-manipulation

bitwise-operators