不能理解这个方法来计算一个数字的平方?

时间:2022-08-02 20:53:51

I have found a function that calculates square of a number:

我找到了一个计算数字平方的函数:

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

It returns value of n2. Question is, how does it do that? After a little testing, I found that between (&a)[k] and (&a)[k+1] is sizeof(a)/sizeof(int). Why is that?

它返回n2的值。问题是,它是怎么做到的?经过一些测试后,我发现在(&a)[k]和(&a)[k+1]之间是sizeof(a)/sizeof(int)。这是为什么呢?

5 个解决方案

#1


116  

Obviously a hack... but a way of squaring a number without using the * operator (this was a coding contest requirement).

显然一个黑客…但是一种不使用*操作符(这是编码竞赛要求)的方法。

(&a)[n] 

is equivalent to a pointer to int at location

是否等价于指向位置的指针?

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

and thus the entire expression is

整个表达式就是。

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

#2


86  

To understand this hack, first you need to understand the pointer difference, i.e, what happens when two pointers pointing to elements of same array are subtracted?

要理解这个hack,首先需要了解指针的区别。当两个指向相同数组元素的指针被减去时,会发生什么?

When one pointer is subtracted from another, the result is the distance (measured in array elements) between the pointers. So, if p points to a[i] and q points to a[j], then p - q is equal to i - j.

当一个指针从另一个指针中减去时,结果就是指针之间的距离(以数组元素度量)。所以,如果p指向a[i], q指向a[j],那么p - q等于i - j。

C11: 6.5.6 Additive operators (p9):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. [...].
In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i−j provided the value fits in an object of type ptrdiff_t.

当两个指针被减去时,它们都指向相同数组对象的元素,或者是数组对象的最后一个元素;结果是两个数组元素的下标的不同。[…]。换句话说,如果表达式P和Q指向一个数组对象的第i个和第j个元素,那么表达式(P)-(Q)就具有i j提供的值,该值适合于ptrdiff_t类型的对象。

Now I am expecting that you are aware of array name conversion to pointer, a converts to pointer to first element of array a. &a is address of the entire memory block, i.e it is an address of array a. The figure below will help you to understand (read this answer for detailed explanation):

现在我期望您知道数组名称转换为指针,一个转换为指向数组a的第一个元素的指针。e是数组a的地址,下面的图将帮助您理解(请阅读以下详细说明的答案):

不能理解这个方法来计算一个数字的平方?

This will help you to understand that why a and &a has the same address and how (&a)[i] is the address of ith array (of same size as that of a).

这将帮助您理解为什么a和&a有相同的地址,以及(和)[i]是第ith数组的地址(与a的大小相同)。

So, the statement

因此,声明

return (&a)[n] - a; 

is equivalent to

相当于

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

and this difference will give the number of elements between the pointers (&a)[n] and (&a)[0], which are n arrays each of n int elements. Therefore, total array elements are n*n = n2.

这种差异将给出指针(和)[n]和(&a)[0]之间的元素个数,它们是n个数组,每一个n个int元素。因此,总数组元素是n*n = n2。


NOTE:

注意:

C11: 6.5.6 Additive operators (p9):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined.

当两个指针被减去时,它们都指向相同数组对象的元素,或者是数组对象的最后一个元素;结果是两个数组元素的下标的不同。结果的大小是由实现定义的,它的类型(一个有符号整数类型)是在 头。如果结果不能在该类型的对象中表示,则该行为是未定义的。 中定义的ptrdiff_t。h>

Since (&a)[n] neither points to elements of the same array object nor one past the last element of the array object, (&a)[n] - a will invoke undefined behavior.

由于(和)[n]既不指向相同数组对象的元素,也不指向数组对象的最后一个元素,(&a)[n] - a将调用未定义的行为。

Also note that, better to change the return type of function p to ptrdiff_t.

还要注意,最好将函数p的返回类型改为ptrdiff_t。

#3


34  

a is a (variable) array of n int.

a是一个(变量)n int数组。

&a is a pointer to a (variable) array of n int.

&a是一个指向一个(变量)数组的指针。

(&a)[1] is a pointer of int one int past the last array element. This pointer is n int elements after &a[0].

(和)[1]是一个int型指针,它通过了最后一个数组元素。这个指针是在和[0]之后的n int元素。

(&a)[2] is a pointer of int one int past the last array element of two arrays. This pointer is 2 * n int elements after &a[0].

