如何在不使用運算符的情況下編寫LessThan方法

Question

如何遞歸編寫一種方法來檢查數字是否小於另一個，而不使用'<'運算符？

1. 您只能使用加號，減號，倍數和等號運算符。
2. 它必須是遞歸
3. x和y將始終爲0或更高
4. 應該返回boolean
5. 如果需要的話，你可以讓其他的方法，但他們必須遵守上述規則。

灣我已經走到這一步：

public static boolean isLessThan(int x, int y) { 
    if(x == y - 1) return true; 
    if(x == y + 1) return false; 
    if(x == y) return false; 

    return isLessThan((x), (y-1)) || isLessThan((x-1), y); 
} 

Answer 1

因爲你已經通過編寫自己的代碼善意的嘗試，因爲我看到這是一種困惑，我爲您提供下面只有一個遞歸調用的代碼，而不是像您的代碼中那樣進行兩次遞歸調用。

我認爲這是儘可能簡單，因爲它滿足約束。

它做什麼：它將兩個數字倒數爲零，並檢查哪一個先到達零。如果兩者同時達到零，則結果應該是錯誤的，但只需檢查y是否已包含該檢查。

public static boolean isLessThan(int x, int y) { 
    if (y == 0) { 
     return false; 
    } 
    if (x == 0) { 
     return true; 
    } 

    return isLessThan(x - 1, y - 1); 
} 

@Andreas的答案比上面更有效率。我的目標最初是爲了一個簡短而乾淨的答案。 我試圖創建一個較短的移位方法。 儘管比計數例子更難掌握，但它具有更好的複雜性，並且與上述代碼具有相同數量的行（我不計算該常量，因爲我可以將代碼包含在代碼中以犧牲可讀性爲代價）。

請注意，此代碼左移而非右移，並且它首先檢查最重要的位。

public static final int HIGH_BIT = 1 << 31; 

public static boolean isLessThan(int x, int y) { 
    if (x == y) { 
     return false; 
    } 
    if ((x & HIGH_BIT) != (y & HIGH_BIT)) { 
     return (y & HIGH_BIT) == HIGH_BIT; 
    } 
    return isLessThan(x << 1, y << 1); 
} 

注：如果!=是不允許的，你可以改變第二if聲明：

if (((x^y) & HIGH_BIT) == HIGH_BIT) 

還要注意的是，複雜性確實是O(1)因爲，雖然該算法是理論上O(log n)，Java的int爲32位，因此上限爲O(32)，與O(1)相同。

Answer 2

你可以不喜歡它的這個問題的答案：
Bitwise operations equivalent of greater than operator

但是不兌現規則2：必須遞歸。

據comment，規則1應該是：

1. 您只能使用加，減去，乘，等於和按位運營商。

通過使用該右移運營商，我們可以得到在Ø溶液（log n）的時間，不像answer by Erwin Bolwidt，這是O（n）的時間，而且容易造成StackOverflowError。

public static boolean isLessThan(int x, int y) { 
    return compare(x, y) == -1; 
} 

private static int compare(int x, int y) { 
    if (x == y) 
     return 0; // x == y 
    if (x == 0) 
     return -1; // x < y 
    if (y == 0) 
     return 1; // x > y 

    // Compare higher bits. If different, then that is result 
    int cmp = compare(x >> 1, y >> 1); 
    if (cmp != 0) 
     return cmp; 

    // Only bit 0 differs, so two choices: 
    // x0 == 1 && y0 == 0 -> return 1 
    // x0 == 0 && y0 == 1 -> return -1 
    return (x & 1) - (y & 1); 
} 

如果!=是不允許的，代碼可以改爲：

// same code up to and including recursive call 
if (cmp == 0) 
    return (x & 1) - (y & 1); 
return cmp;