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
