Bonjour tout ce que je me demandais s'il existe un moyen de mettre en œuvre cette méthode sans couler à un type de données plus large (long, double, double, etc.)? Par exemple, nous pourrions mettre en œuvre un pour la méthode canadand code> (sans moulage) comme tel: p> public static boolean CanTimes(int a, int b) {
if (a == 0 || b == 0) {
return true;
}
if (a > 0) {
if (b > 0) {
return a <= Integer.MAX_VALUE / b;
} else {
return a <= Integer.MIN_VALUE / b;
}
} else {
if (b > 0) {
return b <= Integer.MIN_VALUE / a;
} else {
return a <= -Integer.MAX_VALUE / b;
}
}
}
4 Réponses :
Vous pouvez faire la multiplication, puis vérifier si la division par un facteur donne toujours l'autre.
Ce qui précède ne fonctionne pas tout le temps, car Dietrich Epp le souligne; Il échoue pour -1 et integer.min_value. Je ne sais pas s'il y a d'autres cas de bord. Sinon, il serait facile de vérifier ce cas.
Intéressant. Est-ce que cela fonctionne de manière fiable? Ou y a-t-il des cas de bord qui entraînent des faux positifs?
L'algorithme échouera pour a = -1 , b = -0x80000000 . a * b = -0x8000000000 (débordement), mais (a * b) / a == b car le débordement arrive également pendant le chèque.
@Thilo - Je pensais que c'était fiable, mais un petit exemple (si je le faisais bien) me fait penser que ce n'est pas le cas. En 2 bits, le complément de 2 bits arithmétique, 11 * 10 (c'est-à-dire -1 * -2) donne 10 (ce qui est faux). Mais 10/11 donne 10, donc cela passerait le test. Un meilleur test serait de diviser le plus grand nombre (magnitude) autorisé par un facteur et testez que le résultat est moins (en magnitude) que l'autre facteur. Des tests distincts sont nécessaires pour chaque combinaison de signe, je pense.
Selon mon commentaire, voici la version adaptée, avec quelques tests de l'unité:
public static int mulAndCheck( int a, int b )
{
int ret;
String msg = "overflow: multiply";
if ( a > b )
{
// use symmetry to reduce boundry cases
ret = mulAndCheck( b, a );
}
else
{
if ( a < 0 )
{
if ( b < 0 )
{
// check for positive overflow with negative a, negative b
if ( a >= Integer.MAX_VALUE / b )
{
ret = a * b;
}
else
{
throw new ArithmeticException( msg );
}
}
else if ( b > 0 )
{
// check for negative overflow with negative a, positive b
if ( Integer.MIN_VALUE / b <= a )
{
ret = a * b;
}
else
{
throw new ArithmeticException( msg );
}
}
else
{
// assert b == 0
ret = 0;
}
}
else if ( a > 0 )
{
// assert a > 0
// assert b > 0
// check for positive overflow with positive a, positive b
if ( a <= Integer.MAX_VALUE / b )
{
ret = a * b;
}
else
{
throw new ArithmeticException( msg );
}
}
else
{
// assert a == 0
ret = 0;
}
}
return ret;
}
@Test( expected = ArithmeticException.class )
public void testOverflow()
{
mulAndCheck( Integer.MAX_VALUE, Integer.MAX_VALUE );
}
@Test( expected = ArithmeticException.class )
public void testOverflow1()
{
mulAndCheck( Integer.MIN_VALUE, Integer.MAX_VALUE );
}
@Test
public void testTimesMinus1()
{
Assert.assertEquals( Integer.MIN_VALUE + 1, mulAndCheck( Integer.MAX_VALUE, -1 ) );
Assert.assertEquals( Integer.MAX_VALUE, mulAndCheck( Integer.MIN_VALUE + 1, -1 ) );
}
Ceci est blatif Plagiarisme de Cet article !
@Bohemian je suis à peu près sûr que j'ai posté où cela est adapté de dans mon commentaire à l'OP: "Une petite quantité de googling a eu lieu ceci: java2s.com/tatudial/java/0040__Data-type/... qui est pour Longs, mais évidemment, il est à seulement des secondes d'être adaptés à l'INT. " De toute façon, vous n'ajoutez rien de précieux à la discussion ici.
mathématiquement, la somme du log-base-2 doit être inférieure à 2 32 . Malheureusement, les maths ne nous donnent pas la base de journal 2, mais cela reste assez simple: S'il y a un débordement, la division par le numéro d'origine ne nous ramènera pas au numéro de départ.
Il est important de noter que cela fonctionnera pour longs , qui ne peut pas être jeté.
Cela ne fonctionne pas tout le temps. Si le produit (mathématique) est négatif, la limite à vérifier est -Integer.min_value .
@TedhoppP Oui - Il y a un cas d'avance du produit étant exactement INTEGER.MIN_VALUE non couvert, mais Journal n'est pas si précis. Si vous pouvez vivre avec ce boîtier de bord, cette solution serait acceptable. (L'utilisation de math.abs () rend les résultats négatifs toujours correctement vérifiés)
Je ne pense pas " journal n'est pas si précis" est une grande partie d'une défense de integer.min_value non couvert. Vous dites simplement "Oui, d'accord, il y a une entrée que cela ne va pas, mais il y a d'autres intrants qu'il a mal ce qui est de toute façon". Et si le questionneur veut que la solution soit correcte?
BTW est-il garanti que s'il y a un débordement, la division par le numéro d'origine ne nous ramènerait pas au numéro de départ quelles que soient les intrants?
@Pacerier - Il n'est pas garanti. Essayez -1 et intger.min_value pour A et b .
@Tedhopp en fait, c'est est garanti. Vous peut multiplier -1 et intger.min_value . Le fait que le résultat soit integer.min_value (une bizarrerie de la mise en œuvre de 2's-compliment de Java) est hors de propos. Vous pouvez toujours le faire et techniquement ce n'est pas un débordement. Bravo de penser à cette particularité Tho!
@Bohemian Pourquoi n'est-ce pas un débordement? Multiplier deux nombres négatifs ne doivent pas produire un nombre négatif à moins de débordement. Il essaie de représenter 2 ^ 31 et il est trop grand pour s'intégrer à un int .
@Tedhopp Pourquoi n'est-ce pas un débordement? Heureux que vous ayez posé ... parce que math.abs (intger.min_value) retour intger.min_value ! Comme je l'ai dit, c'est une bizarrerie. D'une certaine manière, je ne suis pas en désaccord avec vous, mais ce n'est que la façon dont Java travaille ... c'est techniquement pas un trop-plein, car il n'y a pas d'égal positif correspondant pour INTEGER.MIN_VALUE . Il y a 2 ^ 32 valeurs pour INTS, mais une valeur est utilisée pour zéro, de sorte que cela laisse un nombre impair à partager entre des nombres positifs et négatifs. L'utilisation du compliment de 2 signifie que le choix logique est qu'il y a un nombre plus négatif que des nombres positifs.
puisque la multiplication de (j'ai renommé votre A * B code> est identique à celle de A + A + A + ... code> répété B code> fois (et Versa), vous pouvez faire quelque chose comme ceci: CANMultiple () code> fonction à isintmultiplication () code>, puisque je pense que c'est plus clair) p > // returns true, Integer.MAX_VALUE * 1 is still an int
isIntMultiplication(Integer.MAX_VALUE, 1);
// returns false, Integer.MAX_VALUE * 2 is a long
isIntMultiplication(Integer.MAX_VALUE, 2);
// returns true, Integer.MAX_VALUE/2 * 2 is still an int
isIntMultiplication(Integer.MAX_VALUE/2, 2);
// returns false, Integer.MAX_VALUE * Integer.MAX_VALUE is a long
isIntMultiplication(Integer.MAX_VALUE, Integer.MAX_VALUE);
Les signes sont importants car -integer.min_value> Integer.max_Value (mathématiquement).
HMM, l'approche fonctionne (bien que le signe ait besoin de tri), mais je pense que 64k ajouts dans le pire des cas peuvent probablement être battus pour la performance ...
J'aime l'idée d'échanger la gauche et à droite en choisissant le plus petit pour boucler, bien que ce soit encore assez lent.
@Pacerier: Peut être pire, la vérification de l'ajout de débordement pourrait être implémentée comme un total répété ++ total , avec un chèque que total! = INTEGER.MAX_VALUE ;-)
Pourquoi? Pourquoi la restriction artificielle?
Peut-être que vous pouvez faire quelque chose avec
integer.numberfleadingzeros . Si la somme des deux zéros de premier plan est supérieure à 31, ce sera toujours un Int, ou quelque chose comme ça.@EJP Ce n'est pas une restriction artificielle, je me demande s'il y a un moyen de le faire sans avoir à se lancer dans un type de données plus large. Par exemple, Headgeek a une demi-solution ici Stackoverflow.com/a/199455/632951 . Son est une estimation si j'étais intéressé par la manière dont nous pourrions l'améliorer de telle sorte qu'il fonctionne réellement.
Une petite quantité de googling a tourné ceci: Java2s.com/Tutorial/java / 0040__Data Type / ... qui est pour Longs, mais évidemment, il est à seulement des secondes d'être adaptés à l'INTS.
@Strelok Wow bon truc! Parfois, les choses simples sont les difficiles à penser.
@Pacerier OK - J'ai posté une solution simple, une ligne et précise pour vous - voir ma réponse