Pourquoi i = i + i me donne-t-il 0?

96

J'ai un programme simple:

public class Mathz {
    static int i = 1;
    public static void main(String[] args) {    
        while (true){
            i = i + i;
            System.out.println(i);
        }
    }
}

Quand je lance ce programme, tout ce que je vois est 0pour ima sortie. Je me serais attendu à ce que la première fois, nous l'aurions i = 1 + 1, suivie de i = 2 + 2, suivie de i = 4 + 4etc.

Est-ce dû au fait que dès que nous essayons de re-déclarer isur le côté gauche, sa valeur est réinitialisée 0?

Si quelqu'un pouvait m'indiquer les détails les plus fins, ce serait formidable.

Changez le inten longet il semble imprimer les nombres comme prévu. Je suis surpris de la vitesse à laquelle il atteint la valeur maximale de 32 bits!

DeaIss
la source

Réponses:

168

Le problème est dû à un débordement d'entier.

En arithmétique 32 bits à complément double:

icommence en effet avec des valeurs de puissance de deux, mais les comportements de débordement commencent une fois que vous atteignez 2 30 :

2 30 + 2 30 = -2 31

-2 31 + -2 31 = 0

... en intarithmétique, puisqu'il s'agit essentiellement du mod arithmétique 2 ^ 32.

Louis Wasserman
la source
28
Pourriez-vous développer un peu votre réponse?
DeaIss le
17
@oOTesterOo Il commence à imprimer 2, 4 etc mais il atteint très rapidement la valeur maximale de l'entier et il "s'enroule" en nombres négatifs, une fois qu'il atteint zéro, il reste à zéro pour toujours
Richard Tingle
52
Cette réponse est même pas complète (il n'a même pas mentionné que la valeur ne sera 0sur les premières itérations, mais la vitesse de sortie est obscurcir ce fait de l'OP). Pourquoi est-ce accepté?
Courses de légèreté en orbite le
16
Vraisemblablement, il a été accepté car il a été jugé utile par le PO.
Joe
4
@LightnessRacesinOrbit Bien que cela n'aborde pas directement les problèmes posés par l'OP dans sa question, la réponse donne suffisamment d'informations pour qu'un programmeur décent puisse en déduire ce qui se passe.
Kevin
334

introduction

Le problème est un débordement d'entier. S'il déborde, il revient à la valeur minimale et continue à partir de là. S'il sous-déborde, il revient à la valeur maximale et continue à partir de là. L'image ci-dessous est celle d'un odomètre. J'utilise cela pour expliquer les débordements. C'est un débordement mécanique mais un bon exemple quand même.

Dans un odomètre, le max digit = 9, allant au-delà du maximum signifie 9 + 1, ce qui reporte et donne un 0; Cependant, il n'y a pas de chiffre supérieur à changer en a 1, donc le compteur se réinitialise à zero. Vous voyez l'idée - les "débordements d'entiers" viennent à l'esprit maintenant.

entrez la description de l'image ici entrez la description de l'image ici

Le plus grand littéral décimal de type int est 2147483647 (2 31 -1). Tous les littéraux décimaux de 0 à 2147483647 peuvent apparaître partout où un littéral int peut apparaître, mais le littéral 2147483648 peut apparaître uniquement comme l'opérande de l'opérateur de négation unaire -.

Si une addition entière déborde, alors le résultat est les bits de poids faible de la somme mathématique comme représenté dans un format de complément à deux suffisamment grand. En cas de dépassement de capacité, alors le signe du résultat n'est pas le même que le signe de la somme mathématique des deux valeurs d'opérande.

Ainsi, 2147483647 + 1déborde et s'enroule autour de -2147483648. Par conséquent int i=2147483647 + 1serait débordé, ce qui n'est pas égal à 2147483648. De plus, vous dites "il imprime toujours 0". Ce n'est pas le cas, car http://ideone.com/WHrQIW . Ci-dessous, ces 8 chiffres montrent le point auquel il pivote et déborde. Il commence alors à imprimer des 0. Aussi, ne soyez pas surpris de la vitesse de calcul, les machines d'aujourd'hui sont rapides.

268435456
536870912
1073741824
-2147483648
0
0
0
0

Pourquoi le débordement d'entier "s'enroule"

PDF original

Ali Gajani
la source
17
J'ai ajouté l'animation pour "Pacman" à des fins symboliques, mais elle sert également d'un excellent visuel de la façon dont on verrait des "débordements d'entiers".
Ali Gajani
9
C'est ma réponse préférée sur ce site de tous les temps.
Lee White
2
Vous semblez avoir manqué qu'il s'agissait d'une séquence de doublement, sans en ajouter une.
Paŭlo Ebermann
2
Je pense que l'animation de pacman a obtenu cette réponse plus de votes positifs que la réponse acceptée. Ayez un autre vote positif sur moi - c'est l'un de mes jeux préférés!
Husman
3
Pour tous ceux qui n'ont pas compris le symbolisme: en.wikipedia.org/wiki/Kill_screen#Pac-Man
wei2912
46

