Ich kann diese Methode zur Berechnung des Quadrats einer Zahl nicht verstehen

135

Ich habe eine Funktion gefunden, die das Quadrat einer Zahl berechnet:

int p(int n) {
    int a[n]; //works on C99 and above
    return (&a)[n] - a;
}

Es gibt den Wert von n 2 zurück . Die Frage ist, wie macht das das? Nach ein wenig Test fand ich das zwischen (&a)[k]und (&a)[k+1]ist sizeof(a)/ sizeof(int). Warum ist das so?

Emanuel
quelle
6
Haben Sie Links zu dem Ort, an dem Sie diese Informationen gefunden haben?
R Sahu
4
int p(n)? Kompiliert das überhaupt?
Barak Manos
78
Das ist großartig, jetzt benutze es nie wieder und benutze stattdessen n * n ...
26
oder besser:int q(int n) { return sizeof (char [n][n]); }
ouah
17
@ouah unter der Annahme, dass sich diese Frage auf codegolf.stackexchange.com/a/43262/967 bezieht, war der Grund, den ich nicht verwendet habe sizeof, das Speichern von Zeichen. Alle anderen: Dies ist absichtlich dunkler Code, es ist undefiniertes Verhalten, @ ouahs Antwort ist richtig.
ecatmur

Antworten:

117

Offensichtlich ein Hack ... aber eine Möglichkeit, eine Zahl ohne Verwendung des *Operators zu quadrieren (dies war eine Anforderung für einen Codierungswettbewerb).

(&a)[n] 

entspricht einem Zeiger auf intat location

(a + sizeof(a[n])*n)

und somit ist der gesamte Ausdruck

  (&a)[n] -a 

= (a + sizeof(a[n])*n -a) /sizeof(int)

= sizeof(a[n])*n / sizeof(int)
= sizeof(int) * n * n / sizeof(int)
= n * n
Mark Lakata
quelle
11
Und wie Sie eindeutig andeuten, aber ich habe das Bedürfnis, dies explizit zu machen, handelt es sich bestenfalls um einen Syntax-Hack. Die Multiplikationsoperation wird dort noch ausgeführt. Es ist nur der Bediener, der vermieden wird.
Tommy
Ich habe verstanden, was dahinter steckt, aber meine eigentliche Frage ist, warum (& a) [k] an derselben Adresse ist wie a + k * sizeof (a) / sizeof (int)
Emanuel
33
Als alten Kauz bin ich von der Tatsache überrascht , dass der Compiler behandeln kann (&a)als ein Zeiger auf ein Objekt , n*sizeof(int)wenn zum nZeitpunkt der Kompilierung nicht bekannt ist. C war früher eine einfache Sprache ...
Floris
Das ist ein ziemlich kluger Hack, aber etwas, das Sie (hoffentlich) nicht im Produktionscode sehen würden.
John Odom
14
Nebenbei bemerkt ist es auch UB, weil es einen Zeiger inkrementiert, um weder auf ein Element des zugrunde liegenden Arrays zu zeigen, noch einfach vorbei.
Deduplikator
86

Um diesen Hack zu verstehen, müssen Sie zuerst den Zeigerunterschied verstehen, dh was passiert, wenn zwei Zeiger, die auf Elemente desselben Arrays zeigen, subtrahiert werden?

Wenn ein Zeiger von einem anderen subtrahiert wird, ist das Ergebnis der Abstand (gemessen in Array-Elementen) zwischen den Zeigern. Wenn also pauf a[i]und qzeigt auf a[j], dann p - qist gleichi - j .

C11: 6.5.6 Additive Operatoren (S. 9):

Wenn zwei Zeiger subtrahiert werden , zeigen beide auf Elemente desselben Array-Objekts oder auf einen nach dem letzten Element des Array-Objekts. Das Ergebnis ist die Differenz der Indizes der beiden Array-Elemente . [...].
Mit anderen Worten, wenn die Ausdrücke Pund Qauf das i-te bzw. das j-te Element eines Array-Objekts verweisen , hat der Ausdruck (P)-(Q)den Wert,i−j sofern der Wert in ein Objekt vom Typ passt ptrdiff_t.

Jetzt erwarte ich, dass Sie wissen, dass der Array-Name in einen Zeiger akonvertiert und in einen Zeiger auf das erste Element des Arrays konvertiert wird a. &aist die Adresse des gesamten Speicherblocks, dh es ist eine Adresse des Arrays a. Die folgende Abbildung hilft Ihnen beim Verständnis ( lesen Sie diese Antwort für eine detaillierte Erklärung ):

Geben Sie hier die Bildbeschreibung ein

Dies hilft Ihnen zu verstehen, warum aund &ahat die gleiche Adresse und wie (&a)[i]ist die Adresse des i- ten Arrays (von der gleichen Größe wie die von a).

