# ZJ m399 - print(max(A,B)) 題解

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 初步想法

首先把問題先想成兩個部分 : 要怎麼知道在沒有 if 和大於小於運算子來知道 $A$、$B$ 哪個比較大，以及要怎麼用前面的結果來回傳答案。

後面那個部分比較簡單，假設經過一輪運算後可以得到一個值 $x$，$x = 0$的時候代表 $A>B$，而 $x = 1$ 的時候則 $B\geq A$。那我們可以把答案表示成 $(A \times (x\ xor\ 1) + B \times x)$，而接著我們要想辦法算出 $x$，計算 $x$ 的方法其實有很多種，下面介紹其中的三種方法。

### 方法1: 利用減法操作所造成的溢位

題目的減法操作所造成的 overflow，會讓 $2^{63}$ 的這個 bit 值改變。在比大小的時候，首先如果 $A, B$ 在 $2^{63}$ 這個的 bit 如果不同，因為它是最大的位數，所以就已經可以判斷出 $A, B$ 的大小；如果 $A, B$ 在 $2^{63}$ 這個的 bit 相同，在 $2^{63}$ 這個的 bit 相減的話會被消除 (都是 $1$ 的話會互消，$0$ 的話就沒這問題)，所以結論是變成兩個 $< 2^{63}$ 的數相減，如果$A - B$減出來變負的，就會因為 overflow 讓 $2^{63}$ 這個的 bit 變成 $1$ ，反之這個 bit 為 $0$，我們可以用上述的方法算出我們要的 $x$ 。(本作法由 korinoba 提供)

### 方法2: 類方法1

概念和前面一樣，只是故意讓「$A$、$B$」都變成 $< 2^{63}$ ，就是在一開始的時候直接將 $A, B$ 都先除以 $2$，如果相同再根據最低的 bit 的情況回傳答案。

### 方法3: 利用除法操作的特性

前面用到的是減法的特性，而答案也可以用除法計算，可以先令一個函數$f(x)=$

\begin{cases}
1 , x>=1 \\
0 , x=0 \\
\end{cases}

則 $x$ 實際上可以用 $A \times f(\frac{A}{B}) + B \times f(\frac{B}{A}) - A \times (f(A \ xor \ B) \ xor \ 1)$ 來表示，其中，還必須特別避免 $A = 0$ 與 $B = 0$ 的情況。在 $A=0$ 且 $B \ne 0$ 或 $B=0$ 且 $A \ne 0$ 時，可以直接把 $= 0$ 的數字 $+1$ （這裡用到了 $A += f(A) \times 1$ ， $B$ 的做法也是如此），可以發現這樣做不會影響答案的值。否則若 $A=0$ 且 $B=0$ 時 ，同樣可以把 $A,B$ 都 $+1$ ，但要記得對最後的答案做特殊處理（記得 $-1$）。
(本做法由 Ststone 提供)

### 分析

上面的三種都可以在適當的實作下完成題目要求的目標。