Non, il n'imprime pas que des zéros.

Changez-le en ceci et vous verrez ce qui se passe.

    int k = 50;
    while (true){
        i = i + i;
        System.out.println(i);
        k--;
        if (k<0) break;
    }

Ce qui se passe est appelé débordement.

peter.petrov
la source
61
Manière intéressante d'écrire une boucle for :)
Bernhard
17
@Bernhard C'est probablement pour garder la structure du programme d'OP.
Taemyr
4
@Taemyr Probablement, mais il aurait pu le remplacer truepar i<10000:)
Bernhard
7
Je voulais juste ajouter quelques déclarations; sans supprimer / modifier aucune déclaration. Je suis surpris qu'il ait attiré une telle attention.
peter.petrov
18
Vous auriez pu utiliser l'opérateur caché while(k --> 0)familièrement nommé "while kva à 0";)
Laurent LA RIZZA
15
static int i = 1;
    public static void main(String[] args) throws InterruptedException {
        while (true){
            i = i + i;
            System.out.println(i);
            Thread.sleep(100);
        }
    }

production:

2
4
8
16
32
64
...
1073741824
-2147483648
0
0

when sum > Integer.MAX_INT then assign i = 0;
TrungTran05T3
la source
4
Euh, non, cela fonctionne juste pour que cette séquence particulière arrive à zéro. Essayez de commencer par 3.
Paŭlo Ebermann
4

Comme je n'ai pas assez de réputation, je ne peux pas publier l'image de la sortie pour le même programme en C avec une sortie contrôlée, vous pouvez essayer vous-même et voir qu'il imprime réellement 32 fois, puis comme expliqué en raison d'un débordement i = 1073741824 + 1073741824 changements à -2147483648 et un autre ajout supplémentaire est hors de portée de int et devient Zero.

#include<stdio.h>
#include<conio.h>

