Não consigo entender essa maneira de calcular o quadrado de um número

135

Eu encontrei uma função que calcula o quadrado de um número:

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

Retorna o valor de n 2 . A questão é: como isso acontece? Após um pequeno teste, descobri que entre (&a)[k]e (&a)[k+1]é sizeof(a)/ sizeof(int). Por que é que?

Emanuel
fonte
6
Você tem links para onde você encontrou essas informações?
R Sahu
4
int p(n)? Isso compila mesmo?
barak manos
78
Isso é incrível, agora nunca mais use-o novamente e use n * n ...
26
ou melhor:int q(int n) { return sizeof (char [n][n]); }
ouah
17
@ouah supondo que esta pergunta se refira a codegolf.stackexchange.com/a/43262/967, a razão pela qual não usei sizeoffoi para salvar caracteres. Todos os outros: este é um código intencionalmente obscuro, é um comportamento indefinido, a resposta de @ ouah está correta.
ecatmur

Respostas:

117

Obviamente, um hack ... mas uma maneira de quadrilhar um número sem usar o *operador (este era um requisito de concurso de codificação).

(&a)[n] 

é equivalente a um ponteiro para intno local

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

e assim toda a expressão é

  (&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
fonte
11
E, como você claramente sugere, mas sinto a necessidade de explicitar, é um hack de sintaxe, na melhor das hipóteses. A operação de multiplicação ainda estará lá embaixo; é apenas o operador que está sendo evitado.
Tommy
Eu tenho o que acontece por trás, mas a minha verdadeira pergunta é por isso que (& a) [k] é no mesmo endereço como um + k * sizeof (a) / sizeof (int)
Emanuel
33
Como um codificador antigo, fico surpreso pelo fato de o compilador poder tratar (&a)como um ponteiro para um objeto de n*sizeof(int)quando nnão é conhecido em tempo de compilação. C costumava ser uma simples linguagem ...
Floris
Isso é um truque bastante inteligente, mas algo que você não veria no código de produção (espero).
John Odom
14
Como um aparte, também é UB, porque incrementa um ponteiro para apontar nem para um elemento da matriz subjacente, nem apenas para o passado.
Deduplicator
86

Para entender esse hack, primeiro você precisa entender a diferença de ponteiro, ou seja, o que acontece quando dois ponteiros apontando para elementos da mesma matriz são subtraídos?

Quando um ponteiro é subtraído de outro, o resultado é a distância (medida em elementos da matriz) entre os ponteiros. Então, se paponta para a[i]e qaponta para a[j], então p - qé igual ai - j .

C11: 6.5.6 Operadores aditivos (p9):

Quando dois ponteiros são subtraídos , ambos apontam para elementos do mesmo objeto de matriz ou um após o último elemento do objeto de matriz; o resultado é a diferença dos subscritos dos dois elementos da matriz . [...]
Em outras palavras, se as expressões Pe Qapontarem para, respectivamente, os elementos -ésimo i-ésimo j-ésimo de um objeto de matriz, a expressão (P)-(Q)terá o valori−j desde que o valor se ajuste a um objeto do tipo ptrdiff_t.

Agora, espero que você esteja ciente da conversão do nome da matriz em ponteiro, aconverta em ponteiro no primeiro elemento da matriz a. &aé o endereço de todo o bloco de memória, ou seja, é um endereço do array a. A figura abaixo ajudará você a entender ( leia esta resposta para obter explicações detalhadas ):

insira a descrição da imagem aqui

Isso ajudará você a entender que por isso ae &atem o mesmo endereço e como (&a)[i]é o endereço do i th array (de mesmo tamanho que a do a).

Então, a afirmação

return (&a)[n] - a; 

é equivalente a

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

e essa diferença fornecerá o número de elementos entre os ponteiros (&a)[n]e (&a)[0], que são nmatrizes cada um dos n intelementos. Portanto, o total de elementos da matriz é n*n= n2 .


NOTA:

C11: 6.5.6 Operadores aditivos (p9):

Quando dois ponteiros são subtraídos, ambos apontam para elementos do mesmo objeto de matriz ou um após o último elemento do objeto de matriz ; o resultado é a diferença dos subscritos dos dois elementos da matriz. O tamanho do resultado é definido pela implementação e seu tipo (um tipo inteiro assinado) é ptrdiff_tdefinido no <stddef.h>cabeçalho. Se o resultado não for representável em um objeto desse tipo, o comportamento será indefinido.

Como (&a)[n]nem pontos para elementos do mesmo objeto de matriz nem um após o último elemento do objeto de matriz, (&a)[n] - ainvocará um comportamento indefinido .

Observe também que é melhor alterar o tipo de retorno da função ppara ptrdiff_t.

haccks
fonte
"ambos apontarão para elementos do mesmo objeto de matriz" - o que levanta a questão para mim se esse "hack" não é UB, afinal. A expressão aritmética do ponteiro está se referindo ao fim hipotético de um objeto inexistente: isso é permitido?
Martin Ba
Para resumir, a é o endereço de uma matriz de n elementos, então & a [0] é o endereço do primeiro elemento dessa matriz, que é igual a a; além disso, & a [k] sempre será considerado um endereço de uma matriz de n elementos, independentemente de k, e como & a [1..n] também é um vetor, a "localização" de seus elementos é consecutiva, significando o primeiro elemento está na posição x, o segundo está na posição x + (número de elementos do vetor a que é n) e assim por diante. Estou certo? Além disso, este é um espaço de heap, então isso significa que, se eu alocar um novo vetor dos mesmos n elementos, seu endereço será o mesmo que (& a) [1]?
Emanuel
1
@Emanuel; &a[k]é um endereço do kth elemento da matriz a. É (&a)[k]que sempre será considerado o endereço de uma matriz de kelementos. Assim, em primeiro elemento está na posição a(ou &a), segundo está na posição a+ (número de elementos de matriz aque é n) * (tamanho de um elemento de matriz) e assim por diante. E observe que a memória para matrizes de comprimento variável é alocada na pilha, não na pilha.
haccks
@MartinBa; Isso é permitido? Não. Não é permitido. É UB. Veja a edição.
haccks
1
@haccks boa coincidência entre a natureza da pergunta e seu apelido #
Dimitar Tsonev
35

aé uma matriz (variável) de n int.

&aé um ponteiro para uma matriz (variável) de n int.

(&a)[1]é um ponteiro de intum intpassado o último elemento da matriz. Este ponteiro é n intelementos depois &a[0].

(&a)[2]é um ponteiro de intum intpassado o último elemento da matriz de duas matrizes. Este ponteiro é 2 * n intelementos depois &a[0].

(&a)[n]é um ponteiro de intum intpassado o último elemento da matriz de nmatrizes. Este ponteiro é n * n intelementos depois &a[0]. Basta subtrair &a[0]ou ae você tem n.

É claro que esse é um comportamento tecnicamente indefinido, mesmo que funcione em sua máquina, pois (&a)[n]não aponta para dentro da matriz ou ultrapassa o último elemento da matriz (conforme exigido pelas regras C da aritmética dos ponteiros).

ouah
fonte
Bem, eu entendi, mas por que isso acontece em C? Qual é a lógica por trás disso?
Emanuel
@Emanuel Não existe uma resposta mais rígida para isso, pois a aritmética do ponteiro é útil para medir a distância (geralmente em uma matriz), a [n]sintaxe declara uma matriz e as matrizes se decompõem em ponteiros. Três coisas separadamente úteis com essa conseqüência.
Tommy
1
@Emanuel Se você está perguntando por que alguém faria isso, há poucas razões e todas as razões para isso não devido à natureza UB da ação. E é importante notar que (&a)[n]é tipo int[n], e que se expressa como int*devido às matrizes que exprimem como o endereço do seu primeiro elemento, no caso de que não estava claro na descrição.
precisa saber é o seguinte
Não, eu não quis dizer por que alguém faria isso, eu quis dizer por que o padrão C se comporta dessa maneira nesta situação.
Emanuel
1
@Emanuel Aritmética de ponteiros (e, neste caso, um subcapítulo desse tópico: diferenciação de ponteiros ). Vale a pena pesquisar no Google, bem como ler perguntas e respostas neste site. possui muitos benefícios úteis e é definido concretamente nos padrões quando usado adequadamente. Para compreendê-lo completamente, você precisa entender como os tipos no código que você listou são inventados.
precisa saber é o seguinte
12

Se você tiver dois ponteiros que apontam para dois elementos da mesma matriz, sua diferença produzirá o número de elementos entre esses ponteiros. Por exemplo, este trecho de código produzirá 2.

int a[10];

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

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

Agora vamos considerar a expressão

(&a)[n] - a;

Nesta expressão atem tipo int *e aponta para seu primeiro elemento.

A expressão &atem tipo int ( * )[n]e aponta para a primeira linha da matriz bidimensional da imagem. Seu valor corresponde ao valor dos atipos diferentes.

( &a )[n]

é o n-ésimo elemento dessa matriz bidimensional da imagem e tem o tipo int[n]Isso é a n-ésima linha da matriz da imagem. Na expressão, (&a)[n] - aele é convertido no endereço do seu primeiro elemento e tem o tipo `int *.

Portanto, entre (&a)[n]e aexistem n linhas de n elementos. Então a diferença será igual a n * n.

Vlad de Moscou
fonte
Então, atrás de toda matriz, existe uma matriz do tamanho n * n?
Emanuel
@ Emanuel Entre esses dois ponteiros, existe uma matriz de elementos nxn. E a diferença dos ponteiros dá um valor igual a n * n, que é quantos elementos há entre os ponteiros.
Vlad de Moscovo
Mas por que essa matriz do tamanho n * n fica para trás? Tem algum uso em C? Quero dizer, é como C "alocou" mais matrizes do tamanho n, sem que eu saiba? Se sim, posso usá-los? Caso contrário, por que essa matriz seria formada (quero dizer, ela deve ter um propósito para estar lá).
Emanuel
2
@ Emanuel - Essa matriz é apenas uma explicação de como a aritmética dos ponteiros funciona nesse caso. Essa matriz não está alocada e você não pode usá-la. Como já foi dito algumas vezes, 1) esse trecho de código é um hack que não tem uso prático; 2) você precisa aprender como a aritmética do ponteiro funciona para entender esse hack.
void_ptr
@ Emanuel Isso explica a aritmética do ponteiro. A expressão (& a) [n] é um ponteiro para o n elemento da matriz bidimensional da imagem devido à aritmética do ponteiro.
Vlad de Moscow
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

Portanto,

  1. tipo de (&a)[n]é int[n]ponteiro
  2. tipo de aé intponteiro

Agora a expressão (&a)[n]-aexecuta uma subtração de ponteiro:

  (&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
fonte