Also die Aussage

return (&a)[n] - a; 

ist äquivalent zu

return (&a)[n] - (&a)[0];  

und dieser Unterschied gibt die Anzahl der Elemente zwischen den Zeigern (&a)[n]und an (&a)[0], die nArrays jedes n intElements sind. Daher sind die gesamten Array-Elemente n*n= n2 .


HINWEIS:

C11: 6.5.6 Additive Operatoren (S. 9):

Wenn zwei Zeiger subtrahiert werden, zeigen beide auf Elemente desselben Array-Objekts oder auf einen nach dem letzten Element des Array-Objekts . Das Ergebnis ist die Differenz der Indizes der beiden Array-Elemente. Die Größe des Ergebnisses ist implementierungsdefiniert und sein Typ (ein vorzeichenbehafteter Integer-Typ) ist ptrdiff_tim <stddef.h>Header definiert . Wenn das Ergebnis in einem Objekt dieses Typs nicht darstellbar ist, ist das Verhalten undefiniert.

Da (&a)[n]weder auf Elemente desselben Array-Objekts noch auf Elemente hinter dem letzten Element des Array-Objekts verweist, (&a)[n] - awird undefiniertes Verhalten aufgerufen .

Beachten Sie auch, dass es besser ist, den Rückgabetyp der Funktion pin zu ändern ptrdiff_t.

Haccks
quelle
"beide sollen auf Elemente desselben Array-Objekts verweisen" - was für mich die Frage aufwirft, ob dieser "Hack" doch nicht UB ist. Der arithmetische Zeigerausdruck bezieht sich auf das hypothetische Ende eines nicht existierenden Objekts: Ist dies überhaupt erlaubt?
Martin Ba
Zusammenfassend ist a die Adresse eines Arrays von n Elementen, also ist & a [0] die Adresse des ersten Elements in diesem Array, die mit a identisch ist; Außerdem wird & a [k] unabhängig von k immer als Adresse eines Arrays von n Elementen betrachtet, und da & a [1..n] ebenfalls ein Vektor ist, ist die "Position" seiner Elemente aufeinanderfolgend, was bedeutet Das erste Element befindet sich an Position x, das zweite an Position x + (Anzahl der Elemente des Vektors a, der n ist) und so weiter. Habe ich recht? Dies ist auch ein Heap-Raum. Bedeutet dies, dass wenn ich einen neuen Vektor mit denselben n Elementen zuordne, seine Adresse dieselbe ist wie (& a) [1]?
Emanuel
1
@Emanuel; &a[k]ist eine Adresse des kElements des Arrays a. Es ist (&a)[k]das, was immer als Adresse eines Arrays von kElementen betrachtet wird. So ist das erste Element an der Position a(oder &a), die zweite an der Position a+ (Anzahl der Elemente des Arrays , awelche ist n) * (Größe eines Array - Elements) und so weiter. Beachten Sie, dass der Speicher für Arrays mit variabler Länge auf dem Stapel und nicht auf dem Heap zugewiesen wird.
haccks
@ MartinBa; Ist das überhaupt erlaubt? Nein, es ist nicht erlaubt. Es ist UB. Siehe die Bearbeitung.
Haccks
1
@haccks schöner Zufall zwischen der Natur der Frage und Ihrem Spitznamen
Dimitar Tsonev
35

aist ein (variables) Array von n int.

&aist ein Zeiger auf ein (variables) Array von n int.

(&a)[1]ist ein Zeiger von inteins intnach dem letzten Array-Element. Dieser Zeiger ist n intElemente nach &a[0].

(&a)[2]ist ein Zeiger von inteins intnach dem letzten Array-Element von zwei Arrays. Dieser Zeiger ist 2 * n intElemente nach &a[0].

(&a)[n]ist ein Zeiger von inteins intnach dem letzten Array-Element von nArrays. Dieser Zeiger ist n * n intElemente nach &a[0]. Einfach subtrahieren &a[0]oder aund du hast n.

Dies ist natürlich ein technisch undefiniertes Verhalten, selbst wenn es auf Ihrem Computer (&a)[n]funktioniert, da es nicht innerhalb des Arrays oder nach dem letzten Array-Element zeigt (wie in den C-Regeln der Zeigerarithmetik vorgeschrieben).

