Как написать метод LessThan без использования оператора

Поскольку вы сделали добросовестную попытку, написав свой собственный код, и поскольку я вижу, что это своего рода головоломка, я предлагаю вам ниже код, который имеет только один рекурсивный вызов, а не два рекурсивных вызова, как в вашем коде. .

Я думаю, что это так же просто, как и при соблюдении ограничений.

Что он делает: он считает оба числа до нуля и проверяет, какое из них достигнет нуля первым. Если оба достигают нуля одновременно, результат должен быть ложным, но простая проверка того, равен ли 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).

Вы можете сделать это как ответ на этот вопрос:
Побитовые операции, эквивалентные больше, чем оператор

Однако это не соответствует правилу 2: это должно быть рекурсивным.

Согласно комментарий, правило 1 должно быть таким:

1. Вы можете использовать только операторы плюс, минус, умножить, равно и побитовый. .

С помощью оператора сдвиг вправо мы можем получить решение за время O(log n), в отличие от ответ Эрвина Болвидта, что занимает 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;