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

因为您通过编写自己的代码进行了真诚的尝试，并且因为我认为这是一种难题，所以我向您提供下面的代码，该代码只有一个递归调用，而不是有两个递归调用，例如在您的代码中。

我认为这在满足约束的情况下是最简单的。

它的作用:它将两个数字倒数到零，并检查哪个数字首先达到零。如果两者同时达到零，则结果应该为 false，但简单地检查 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 整数是 32 位，因此上限是O(32)，与O(1)相同。