如何在不使用运算符的情况下编写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;