Domanda Risolto Cosa chiede la traccia?

[nostyn]

Tratto da "Il linguaggio C" di Brian W.Kernighan e Dennis M.Ritchie. Capitolo 3, paragrafo 6, esercizio 3.4.

Questo e' il codice a cui e' riferito:

void itoa(int n, char s[])
{
    int i, sign;
 
    if((sign = n) < 0)
        n = -n;
    i = 0;
    do
    {
        s[i++] = n % 10 + '0';
    } while ((n /= 10) > 0);
    if(sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

La funzione in questione prende un numero n e lo trasforma in caratteri all'interno della stringa s . reverse() rovescia la la stringa che riceve in input .

Traccia:
In un sistema con complemento a due, la nostra versione di itoa non gestisce correttamente il massimo numero negativo ammesso in ingresso, cioe' il valore di n pari a - ( 2 ^ (dimensioneparola - 1)). Si spieghi il perche', e si apportino le modifiche necessarie per visualizzare tale valore correttamente, indipendentemente dal tipo di macchina.

Quesito ed osservazioni:
Credo di non aver capito appieno la traccia: prima di tutto non capisco se per complemento a due intende ricevere in ingresso un numero binario o dare in output un numero binario. Io l'ho interpretato come ricevere in input un numero in base decimale per poi darlo in output in forma binaria all'interno della stringa.
L'unico dettaglio che credo non permetta di gestire correttamente il valore e' che in binario non essendo rappresentabile '- 0', -00000000 stia a simboleggiare -1, dunque per tale ragione dovrebbe essere sufficiente apportare questa modifica:

if((sign = n) < 0)
    if(++n != 0)
        n = -n;

E sostituire i due 10 con 2, chiaramente. Cosa ne pensate? Credete sia questa una possibile interpretazione e risoluzione?

Grazie in anticipo per le risposte.

 

[St3ve]

Un numero di k bit, in complemento a due, può rappresentare i numeri interi da -2^(k-1) fino a 2^(k-1) - 1.
Il codice di itoa a un certo punto fa n = -n. Supponendo che il suo input sia proprio -2^(k-1), quell'istruzione causa un integer overlow perché +2^(k-1) non è rappresentabile (è troppo grande).

Questo risponde a "si spieghi il perché". Ora, ammesso che tu abbia capito bene il problema, prova a vedere se riesci a risolverlo.

 

[nostyn]

Un numero di k bit, in complemento a due, può rappresentare i numeri interi da -2^(k-1) fino a 2^(k-1) - 1.
Il codice di itoa a un certo punto fa n = -n. Supponendo che il suo input sia proprio -2^(k-1), quell'istruzione causa un integer overlow perché +2^(k-1) non è rappresentabile (è troppo grande).

Questo risponde a "si spieghi il perché". Ora, ammesso che tu abbia capito bene il problema, prova a vedere se riesci a risolverlo.

E' esattamente quello a cui mi riferivo! Chiaramente l'ho scritto in modo molto piu' rozzo ahahah E per '-' intendevo rappresentare il bit meno significativo che fungeva da segno. Comunque la modifica che ho inserito nel secondo blocco di codice dovrebbe risolvere il problema, tu lo avresti scritto in un altro modo? ^^ Senza alterare tutto il resto intendo. E grazie della risposta dettagliata!

Messaggio unito automaticamente: 17 Aprile 2019

Ora, ammesso che tu abbia capito bene il problema, prova a vedere se riesci a risolverlo.

Spoiler

#include <stdio.h>
#include <string.h>

void reverse(char s[])
{
    int c, i, j;
    for(i = 0, j = strlen(s) - 1; i < j; i++, j--)
    {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

void itoa(int n, char s[])
{
    int i, sign;
   
    if((sign = n) < 0)
        if(++n != 0)
            n = -n;
    i = 0;
    do
    {
        s[i++] = n % 2 + '0';
    } while ((n /= 2) > 0);
    if(sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

int main()
{
    int n = -1;
    char s[] = "........";
   
    printf("%d\n",n);
    itoa(n,s);
    printf("%s\n",s);
    return 0;
}

Dunque in questo modo

 

[St3ve]

Comunque la modifica che ho inserito nel secondo blocco di codice dovrebbe risolvere il problema

Proprio no.

#include <limits.h>
#include <stdio.h>

void test(int n) {
  char s[32] = {0};
  itoa(n, s);
  printf("%d => %s\n", n, s);
}

int main() {
  test(0);
  test(1);
  test(-1);
  test(INT_MAX);
  test(INT_MIN);
  return 0;
}

Guarda cosa fa itoa prima e dopo la tua modifica. L'unica cosa che vuoi sistemare, è il problema (un undefined behavior) che c'è su INT_MIN.

 

[nostyn]

Proprio no.

#include <limits.h>
#include <stdio.h>

void test(int n) {
  char s[32] = {0};
  itoa(n, s);
  printf("%d => %s\n", n, s);
}

int main() {
  test(0);
  test(1);
  test(-1);
  test(INT_MAX);
  test(INT_MIN);
  return 0;
}

Guarda cosa fa itoa prima e dopo la tua modifica. L'unica cosa che vuoi sistemare, è il problema (un undefined behavior) che c'è su INT_MIN.

Non mi da alcun errore : / Su quale macchina lo hai provato?*

 

[St3ve]

Probabilmente non hai ancora ben capito il problema. Ripeto, guarda cosa fa itoa prima e dopo la tua modifica.

Prima:

0 => 0
1 => 1
-1 => -1
2147483647 => 2147483647
-2147483648 => -(

Dopo:

0 => 0
1 => 1
-1 => -0
2147483647 => 1111111111111111111111111111111
-2147483648 => -1111111111111111111111111111111

La funzione itoa serve per passare da un int ad una stringa ascii, ma l'implementazione del libro ha un integer overflow. Devi semplicemente risolvere il bug. L'output vorresti vedere è:

0 => 0
1 => 1
-1 => -1
2147483647 => 2147483647
-2147483648 => -2147483648

 

[nostyn]

Probabilmente non hai ancora ben capito il problema. Ripeto, guarda cosa fa itoa prima e dopo la tua modifica.

Prima:

0 => 0
1 => 1
-1 => -1
2147483647 => 2147483647
-2147483648 => -(

Dopo:

0 => 0
1 => 1
-1 => -0
2147483647 => 1111111111111111111111111111111
-2147483648 => -1111111111111111111111111111111

La funzione itoa serve per passare da un int ad una stringa ascii, ma l'implementazione del libro ha un integer overflow. Devi semplicemente risolvere il bug. L'output vorresti vedere è:

0 => 0
1 => 1
-1 => -1
2147483647 => 2147483647
-2147483648 => -2147483648

Ahh, scusa, hai perfettamente ragione. In effetti come ho scritto nel thread e' proprio questo il dubbio che mi assaliva, ovvero se in effetti l'output dovesse essere in binario ^^ Penso a una soluzione

 

[nostyn]

@St3ve dunque ho apportato un paio di modifiche alla prima parte della funzione ed ora dovrebbe adattarsi a qualsiasi macchina, fammi sapere se ritieni abbastanza elegante questa soluzione

Spoiler: Sorgente completo

#include <stdio.h>
#include <string.h>
#include <limits.h>

void reverse(char s[])
{
    int c, i, j;
    for(i = 0, j = strlen(s) - 1; i < j; i++, j--)
    {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

void itoa(int n, char s[])
{
    int i = 0, sign, skip = 0;
    
    if((sign = n) < 0)
    {
        n = -n - 1;
        if((n % 10) == 9)
        {
            s[i++] = '0';
            n = (n / 10) + 1;
        }
        else
        {
            s[i++] = n % 10 + 1 + '0';
            if((n /= 10) == 0)
                skip = 1;
        }
    }
    
    if(skip == 0)
    {
        do
        {
            s[i++] = n % 10 + '0';
        } while ((n /= 10) > 0);
    }
    
    if(sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

void test(int n)
{
    char s[32] = {0};
    itoa(n, s);
    printf("%d => %s\n", n, s);
}

int main()
{
    test(0);
    test(1);
    test(-1);
    test(INT_MAX);
    test(INT_MIN);
    return 0;
}

Spoiler: solo Funzione itoa

void itoa(int n, char s[])
{
    int i = 0, sign, skip = 0;
    
    if((sign = n) < 0)
    {
        n = -n - 1;
        if((n % 10) == 9)
        {
            s[i++] = '0';
            n = (n / 10) + 1;
        }
        else
        {
            s[i++] = n % 10 + 1 + '0';
            if((n /= 10) == 0)
                skip = 1;
        }
    }
    
    if(skip == 0)
    {
        do
        {
            s[i++] = n % 10 + '0';
        } while ((n /= 10) > 0);
    }
    
    if(sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

Spoiler: solo Modifiche apportate

int i = 0, sign, skip = 0;

if((sign = n) < 0)
{
....n = -n - 1;
....if((n % 10) == 9)
....{
........s[i++] = '0';
........n = (n / 10) + 1;
....}
....else
....{
........s[i++] = n % 10 + 1 + '0';
........if((n /= 10) == 0)
............skip = 1;
....}
}

if(skip == 0)
{
....do
....{
........s[i++] = n % 10 + '0';
....} while ((n /= 10) > 0);
}

 

[St3ve]

Okay, ma stai comunque causando un integer overflow: con n = -n - 1 stai in realtà facendo n = (-n) - 1 e visto che una delle operazioni intermedie calcola -n hai un undefined behavior su INT_MIN. Visto che è un problema marginale e mi risponderesti subito, ti precedo dicendo che per sistemare la tua soluzione basta fare n = -(n + 1).

Una soluzione un po' più elegante secondo me potrebbe essere questa

void itoa(int n, char s[]) {
  int sign = n > 0 ? 1 : -1;
  int i = 0;

  do {
    s[i++] = sign * (n % 10) + '0';
  } while ((n /= 10) != 0);

  if (sign < 0)
    s[i++] = '-';

  s[i] = '\0';
  reverse(s);
}

 

[nostyn]

Okay, ma stai comunque causando un integer overflow.. ..basta fare n = -(n + 1).

Lo avevo pensato anche io, infatti in una prima versione avevo scritto n = -(n + 1), ma poi compilando ho notato che fungeva lo stesso e quindi ho pensato che il processore non avesse problemi a svolgere questo tipo di calcoli e che il problema si presentasse solo quando si trattava di inserire il valore all'interno di una variabile. Infatti prima dopo essere stato svolto il calcolo dall'ALU il valore viene salvato nell'accumulatore. Suppongo dunque che quest'ultimo sia capace di contenere valori molto piu' grandi. Queste sono osservazioni, probabilmente errate, che ho basato sulla mia flebile conoscenza della struttura di una CPU, dunque correggimi se non e' cosi' per favore : /

Una soluzione un po' più elegante secondo me potrebbe essere questa..

Decisamente piu' elegante, altroche'. In effetti mi sono fatto molti giri mentali quando la soluzione era molto semplice ^^ Grazie della dritta.

La funzione itoa serve per passare da un int ad una stringa ascii, ma l'implementazione del libro ha un integer overflow..

Ho creduto che l'esercizio chiedesse la conversione in binario a causa di dimensioneparola in - ( 2 ^ (dimensioneparola - 1)) . Che poi alla fine sarebbe la k a cui facevi riferimento tu. Il punto e' che non c'e' relazione tra il numero minimo rappresentabile e la dimensione della parola se non con la rappresentazione in binario. Cioe', se la parola e' composta da x caratteri, allora un carattere occupa lo spazio per il bit di segno, il che spiega il dimensioneparola - 1. In effetti analizzando la traccia letteralmente come hai fatto tu si risolve proprio cosi', ma forse chi ha ideato la traccia pensava ad altro (?)

 

[St3ve]

Lo avevo pensato anche io, infatti in una prima versione avevo scritto n = -(n + 1), ma poi compilando ho notato che fungeva lo stesso e quindi ho pensato che il processore non avesse problemi a svolgere questo tipo di calcoli e che il problema si presentasse solo quando si trattava di inserire il valore all'interno di una variabile. Infatti prima dopo essere stato svolto il calcolo dall'ALU il valore viene salvato nell'accumulatore. Suppongo dunque che quest'ultimo sia capace di contenere valori molto piu' grandi. Queste sono osservazioni, probabilmente errate, che ho basato sulla mia flebile conoscenza della struttura di una CPU, dunque correggimi se non e' cosi' per favore : /

Compilare e notare che funziona è il motivo per cui gli undefined behavior sono un problema difficile da gestire. Il problema non è (solo) cosa succede nell'hardware, ma (anche) cosa succede nel compilatore.

Ad esempio, in C l'istruzione INT_MAX + 1 è un comportamento indefinito. Tuttavia, a livello di assembly non esiste il concetto di registro signed e unsigned (il segno viene gestito sulla singola operazione, tramite il flag register) quindi fare INT_MAX + 1 è ammesso ed ha lo stesso valore di INT_MIN. A livello hardware il comportamento è ben definito, ma il compilatore è libero di non considerare cosa succede nell'hardware per ottimizzare il codice come meglio crede:

#include <stdio.h>

int main() {
  int a;  // Manually insert 2147483647
  printf("Insert a number: ");
  scanf("%d", &a);

  int b = a + 1;

  if (a > b)
    printf("%d > %d\n", a, b);
  else
    printf("%d <= %d\n", a, b);

  return 0;
}

Questo codice potrebbe avere un output diverso se compilato con un compilatori diversi, anche se gira sullo stesso computer. Ecco cosa succede semplicemente abilitando le ottimizzazioni:

$ gcc -O0 -o ub ub.c && ./ub
Insert a number: 2147483647
2147483647 > -2147483648

$ gcc -O1 -o ub ub.c && ./ub
Insert a number: 2147483647
2147483647 <= -2147483648

Il compilatore assume a+1 > a dimenticandosi che INT_MAX + 1 == INT_MIN. Il comportamento è indefinito, quindi è un'assunzione che può fare.

Il punto e' che non c'e' relazione tra il numero minimo rappresentabile e la dimensione della parola se non con la rappresentazione in binario. Cioe', se la parola e' composta da x caratteri, allora un carattere occupa lo spazio per il bit di segno, il che spiega il dimensioneparola - 1. In effetti analizzando la traccia letteralmente come hai fatto tu si risolve proprio cosi', ma forse chi ha ideato la traccia pensava ad altro (?)

A me il testo sembra molto chiaro: in un sistema con complemento a due, il massimo valore rappresentabile da una parola di lunghezza w è 2^(w-1) - 1 mentre il minimo valore rappresentabile è -2^(w-1). Dire "complemento a due" già sottointende che la parola è binaria (che, tra l'altro, è un'assunzione che puoi assumere come implicita in un testo di informatica) e il massimo/minimo numero rappresentabile è indipendente dalla base con cui lo rappresenti. Che non avevi capito ci può stare, ma non vedo ambiguità: ti stava semplicemente dicendo che c'è un bug quando l'utente inserisce -2^(w-1) (che non necessariamente corrisponde a -2147483648).

 

[nostyn]

Il compilatore assume a+1 > a dimenticandosi che INT_MAX + 1 == INT_MIN. Il comportamento è indefinito, quindi è un'assunzione che può fare.

Molto interessante, ti ringrazio per questa parentesi, non avevo idea che il compilatore potesse operare simili semplificazioni!

A me il testo sembra molto chiaro: in un sistema con complemento a due, il massimo valore rappresentabile da una parola di lunghezza w è 2^(w-1) - 1 mentre il minimo valore rappresentabile è -2^(w-1). Dire "complemento a due" già sottointende che la parola è binaria (che, tra l'altro, è un'assunzione che puoi assumere come implicita in un testo di informatica) e il massimo/minimo numero rappresentabile è indipendente dalla base con cui lo rappresenti. Che non avevi capito ci può stare, ma non vedo ambiguità: ti stava semplicemente dicendo che c'è un bug quando l'utente inserisce -2^(w-1) (che non necessariamente corrisponde a -2147483648).

Va bene, lo terro' a mente per altri casi analoghi ^^