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

<<回主頁

初步想法

首先把問題先想成兩個部分 : 要怎麼知道在沒有 if 和大於小於運算子來知道

$A$、

$B$ 哪個比較大，以及要怎麼用前面的結果來回傳答案。

後面那個部分比較簡單，假設經過一輪運算後可以得到一個值

$x$，

$x=0$的時候代表

$A>B$，而

$x=1$ 的時候則

$B\ge A$。那我們可以把答案表示成

$(A\times (xxor1)+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{array}{l}1,x>=1\\ 0,x=0\end{array}$$

則

$x$ 實際上可以用

$A\times f(\frac{A}{B})+B\times f(\frac{B}{A})-A\times (f(AxorB)xor1)$ 來表示，其中，還必須特別避免

$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 提供)

分析

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