Nie rozumiem tego sposobu obliczenia kwadratu liczby

135

Znalazłem funkcję, która oblicza kwadrat liczby:

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

Zwraca wartość n 2 . Pytanie brzmi, jak to się dzieje? Po krótkich testach stwierdziłem, że między (&a)[k]a (&a)[k+1]jest sizeof(a)/ sizeof(int). Dlaczego?

Emanuel
źródło
6
Czy masz linki do miejsc, w których znalazłeś te informacje?
R Sahu
4
int p(n)? Czy to się w ogóle kompiluje?
barak manos
78
To jest niesamowite, teraz nigdy więcej go nie używaj i zamiast tego użyj n * n ...
26
lub lepiej:int q(int n) { return sizeof (char [n][n]); }
ouah
17
@ouah zakładając, że to pytanie odnosi się do codegolf.stackexchange.com/a/43262/967, powodem, dla którego nie użyłem, sizeofbyło zapisywanie znaków. Wszyscy inni: to celowo niejasny kod, niezdefiniowane zachowanie, odpowiedź @ ouah jest poprawna.
ecatmur

Odpowiedzi:

117

Oczywiście hack ... ale sposób na podniesienie liczby do kwadratu bez użycia *operatora (był to wymóg zawodów w kodowaniu).

(&a)[n] 

jest odpowiednikiem wskaźnika do intat location

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

