Не могу понять, как рассчитать квадрат числа

135

Я нашел функцию, которая вычисляет квадрат числа:

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

Возвращает значение n 2 . Вопрос в том, как это сделать? После небольшого тестирования я обнаружил, что между (&a)[k]и (&a)[k+1]есть sizeof(a)/ sizeof(int). Это почему?

Эмануэль
источник
6
У вас есть ссылки на то, где вы нашли эту информацию?
Р Саху
4
int p(n)? Это даже компилируется?
Барак Манос
78
Это потрясающе, теперь никогда не используйте его снова и вместо этого используйте n * n ...
26
или лучше:int q(int n) { return sizeof (char [n][n]); }
ouah
17
@ouah, если предположить, что этот вопрос относится к codegolf.stackexchange.com/a/43262/967, поэтому я не использовал sizeofего для сохранения символов. Все остальные: это намеренно неясный код, это неопределенное поведение, ответ @ ouah правильный.
Ecatmur

Ответы:

117

Очевидно, что взломать ... но способ возведения в квадрат числа без использования *оператора (это было требование конкурса кодирования).

(&a)[n] 

эквивалентно указателю intна местоположение

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

и, таким образом, все выражение

  (&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
Марк Лаката
источник
11
И, как вы явно подразумеваете, но я чувствую необходимость сделать это явно, это в лучшем случае синтаксический взлом. Операция умножения все еще будет там; это просто оператор, которого избегают.
Томми
Я понял, что происходит, но мой реальный вопрос - почему (& a) [k] находится по тому же адресу, что и + k * sizeof (a) / sizeof (int)
Эмануэль
33
Как старый кодер, я удивлен тем фактом, что компилятор может обращаться (&a)с указателем на объект, n*sizeof(int)когда nон неизвестен во время компиляции. Раньше был простой язык ...
Флорис
Это довольно умный взлом, но то, что вы не увидите в рабочем коде (надеюсь).
Джон Одом
14
Кроме того, это также UB, потому что он увеличивает указатель, чтобы указать ни на элемент базового массива, ни просто на прошлое.
Дедупликатор
86

Чтобы понять этот хак, сначала нужно понять разницу в указателях, т. Е. Что происходит, когда два указателя указывают на элементы одного массива вычитаются ?

Когда один указатель вычитается из другого, результатом является расстояние (измеренное в элементах массива) между указателями. Итак, если pуказывает на a[i]и qуказывает на a[j], тоp - q равноi - j .

C11: 6.5.6 Аддитивные операторы (p9):

Когда вычтены два указателя , оба должны указывать на элементы одного и того же объекта массива или один после последнего элемента объекта массива; Результатом является разница индексов двух элементов массива . [...].
Другими словами, если выражения Pи Qуказывают, соответственно, на i-й и j-й элементы объекта массива, выражение (P)-(Q)имеет значениеi−j при условии, что это значение соответствует объекту типа ptrdiff_t.

Теперь я ожидаю, что вы знаете о преобразовании имени массива в указатель, aпреобразует указатель на первый элемент массива a. &aэто адрес всего блока памяти, т.е. это адрес массива a. Рисунок ниже поможет вам понять ( прочитайте этот ответ для подробного объяснения ):

введите описание изображения здесь

Это поможет вам понять , что , почему aи &aимеет тот же адрес , и как (&a)[i]это адрес I - го массива (такого же размера, как уa ).

Итак, утверждение

return (&a)[n] - a; 

эквивалентно

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

и эта разница будет давать количество элементов между указателями (&a)[n]и (&a)[0], которые являются nмассивами каждого из n intэлементов. Следовательно, все элементы массива равны n*n= n2 .


НОТА:

C11: 6.5.6 Аддитивные операторы (p9):

Когда вычтены два указателя, оба должны указывать на элементы одного и того же объекта массива или один после последнего элемента объекта массива ; Результатом является разница индексов двух элементов массива. Размер результата определяется реализацией , а его тип (целочисленный тип со знаком) ptrdiff_tопределяется в <stddef.h>заголовке. Если результат не может быть представлен в объекте этого типа, поведение не определено.

Поскольку (&a)[n]ни указатель на элементы одного и того же объекта массива, ни на один элемент после последнего элемента объекта массива (&a)[n] - aне вызовет неопределенное поведение .

Также отметим , что, лучше изменить тип возвращаемого значения функции pв ptrdiff_t.

haccks
источник
«оба должны указывать на элементы одного и того же объекта массива» - что вызывает у меня вопрос, не является ли этот «хак» UB в конце концов. Арифметическое выражение указателя относится к гипотетическому концу несуществующего объекта: это вообще разрешено?
Мартин Ба
Итак, a - это адрес массива из n элементов, поэтому & a [0] - это адрес первого элемента в этом массиве, который совпадает с a; кроме того, & a [k] всегда будет считаться адресом массива из n элементов, независимо от k, а поскольку & a [1..n] также является вектором, «местоположение» его элементов является последовательным, что означает первый элемент находится в позиции x, второй - в позиции x + (количество элементов вектора a, равное n) и так далее. Я прав? Кроме того, это пространство кучи, значит ли это, что если я выделю новый вектор из тех же n элементов, его адрес будет таким же, как (& a) [1]?
Эммануил
1
@Emanuel; &a[k]это адрес kэлемента массива a. Это (&a)[k]то, что всегда будет считаться адресом массива kэлементов. Итак, первый элемент находится в позиции a(или &a), второй - в позиции a+ (количество элементов массива, aкоторое есть n) * (размер элемента массива) и так далее. И обратите внимание, что память для массивов переменной длины выделяется в стеке, а не в куче.
хак
@MartinBa; Это даже разрешено? Нет, это не разрешено Его UB. Смотрите редактирование.
хак
1
@ Счастливое совпадение природы вопроса и вашего псевдонима
Димитар Цонев
35

a является (переменным) массивом n int .

&a указатель на (переменную) массив n int .

(&a)[1]это указатель на intодин intпосле последнего элемента массива. Этот указатель является n intэлементами после&a[0] .

(&a)[2]является указателем intодного intпоследнего элемента массива из двух массивов. Этот указатель является 2 * n intэлементами после&a[0] .

(&a)[n]является указателем на intодин intпосле последнего элемента массива nмассивов. Этот указатель является n * n intэлементами после &a[0]. Просто вычтите &a[0]или у aвас естьn .

Конечно, это технически неопределенное поведение, даже если оно работает на вашем компьютере, так как (&a)[n]не указывает внутри массива или после последнего элемента массива (как того требуют правила C арифметики указателей).

ouah
источник
Ну, я понял, но почему это происходит в C? Какая логика стоит за этим?
Эммануил
@ Эммануил, на самом деле нет более строгого ответа на этот вопрос, чем эта арифметика указателей, полезная для измерения расстояния (обычно в массиве), [n]синтаксис объявляет массив, а массивы разлагаются на указатели. Три отдельно полезные вещи с этим следствием.
Томми
1
@ Эммануил, если вы спрашиваете, почему кто-то это сделал, у нас мало причин, и нет причин не из-за природы UB. И стоит отметить, что (&a)[n]это тип int[n]и который выражается как int*массив массивов, выражающий в качестве адреса их первого элемента, в случае, если это не было ясно в описании.
WhozCraig
Нет, я не имел в виду, почему кто-то сделал бы это, я имел в виду, почему стандарт C ведет себя так в этой ситуации.
Эммануил
1
@ Эмануэль Указатель Арифметика (и в этом случае подраздел этой темы: разность указателей ). Стоит погуглить, а также читать вопросы и ответы на этом сайте. он имеет много полезных преимуществ и конкретно определен в стандартах при правильном использовании. Чтобы полностью понять это, вы должны понять, как измышлены типы в коде, который вы перечислили.
WhozCraig
12

Если у вас есть два указателя, которые указывают на два элемента одного и того же массива, то его разность приведет к количеству элементов между этими указателями. Например, этот фрагмент кода выведет 2.

int a[10];

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

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

Теперь давайте рассмотрим выражение

(&a)[n] - a;

В этом выражении aимеет тип int *и указывает на его первый элемент.

Выражение &aимеет тип int ( * )[n]и указывает на первый ряд отображаемого двумерного массива. Его значение соответствует значению aразных типов.

( &a )[n]

является n-м элементом этого отображаемого двумерного массива и имеет тип, int[n]то есть это n-й ряд отображаемого массива. В выражении (&a)[n] - aон преобразуется в адрес своего первого элемента и имеет тип `int *.

Таким образом, между (&a)[n]и aесть n строк из n элементов. Так что разница будет равна n * n.

Влад из Москвы
источник
Значит, за каждым массивом стоит матрица размером n * n?
Эммануил
@Emanuel Между этими двумя указателями есть матрица из nxn элементов. А разность указателей дает значение, равное n * n, то есть сколько элементов находится между указателями.
Влад из Москвы
Но почему эта матрица размером n * n отстает? Это имеет какое-либо применение в C? Я имею в виду, это как C "выделил" больше массивов размера n, не зная об этом? Если да, могу ли я их использовать? В противном случае, почему эта матрица должна быть сформирована (я имею в виду, у нее должна быть цель, чтобы она была там).
Эммануил
2
@Emanuel - эта матрица является только объяснением того, как арифметика указателей работает в этом случае. Эта матрица не выделена, и вы не можете ее использовать. Как уже было сказано несколько раз: 1) этот фрагмент кода является хаком, который не имеет практического применения; 2) вам нужно узнать, как работает арифметика указателей, чтобы понять этот взлом.
void_ptr
@Emanuel Это объясняет арифметику указателя. Expreesion (& a) [n] - указатель на n-элемент отображаемого двумерного массива из-за арифметики указателя.
Влад из Москвы
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

Таким образом,

  1. тип (&a)[n]являетсяint[n]указатель
  2. тип a İŞ intуказатель

Теперь выражение (&a)[n]-aвыполняет вычитание указателя:

  (&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
источник