(和)[2]是一个指针,一个int型的指针,通过两个数组的最后一个数组元素。这个指针是在[0]之后的2 * n int元素。

(&a)[n] is a pointer of int one int past the last array element of n arrays. This pointer is n * n int elements after &a[0]. Just subtract &a[0] or a and you have n.

(和)[n]是一个指针,一个int型的指针经过n个数组的最后一个数组元素。这个指针是在[0]之后的n * n int元素。只要减去和[0]或者a,就有n。

Of course this is technically undefined behavior even if it works on your machine as (&a)[n] does not point inside the array or one past the last array element (as required by the C rules of pointer arithmetic).

当然,这在技术上是未定义的行为,即使它在你的机器上运行(和)[n]也不指向数组或过去的最后一个数组元素(根据指针算法的C规则)。

#4


12  

If you have two pointers that point to two elements of the same array then its difference will yield the number of elements between these pointers. For example this code snippet will output 2.

如果你有两个指针指向同一个数组的两个元素,那么它的不同就会产生这些指针之间的元素个数。例如,这个代码片段将输出2。

int a[10];

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

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

Now let consider expression

现在我们考虑的表情

(&a)[n] - a;

In this expression a has type int * and points to its first element.

在这个表达式中,a具有类型int *并指向它的第一个元素。

Expression &a has type int ( * )[n] and points to the first row of imaged two dimensional array. Its value matches the value of a though types are different.

表达式和有类型int (*)[n],并指向二维数组的第一行。它的值与a的值相匹配,但类型不同。

( &a )[n]