ouah
quelle
Nun, das habe ich verstanden, aber warum passiert das in C? Was ist die Logik dahinter?
Emanuel
@Emanuel Es gibt keine strengere Antwort darauf als die Zeigerarithmetik, die zum Messen der Entfernung nützlich ist (normalerweise in einem Array). Die [n]Syntax deklariert ein Array und Arrays zerlegen sich in Zeiger. Drei getrennt nützliche Dinge mit dieser Konsequenz.
Tommy
1
@Emanuel Wenn Sie fragen, warum jemand dies tun würde, gibt es wenig Grund und jeden Grund, dies nicht aufgrund der UB-Natur der Aktion zu tun . Und es ist erwähnenswert, dass dies (&a)[n]ein Typ int[n]ist , der sich int*aufgrund von Arrays ausdrückt, die als Adresse ihres ersten Elements ausgedrückt werden , falls dies in der Beschreibung nicht klar war.
WhozCraig
Nein, ich meinte nicht, warum jemand dies tun würde, ich meinte, warum sich der C-Standard in dieser Situation so verhält.
Emanuel
1
@Emanuel Pointer Arithmetic (und in diesem Fall ein Unterkapitel dieses Themas: Zeigerdifferenzierung ). Es lohnt sich zu googeln und Fragen und Antworten auf dieser Seite zu lesen. Es hat viele nützliche Vorteile und ist bei sachgemäßer Verwendung in den Normen konkret definiert. Um es vollständig zu erfassen Sie haben zu verstehen , wie die Typen in dem Code , den Sie ersonnen aufgelistet.
WhozCraig
12

Wenn Sie zwei Zeiger haben, die auf zwei Elemente desselben Arrays zeigen, ergibt die Differenz die Anzahl der Elemente zwischen diesen Zeigern. Zum Beispiel gibt dieses Code-Snippet 2 aus.

int a[10];

int *p1 = &a[1];
int *p2 = &a[3];

printf( "%d\n", p2 - p1 ); 

Betrachten wir nun den Ausdruck

(&a)[n] - a;

In diesem Ausdruck ahat Typ int *und zeigt auf sein erstes Element.

Der Ausdruck &ahat Typ int ( * )[n]und zeigt auf die erste Zeile des abgebildeten zweidimensionalen Arrays. Sein Wert entspricht dem Wert, aobwohl die Typen unterschiedlich sind.

( &a )[n]

ist das n-te Element dieses abgebildeten zweidimensionalen Arrays und hat den Typ int[n]Das heißt, es ist die n-te Zeile des abgebildeten Arrays. Im Ausdruck (&a)[n] - awird es in die Adresse seines ersten Elements konvertiert und hat den Typ `int *.

Also zwischen (&a)[n]und aes gibt n Reihen von n Elementen. Der Unterschied wird also gleich sein n * n.

Vlad aus Moskau
quelle
Hinter jedem Array befindet sich also eine Matrix der Größe n * n?
Emanuel
@Emanuel Zwischen diesen beiden Zeigern befindet sich eine Matrix von nxn Elementen. Und die Differenz der Zeiger ergibt einen Wert gleich n * n, dh wie viele Elemente sich zwischen den Zeigern befinden.
Vlad aus Moskau
Aber warum liegt diese Matrix der Größe n * n dahinter? Hat es irgendeine Verwendung in C? Ich meine, es ist, als hätte C mehr Arrays der Größe n "zugewiesen", ohne dass ich es weiß? Wenn ja, kann ich sie verwenden? Warum sollte diese Matrix sonst gebildet werden (ich meine, sie muss einen Zweck haben, damit sie da ist).
Emanuel
2
@Emanuel - Diese Matrix ist nur eine Erklärung dafür, wie Zeigerarithmetik in diesem Fall funktioniert. Diese Matrix ist nicht zugeordnet und kann nicht verwendet werden. Wie bereits einige Male erwähnt, 1) ist dieses Code-Snippet ein Hack, der keinen praktischen Nutzen hat; 2) Sie müssen lernen, wie Zeigerarithmetik funktioniert, um diesen Hack zu verstehen.
void_ptr
@Emanuel Dies erklärt die Zeigerarithmetik. Expreesion (& a) [n] ist aufgrund der Zeigerarithmetik ein Zeiger auf das n-Element des abgebildeten zweidimensionalen Arrays.
Vlad aus Moskau
4
Expression     | Value                | Explanation
a              | a                    | point to array of int elements
a[n]           | a + n*sizeof(int)    | refer to n-th element in array of int elements
-------------------------------------------------------------------------------------------------
&a             | a                    | point to array of (n int elements array)
(&a)[n]        | a + n*sizeof(int[n]) | refer to n-th element in array of (n int elements array)
-------------------------------------------------------------------------------------------------
sizeof(int[n]) | n * sizeof(int)      | int[n] is a type of n-int-element array

So,

  1. Typ (&a)[n]ist int[n]Zeiger
  2. Typ aist intZeiger

Jetzt führt der Ausdruck (&a)[n]-aeine Zeigersubtraktion durch:

  (&a)[n]-a
= ((a + n*sizeof(int[n])) - a) / sizeof(int)
= (n * sizeof(int[n])) / sizeof(int)
= (n * n * sizeof(int)) / sizeof(int)
= n * n
onlyice
quelle