int main()
{
static int i = 1;

    while (true){
        i = i + i;
      printf("\n%d",i);
      _getch();
    }
      return 0;
}
Kaify
la source
3
Ce programme, en C, déclenche en fait un comportement indéfini à chaque exécution, ce qui permet au compilateur de remplacer tout le programme par n'importe quoi (même system("deltree C:"), puisque vous êtes sous DOS / Windows). Le débordement d'entier signé est un comportement non défini en C / C ++, contrairement à Java. Soyez très prudent lorsque vous utilisez ce type de construction.
filcab
@filcab: "remplacer tout le programme par n'importe quoi" de quoi tu parles. J'ai exécuté ce programme sur Visual studio 2012 et il fonctionne parfaitement pour les deux signed and unsignedentiers sans aucun comportement indéfini
Kaify
3
@Kaify: Travailler correctement est un comportement indéfini parfaitement valide. Imaginez cependant que le code ait fait plus i += ide 32 itérations, puis l'a fait if (i > 0). Le compilateur pourrait optimiser cela if(true)car si nous ajoutons toujours des nombres positifs, ils iseront toujours supérieurs à 0. Il pourrait également laisser la condition dans, où elle ne sera pas exécutée, à cause du débordement représenté ici. Étant donné que le compilateur peut produire deux programmes également valides à partir de ce code, son comportement n'est pas défini.
3Doubloons
1
@Kaify: ce n'est pas une analyse lexicale, c'est le compilateur qui compile votre code et, suivant le standard, peut faire des optimisations «bizarres». Comme la boucle dont parlait 3Doubloons. Tout simplement parce que les compilateurs que vous essayez semblent toujours faire quelque chose, cela ne signifie pas que le standard garantit que votre programme fonctionnera toujours de la même manière. Vous aviez un comportement indéfini, du code aurait pu être éliminé car il n'y a aucun moyen d'y arriver (UB le garantit). Ces articles du blog llvm (et les liens qu'il contient
filcab
2
@Kaify: Désolé de ne pas l'avoir dit, mais il est complètement faux de dire "gardé le secret", surtout quand c'est le deuxième résultat, sur Google, pour "comportement indéfini", qui était le terme spécifique que j'ai utilisé pour ce qui était déclenché .
filcab
4

La valeur de iest stockée en mémoire à l'aide d'une quantité fixe de chiffres binaires. Lorsqu'un numéro nécessite plus de chiffres que ce qui est disponible, seuls les chiffres les plus bas sont stockés (les chiffres les plus élevés sont perdus).

S'ajouter ià lui-même équivaut à multiplier ipar deux. Tout comme la multiplication d'un nombre par dix en notation décimale peut être effectuée en faisant glisser chaque chiffre vers la gauche et en mettant un zéro à droite, la multiplication d'un nombre par deux en notation binaire peut être effectuée de la même manière. Cela ajoute un chiffre à droite, donc un chiffre se perd à gauche.

Ici, la valeur de départ est 1, donc si nous utilisons 8 chiffres pour stocker i(par exemple),

  • après 0 itération, la valeur est 00000001
  • après 1 itération, la valeur est 00000010
  • après 2 itérations, la valeur est 00000100

et ainsi de suite, jusqu'à l'étape finale non nulle

  • après 7 itérations, la valeur est 10000000
  • après 8 itérations, la valeur est 00000000

Peu importe le nombre de chiffres binaires alloués pour stocker le numéro, et quelle que soit la valeur de départ, tous les chiffres seront finalement perdus lorsqu'ils seront poussés vers la gauche. Après ce point, continuer à doubler le nombre ne changera pas le nombre - il sera toujours représenté par tous les zéros.

enfant star
la source
3

C'est correct, mais après 31 itérations, 1073741824 + 1073741824 ne calcule pas correctement et après cela n'imprime que 0.

Vous pouvez refactoriser pour utiliser BigInteger, ainsi votre boucle infinie fonctionnera correctement.

public class Mathz {
    static BigInteger i = new BigInteger("1");

    public static void main(String[] args) {    

        while (true){
            i = i.add(i);
            System.out.println(i);
        }
    }
}
Bruno Volpato
la source
Si j'utilise long au lieu de int, il semble que les nombres> 0 soient imprimés pendant longtemps. Pourquoi ne rencontre-t-il pas ce problème après 63 itérations?
DeaIss le
1
«Ne calcule pas correctement» est une caractérisation incorrecte. Le calcul est correct selon ce que la spécification Java dit devrait se produire. Le vrai problème est que le résultat du calcul (idéal) ne peut pas être représenté comme un int.
Stephen C
@oOTesterOo - parce que longpeut représenter des nombres plus grands que intpossible.
Stephen C
Long a une plus grande portée. Le type BigInteger accepte toute valeur / longueur que votre JVM peut allouer.
Bruno Volpato
J'ai supposé que int débordait après 31 itérations parce que c'est un nombre de taille maximale de 32 bits, et si longtemps, un 64 bits atteindrait son maximum après 63? Pourquoi n'est-ce pas le cas?
DeaIss le
2

Pour déboguer de tels cas, il est bon de réduire le nombre d'itérations dans la boucle. Utilisez ceci au lieu de votre while(true):

for(int r = 0; r<100; r++)

Vous pouvez alors voir qu'il commence par 2 et double la valeur jusqu'à ce qu'il provoque un débordement.

utilisateur3732069
la source
2

J'utiliserai un nombre de 8 bits pour l'illustration car il peut être complètement détaillé dans un court espace. Les nombres hexadécimaux commencent par 0x, tandis que les nombres binaires commencent par 0b.

La valeur maximale pour un entier non signé de 8 bits est 255 (0xFF ou 0b11111111). Si vous ajoutez 1, vous vous attendez généralement à obtenir: 256 (0x100 ou 0b100000000). Mais comme c'est trop de bits (9), c'est au-dessus du maximum, donc la première partie est simplement supprimée, vous laissant effectivement 0 (0x (1) 00 ou 0b (1) 00000000, mais avec le 1 supprimé).

Ainsi, lorsque votre programme s'exécute, vous obtenez:

1 = 0x01 = 0b1
2 = 0x02 = 0b10
4 = 0x04 = 0b100
8 = 0x08 = 0b1000
16 = 0x10 = 0b10000
32 = 0x20 = 0b100000
64 = 0x40 = 0b1000000
128 = 0x80 = 0b10000000
256 = 0x00 = 0b00000000 (wraps to 0)
0 + 0 = 0 = 0x00 = 0b00000000
0 + 0 = 0 = 0x00 = 0b00000000
0 + 0 = 0 = 0x00 = 0b00000000
...
riche souvenir
la source
1

Le plus grand littéral décimal de type intest 2147483648 (= 2 31 ). Tous les littéraux décimaux de 0 à 2147483647 peuvent apparaître partout où un littéral int peut apparaître, mais le littéral 2147483648 peut apparaître uniquement comme l'opérande de l'opérateur de négation unaire -.

Si une addition entière déborde, alors le résultat est les bits de poids faible de la somme mathématique comme représenté dans un format de complément à deux suffisamment grand. En cas de dépassement de capacité, alors le signe du résultat n'est pas le même que le signe de la somme mathématique des deux valeurs d'opérande.

Scooba doo
la source