is n-th element of this imaged two dimensional array and has type int[n] That is it is n-th row of the imaged array. In expression (&a)[n] - a it is converted to the address of its first element and has type `int *.

是这个image二维数组的第n个元素,它有int[n],它是image数组的第n行。在表达式(&a)中,它被转换为它的第一个元素的地址,并且有type ' int *。

So between (&a)[n] and a there are n rows of n elements. So the difference will be equal to n * n.

因此,在(和)[n]和a之间有n行n行元素。所以差就等于n * n。

#5


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

Thus,

因此,

  1. type of (&a)[n] is int[n] pointer
  2. 类型的(和)[n]是int[n]指针。
  3. type of a is int pointer
  4. a的类型是int指针。

Now the expression (&a)[n]-a performs a pointer substraction:

现在,表达式(&a)[n]-a执行一个指针的substraction:

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

#1


116  

Obviously a hack... but a way of squaring a number without using the * operator (this was a coding contest requirement).

显然一个黑客…但是一种不使用*操作符(这是编码竞赛要求)的方法。

(&a)[n] 

is equivalent to a pointer to int at location

是否等价于指向位置的指针?

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

and thus the entire expression is

整个表达式就是。

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

#2


86  

To understand this hack, first you need to understand the pointer difference, i.e, what happens when two pointers pointing to elements of same array are subtracted?

要理解这个hack,首先需要了解指针的区别。当两个指向相同数组元素的指针被减去时,会发生什么?

When one pointer is subtracted from another, the result is the distance (measured in array elements) between the pointers. So, if p points to a[i] and q points to a[j], then p - q is equal to i - j.

当一个指针从另一个指针中减去时,结果就是指针之间的距离(以数组元素度量)。所以,如果p指向a[i], q指向a[j],那么p - q等于i - j。

C11: 6.5.6 Additive operators (p9):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. [...].
In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i−j provided the value fits in an object of type ptrdiff_t.

当两个指针被减去时,它们都指向相同数组对象的元素,或者是数组对象的最后一个元素;结果是两个数组元素的下标的不同。[…]。换句话说,如果表达式P和Q指向一个数组对象的第i个和第j个元素,那么表达式(P)-(Q)就具有i j提供的值,该值适合于ptrdiff_t类型的对象。

Now I am expecting that you are aware of array name conversion to pointer, a converts to pointer to first element of array a. &a is address of the entire memory block, i.e it is an address of array a. The figure below will help you to understand (read this answer for detailed explanation):

现在我期望您知道数组名称转换为指针,一个转换为指向数组a的第一个元素的指针。e是数组a的地址,下面的图将帮助您理解(请阅读以下详细说明的答案):

不能理解这个方法来计算一个数字的平方?

This will help you to understand that why a and &a has the same address and how (&a)[i] is the address of ith array (of same size as that of a).

这将帮助您理解为什么a和&a有相同的地址,以及(和)[i]是第ith数组的地址(与a的大小相同)。

So, the statement

因此,声明

return (&a)[n] - a; 

is equivalent to

相当于

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

and this difference will give the number of elements between the pointers (&a)[n] and (&a)[0], which are n arrays each of n int elements. Therefore, total array elements are n*n = n2.

这种差异将给出指针(和)[n]和(&a)[0]之间的元素个数,它们是n个数组,每一个n个int元素。因此,总数组元素是n*n = n2。


NOTE:

注意:

C11: 6.5.6 Additive operators (p9):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined.

当两个指针被减去时,它们都指向相同数组对象的元素,或者是数组对象的最后一个元素;结果是两个数组元素的下标的不同。结果的大小是由实现定义的,它的类型(一个有符号整数类型)是在 头。如果结果不能在该类型的对象中表示,则该行为是未定义的。 中定义的ptrdiff_t。h>

Since (&a)[n] neither points to elements of the same array object nor one past the last element of the array object, (&a)[n] - a will invoke undefined behavior.

由于(和)[n]既不指向相同数组对象的元素,也不指向数组对象的最后一个元素,(&a)[n] - a将调用未定义的行为。

Also note that, better to change the return type of function p to ptrdiff_t.

还要注意,最好将函数p的返回类型改为ptrdiff_t。

#3


34  

a is a (variable) array of n int.

a是一个(变量)n int数组。

&a is a pointer to a (variable) array of n int.

&a是一个指向一个(变量)数组的指针。

(&a)[1] is a pointer of int one int past the last array element. This pointer is n int elements after &a[0].

(和)[1]是一个int型指针,它通过了最后一个数组元素。这个指针是在和[0]之后的n int元素。

(&a)[2] is a pointer of int one int past the last array element of two arrays. This pointer is 2 * n int elements after &a[0].

(和)[2]是一个指针,一个int型的指针,通过两个数组的最后一个数组元素。这个指针是在[0]之后的2 * n int元素。

(&a)[n] is a pointer of int one int past the last array element of n arrays. This pointer is n * n int elements after &a[0]. Just subtract &a[0] or a and you have n.

(和)[n]是一个指针,一个int型的指针经过n个数组的最后一个数组元素。这个指针是在[0]之后的n * n int元素。只要减去和[0]或者a,就有n。

Of course this is technically undefined behavior even if it works on your machine as (&a)[n] does not point inside the array or one past the last array element (as required by the C rules of pointer arithmetic).

当然,这在技术上是未定义的行为,即使它在你的机器上运行(和)[n]也不指向数组或过去的最后一个数组元素(根据指针算法的C规则)。

#4


12  

If you have two pointers that point to two elements of the same array then its difference will yield the number of elements between these pointers. For example this code snippet will output 2.

如果你有两个指针指向同一个数组的两个元素,那么它的不同就会产生这些指针之间的元素个数。例如,这个代码片段将输出2。

int a[10];

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

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

Now let consider expression

现在我们考虑的表情

(&a)[n] - a;

In this expression a has type int * and points to its first element.

在这个表达式中,a具有类型int *并指向它的第一个元素。

Expression &a has type int ( * )[n] and points to the first row of imaged two dimensional array. Its value matches the value of a though types are different.

表达式和有类型int (*)[n],并指向二维数组的第一行。它的值与a的值相匹配,但类型不同。

( &a )[n]

is n-th element of this imaged two dimensional array and has type int[n] That is it is n-th row of the imaged array. In expression (&a)[n] - a it is converted to the address of its first element and has type `int *.

是这个image二维数组的第n个元素,它有int[n],它是image数组的第n行。在表达式(&a)中,它被转换为它的第一个元素的地址,并且有type ' int *。

So between (&a)[n] and a there are n rows of n elements. So the difference will be equal to n * n.

因此,在(和)[n]和a之间有n行n行元素。所以差就等于n * n。

#5


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

Thus,

因此,

  1. type of (&a)[n] is int[n] pointer
  2. 类型的(和)[n]是int[n]指针。
  3. type of a is int pointer
  4. a的类型是int指针。

Now the expression (&a)[n]-a performs a pointer substraction:

现在,表达式(&a)[n]-a执行一个指针的substraction:

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