如何在不使用运算符的情况下编写 LessThan 方法

Question

您将如何在不使用“<”运算符的情况下递归地编写一个方法来检查一个数字是否小于另一个数字？

您只能使用加号、减号、乘号和等于运算符。
必须是递归的
x 和 y 将始终为 0 或更大
应该returnboolean
如果需要，您可以制作其他方法，但必须遵守上述规则。

Cove 我到目前为止：

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 整数是 32 位，所以上限是 O(32)与 O(1).

相同

Answer 2

你可以像这个问题的答案那样做：
Bitwise operations equivalent of greater than operator

但是这不符合规则 2：它必须是递归的。

根据comment，规则 1 应该是：

您只能使用 plus、minus、multiply、等于和按位运算符。

使用右移运算符，我们可以在O(log n)时间内得到一个解，不像，也就是O(n)的时间，很可能造成WhosebugError.

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;

如何在不使用运算符的情况下编写 LessThan 方法

How to write a LessThan method without using the operator

java

math

recursion

integer

integer-arithmetic