---
title: "Codeforces Round 769 (Div. 2) C(枚舉)"
tags: 題解, 枚舉, 數學
---

https://codeforces.com/contest/1632/problem/C

#### 題意

給兩數 $a$, $b$ ($a$ < $b$)，有三種操作：

- $a$ += 1
- $b$ += 1
- $a$ |= $b$

問最少多少次操作可以讓 $a$ 和 $b$ 相等。

#### 思路

操作一會讓 $a$ 變大、操作二會讓 $b$ 變大、操作三會讓 $a$ 變成比 $b$ 大或等於 $b$。

若 $a$ 比 $b$ 大，只能做操作二來使其相等。

若 $a$ 比 $b$ 小，則可以調整 $a$ 或 $b$ 使 $b$ 變成 $a$ 的 submask，此時做操作三會讓二者相等。

另一種想法是：
遍歷所有可能的 $a$，對於每個 $a$ 找出最小的 $b$ 使得 $b$ 比原來的 $b$ 大且 $b$ 和 $a$ 在 bits 上差距最小。

做法上可以從高位開始看，遇到 $b$ 的 setbit 時同樣設為 setbit、不是 setbit 的話如果 $a$ 是 setbit 則設為 setbit 並更新答案；如果 $a$ 也不是 setbit 則不設為 setbit，因為往下繼續找可以有更小且滿足條件的 $b$。

#### Code

def solve():
    A, B = map(int, input().split())

    if A > B:
        print(A - B)
        return

    MAXV = A | B
    ans = B - A
    for a in range(A, MAXV + 1):
        if a | B == B: ans = min(ans, (a - A) + 1)
    for b in range(B, MAXV + 1):
        if A | b == b: ans = min(ans, (b - B) + 1)

    print(ans)

if __name__ == "__main__":
    for i in range(int(input())):
        solve()

def solve():
    A, B = map(int, input().split())

    if A > B:
        print(A - B)
        return

    ans = B - A
    for a in range(A, B + 1):
        b = 0
        for bit in range(20, -1, -1):
            if (B >> bit) & 1 == 1:
                b |= 1 << bit
            else:
                if (a >> bit) & 1 == 1:
                    b |= 1 << bit
                    break
        ans = min(ans, (a - A) + 1 + ((a | b) - B))

    print(ans)

if __name__ == "__main__":
    for i in range(int(input())):
        solve()