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

Question

如果不使用'<'运算符,你将如何递归地编写一个检查数字是否小于另一个的方法？

1. 您只能使用加号,减号,次数和等于运算符.
2. 它必须是递归的
3. x并且y将始终为0或更大
4. 应该回来 boolean
5. 如果需要,您可以制定其他方法,但必须遵守上述规则.

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的回答比上述更有效.我的目标最初是为了一个简短,干净的答案.我试图创建一个更短的bitshift方法.虽然比计数示例更难掌握,但它具有更好的复杂性,并且它具有与上述代码相同的行数(我不计算那个常数,因为我可以在代码中包含它而牺牲可读性).

请注意,此代码向左移动而不是向右移动 - 它首先检查最高有效位.

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).