a zatem całe wyrażenie jest

  (&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
źródło
11
I jak jasno sugerujesz, ale czuję potrzebę wyjaśnienia, w najlepszym przypadku jest to hack. Operacja mnożenia nadal będzie tam działać; to tylko operator jest unikany.
Tommy,
Mam to, co się dzieje, ale moje prawdziwe pytanie brzmi: dlaczego (& a) [k] jest pod tym samym adresem co a + k * sizeof (a) / sizeof (int)
Emanuel
33
Jako stary programista jestem zaskoczony faktem, że kompilator może traktować (&a)jako wskaźnik do obiektu, n*sizeof(int)kiedy nnie jest znany w czasie kompilacji. C kiedyś był prostym językiem ...
Floris
To całkiem sprytny hack, ale coś, czego nie zobaczysz w kodzie produkcyjnym (miejmy nadzieję).
John Odom
14
Nawiasem mówiąc, jest to również UB, ponieważ zwiększa wskaźnik, aby nie wskazywał ani na element podstawowej tablicy, ani tylko na przeszłość.
Deduplicator
86

Aby zrozumieć ten hack, najpierw musisz zrozumieć różnicę wskaźników, tj. Co się stanie, gdy odejmie się dwa wskaźniki wskazujące na elementy tej samej tablicy ?

Kiedy jeden wskaźnik jest odejmowany od drugiego, wynikiem jest odległość (mierzona w elementach tablicy) między wskaźnikami. Tak więc, jeśli pwskazuje a[i]i qwskazuje na a[j], to p - qjest równei - j .

C11: 6.5.6 Operatory addytywne (p9):

Gdy odejmowane są dwa wskaźniki , oba wskazują elementy tego samego obiektu tablicy lub jeden za ostatnim elementem obiektu tablicy; wynik jest różnicą między indeksami dwóch elementów tablicy . […].
Innymi słowy, jeśli wyrażenia Pi Qwskazują, odpowiednio, i-ty i j-ty element obiektu tablicy, wyrażenie (P)-(Q)ma wartośći−j pod warunkiem, że wartość pasuje do obiektu typu ptrdiff_t.

Teraz oczekuję, że jesteś świadomy konwersji nazwy tablicy na wskaźnik, akonwertuje na wskaźnik do pierwszego elementu tablicy a. &ato adres całego bloku pamięci, czyli adres tablicy a. Poniższy rysunek pomoże ci zrozumieć ( przeczytaj tę odpowiedź, aby uzyskać szczegółowe wyjaśnienie ):

wprowadź opis obrazu tutaj

Pomoże ci to zrozumieć, dlaczego ai &ama ten sam adres i jaki (&a)[i]jest adres i- tej tablicy (tego samego rozmiaru co adres a).

A więc oświadczenie

return (&a)[n] - a; 

jest równa

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

a ta różnica da liczbę elementów między wskaźnikami (&a)[n]i (&a)[0], które są ntablicami każdego z n intelementów. Dlatego łączna liczba elementów tablicy wynosi n*n= n2 .


UWAGA:

C11: 6.5.6 Operatory addytywne (p9):

Gdy odejmowane są dwa wskaźniki, oba wskazują elementy tego samego obiektu tablicy lub jeden za ostatnim elementem obiektu tablicy ; wynik jest różnicą między indeksami dwóch elementów tablicy. Rozmiar wyniku jest zdefiniowany w implementacji , a jego typ (typ liczby całkowitej ze znakiem) jest ptrdiff_tzdefiniowany w <stddef.h>nagłówku. Jeśli wynik nie jest reprezentowalny w obiekcie tego typu, zachowanie jest niezdefiniowane.

Ponieważ (&a)[n]żaden z elementów tego samego obiektu tablicy ani jeden za ostatnim elementem obiektu tablicy nie (&a)[n] - awywoła niezdefiniowanego zachowania .

Zauważ też, że lepiej zmienić zwracany typ funkcji pna ptrdiff_t.

haccks
źródło
„oba powinny wskazywać na elementy tego samego obiektu tablicy” - co rodzi pytanie, czy ten „hack” wcale nie jest UB. Wyrażenie arytmetyczne wskaźnika odnosi się do hipotetycznego końca nieistniejącego obiektu: czy to w ogóle dozwolone?
Martin Ba,
Podsumowując, a jest adresem tablicy n elementów, więc & a [0] jest adresem pierwszego elementu w tej tablicy, który jest taki sam jak a; dodatkowo & a [k] zawsze będzie uważane za adres tablicy n elementów, niezależnie od k, a ponieważ & a [1..n] jest również wektorem, „lokalizacja” jego elementów jest kolejna, co oznacza pierwszy element jest na pozycji x, drugi na pozycji x + (liczba elementów wektora a, czyli n) i tak dalej. Czy mam rację? Jest to również przestrzeń sterty, więc czy oznacza to, że jeśli przydzielę nowy wektor o tych samych n elementach, jego adres jest taki sam jak (& a) [1]?
Emanuel
1
@Emanuel; &a[k]jest adresem kth elementu tablicy a. To (&a)[k]zawsze będzie uważany za adres tablicy kelementów. Zatem pierwszy element jest na pozycji a(lub &a), drugi na pozycji a+ (liczba elementów tablicy, aktóra wynosi n) * (rozmiar elementu tablicy) i tak dalej. Zauważ, że pamięć dla tablic o zmiennej długości jest przydzielana na stosie, a nie na stercie.
haccks
@MartinBa; Czy to w ogóle dozwolone? Nie. To nie jest dozwolone. Jego UB. Zobacz edycję.
haccks
1
@haccks miły zbieg okoliczności między naturą pytania a twoim pseudonimem
Dimitar Tsonev
35

ajest (zmienną) tablicą n int.

&ajest wskaźnikiem do (zmiennej) tablicy n int.

(&a)[1]jest wskaźnikiem o intjeden intza ostatnim elementem tablicy. Ten wskaźnik znajduje się n intpo elementach &a[0].

(&a)[2]jest wskaźnikiem o intjeden intza ostatnim elementem tablicy dwóch tablic. Ten wskaźnik znajduje się 2 * n intpo elementach &a[0].

(&a)[n]jest wskaźnikiem o intjeden intza ostatnim elementem ntablicy. Ten wskaźnik znajduje się n * n intpo elementach &a[0]. Po prostu odejmij &a[0]lub ai masz n.

Oczywiście jest to technicznie niezdefiniowane zachowanie, nawet jeśli działa na twojej maszynie, ponieważ (&a)[n]nie wskazuje wewnątrz tablicy ani o jeden za ostatnim elementem tablicy (zgodnie z wymaganiami reguł C arytmetyki wskaźników).

ouah
źródło
Cóż, rozumiem, ale dlaczego to się dzieje w C? Jaka jest tego logika?
Emanuel
@Emanuel nie ma na to ściślejszej odpowiedzi niż ta arytmetyka wskaźników, która jest przydatna do pomiaru odległości (zwykle w tablicy), [n]składnia deklaruje tablicę, a tablice rozkładają się na wskaźniki. Trzy osobno przydatne rzeczy z tą konsekwencją.
Tommy,
1
@Emanuel jeśli pytasz , dlaczego ktoś miałby to zrobić, nie ma powodu, a każdy powód nie aby ze względu na charakter UB działania. Warto zwrócić uwagę, że (&a)[n]jest to typ int[n], a to wyraża się jako int*dzięki tablicom wyrażającym się jako adres ich pierwszego elementu, na wypadek, gdyby nie było to jasne w opisie.
WhozCraig,
Nie, nie miałem na myśli, dlaczego ktoś to zrobił, chodziło mi o to, dlaczego standard C zachowuje się tak w tej sytuacji.
Emanuel
1
@Emanuel Pointer Arithmetic (w tym przypadku podrozdział tego tematu: różnicowanie wskaźników ). Warto googlować, a także przeczytać pytania i odpowiedzi na tej stronie. ma wiele użytecznych korzyści i jest konkretnie zdefiniowany w normach, jeśli jest właściwie stosowany. Aby w pełni zrozumieć to ty masz , aby zrozumieć, w jaki sposób typy w kodzie wymienione są wymyślone.
WhozCraig,
12

Jeśli masz dwa wskaźniki, które wskazują na dwa elementy tej samej tablicy, to ich różnica da liczbę elementów między tymi wskaźnikami. Na przykład ten fragment kodu wyświetli 2.

int a[10];

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

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

Rozważmy teraz wyrażenie

(&a)[n] - a;

W tym wyrażeniu ama typ int *i wskazuje na swój pierwszy element.

Wyrażenie &ama typ int ( * )[n]i wskazuje pierwszy wiersz obrazowanej dwuwymiarowej tablicy. Jego wartość jest zgodna z wartością, achociaż typy są różne.

( &a )[n]

jest n-tym elementem tej obrazowanej dwuwymiarowej tablicy i ma typ int[n]To jest n-ty wiersz obrazowanej tablicy. W wyrażeniu (&a)[n] - ajest konwertowany na adres swojego pierwszego elementu i ma typ `int *.

Więc pomiędzy (&a)[n]i aistnieje n rzędów n elementów. Więc różnica będzie równa n * n.

Vlad z Moskwy
źródło
Czyli za każdą tablicą jest macierz o rozmiarze n * n?
Emanuel
@Emanuel Pomiędzy tymi dwoma wskaźnikami znajduje się macierz nxn elementów. A różnica wskaźników daje wartość równą n * n, czyli ile elementów znajduje się między wskaźnikami.
Vlad z Moskwy
Ale dlaczego ta macierz o rozmiarze n * n jest za nią? Czy ma to jakieś zastosowanie w C? Chodzi mi o to, że C „przydzielił” więcej tablic o rozmiarze n bez mojej wiedzy? Jeśli tak, czy mogę ich używać? W przeciwnym razie, dlaczego miałaby powstać ta macierz (mam na myśli, że musi mieć cel, aby tam była).
Emanuel,
2
@Emanuel - Ta macierz to tylko wyjaśnienie, jak działa arytmetyka wskaźników w tym przypadku. Ta macierz nie jest przydzielona i nie można jej używać. Jak już kilkakrotnie stwierdzano, 1) ten fragment kodu to hack, który nie ma praktycznego zastosowania; 2) musisz się nauczyć, jak działa arytmetyka wskaźników, aby zrozumieć ten hack.
void_ptr,
@Emanuel To wyjaśnia arytmetykę wskaźnika. Wyrażenie (& a) [n] jest wskaźnikiem do n-elementu obrazowanej dwuwymiarowej tablicy ze względu na arytmetykę wskaźnika.
Vlad z Moskwy
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

A zatem,

  1. typ (&a)[n]to int[n]wskaźnik
  2. typ ato intwskaźnik

Teraz wyrażenie (&a)[n]-awykonuje odejmowanie wskaźnika:

  (&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
jedyny
źródło