Trouvez le nombre max ? c'est basique !

Cette semaine, c'est Mouaad qui vous propose un #KataOfTheWeek : Nombre max ? c'est facile..!

Briefing du Kata : Trouver le nombre max c'est basique, élémentaire ! mais si nous faisions ça différemment ? Votre mission, si vous l'acceptez : écrire une méthode qui trouve le maximum de deux nombres, mais avec un petit bonus : sans utiliser aucun opérateur de comparaison !

Astuce : Quand a > b, alors a - b > 0. Pouvez-vous obtenir le signe de a - b?

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur :

L'approche intuitive pour résoudre ce problème c'est d'implémenter une fonction max est de regarder le signe de a - b. Mais dans notre cas nous ne pouvons pas utiliser un opérateur de comparaison sur ce signe, mais nous pouvons utiliser la multiplication.

Soit k le signe de a - b tel que si a - b > = 0 , k vaut 1 , sinon 0. Soit q l’inverse de k.

Une première solution est présentée dans la classe Solution1. Ce code  fait l'affaire… enfin presque ! Cela échoue, malheureusement, quant a - b cause un overflow ! ceci arrive spécialement dans le cas ou a est un nombre positif et b est un nombre négatif (ou vise versa) !

La solution complète sera d'utiliser la logique précédente si les deux nombres ont le même signe, sinon c'est le nombre positif qui est toujours plus grand (classe Solution2).

public class Solution1 {

    public static void main(String[] args) {
        int a = -10;
        int b = 35;
        int max = max(a, b);
        System.out.println(max);
    }

    /**
     * Get the max between to numbers.
     *
     * @param a first number
     * @param b second number
     * @return max number
     */
    static int max(int a, int b) {
        int k = sign(a - b);
        int q = flip(k);
        return a * k + b * q;
    }

    /**
     * Get the number sign.
     *
     * @param a the number to get its sign.
     * @return 1 if a is positive, and 0 if a is negative
     */
    static int sign(int a) {
        int bit = (a >> 31) & 0x1;
        return flip(bit);
    }

    /**
     * Flips a 1 to a 0 and a 0 to a 1.
     *
     * @param bit the bit to flip.
     * @return flipped bit.
     */
    static int flip(int bit) {
        return 1 ^ bit;
    }
}

public class Solution2 {

    public static void main(String[] args) {
        int a = Integer.MAX_VALUE - 1;
        int b = -20;
        int max = max(a, b);
        System.out.println(max);
    }

    /**
     * Get the max between to numbers.
     *
     * @param a first number
     * @param b second number
     * @return max number
     */
    static int max(int a, int b) {
        int c = a - b;

        int signA = sign(a);
        int signB = sign(b);
        int signC = sign(c);

        int useSignOfA = signA ^ signB; // if `a` and `b` signs are different then 1, otherwise 0
        int useSignOfC = flip(useSignOfA);

        int k = useSignOfA * signA + useSignOfC * signC; // use sign of `a` if different, otherwise `c` sign
        int q =  flip(k);

        return a * k + b * q;
    }

    /**
     * Get the number sign.
     *
     * @param a the number to get its sign.
     * @return 1 if a is positive, and 0 if a is negative
     */
    static int sign(int a) {
        int bit = (a >> 31) & 0x1;
        return flip(bit);
    }

    /**
     * Flips a 1 to a 0 and a 0 to a 1.
     *
     * @param bit the bit to flip.
     * @return flipped bit.
     */
    static int flip(int bit) {
        return 1 ^ bit;
    }
}

Votre équipe TakiVeille