題目敘述
對於字串來說，Edit Distance是一個著名的DP問題。現在我們把這個問題弄得簡單一點，例如：把字串換成數字。對於一個數字$A$，我們想要藉由某些操作換成數字$B$。而對於整數$K$的一個合法的操作包括以下三種情形：
* 乘以 $2$ 加 $1$，即 $K=2K+1$
* 乘以 $2$，即 $K=2K$
* 除以 $2$，即 $K=\lfloor K/2\rfloor$
給定整數 $A$ 和 $B$，請你求出最小的操作次數 $N$使得從 $A$ 開始操作 $N$ 次可以換成 $B$。
輸入說明
包含兩個數字 $A, B$ ($0 \leq A, B \leq 2^{31}$)。
輸出說明
請輸出最小操作次數 $N$。
Sample Input
17
15
Sample Output
7
出處
95建中資訊培訓模擬試題一（Prob 3）
OJ連結
題解
把輸入的數字表示成二進位以後，所有的操作都會變成在當前的二進位字串後面加上一位數、或刪除一位數。考慮 $A$ 和 $B$ 的二進位值之後，他們的最長共同前綴（Longest Common Prefix）$S$，而最佳解就會是一路把 $A$ 除到變成 $S$，然後再一路加上 末尾的位元變成 $B$。
要把數字轉換成二進位的字串、再找出他們的最長共同前綴是一件好像有點麻煩的事情（雖然也不是太麻煩）。我們可以把「加上末尾的位元變成 $B$」的步驟反過來，變成從 $B$ 開始逐一刪除末尾的 0。這樣可以得到一個單純的演算法，重複比較 $A$ 和 $B$ 誰比較大，比較大的數字除以 2，直到相同為止。
/* by tmt514 */
#include <iostream>
using namespace std;
int main() {
int A, B, ans = 0;
cin >> A >> B;
while (A != B) {
(A > B? A : B) /= 2;
++ans;
}
cout << ans << endl;
return 0;
}
關於這題
這題的概念是二進位思考，如果把輸入的數字用不同的表示方法（比方說二進位）表示出來，那麼看似麻煩的操作就會變得很直觀。