求解使非负整数A、B同时相等的最少操作次数

问题描述 #

给定两个非负整数A、B，试计算让二者变为相等值所需的最少操作次数。每一次操作可选择执行以下三种操作之一：

• 将A的值更新为 2*A
• 将B的值更新为 2*B
• 将A、B的值同时分别更新为 A-1、B-1

参考示例 #

当输入 A=7，B=25 时，最优操作序列如下：

1. 执行第三种操作，得到A=6、B=24
2. 执行第一种操作，得到A=12、B=24
3. 执行第一种操作，得到A=24、B=24

总计需要3次操作，无法通过更少的操作次数让两数相等。

复杂度要求 #

该问题为编程测试真题，输入A、B的规模可超过10^12，普通循环遍历类解法会超出时间限制，需设计时间复杂度足够低的高效求解方案。

内容的提问来源于stack exchange，提问作者boolean_life