# GATE2014-2-34

9.3k views

For a C program accessing $\mathbf{X[i] [j] [k]}$, the following intermediate code is generated by a compiler. Assume that the size of an integer is $32$ bits and the size of a character is $8$ bits.

t0 = i ∗ 1024
t1 = j ∗ 32
t2 = k ∗ 4
t3 = t1 + t0
t4 = t3 + t2
t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

1. $\mathbf{X}$ is declared as "int $\mathbf{X[32] [32] [8]}$.
2. $\mathbf{X}$ is declared as "int $\mathbf{X[4] [1024] [32]}$.
3. $\mathbf{X}$ is declared as "char $\mathbf{X[4] [32] [8]}$.
4. $\mathbf{X}$ is declared as "char $\mathbf{X[32] [16] [2]}$.

edited
4
Can it be written like this?

t5 = X[ t4 ]

= X [ t3 ] [ t2 ]

= X [ to ] [ t1 ] [ t2 ]

= X [ i*1024 ][  j *32 ][ k * 4 ]

= X [ i * ( j * ( k * 4 ) ) ][ j * ( k * 4 )][ k * 4 ]  ( multiplication by 4 is due to 32 bit ( or 4 B) integer )

From here clearly option A) is the answer.
5

$(i\times j\times k+ j\times k+ k)\times 4\ bytes$

$Put\ A)\ values\ "intX[32][32][8]"\ above$

$=(32\times 32\times 8+32\times 8+8)\times 4$

$=33824$

$t5=X[t4]$

$t4=t3+t2$

$=t0+t1+k\times 4$

$=i\times 1024+j\times 32+k\times 4$

$Put\ A)\ values\ "intX[32][32][8]"\ in\ 't4'$

$=32\times 1024+ 32\times 32+ 8\times 4$

$=33824$

$Ans: A$

In order to visualize what exactly is happening: Refer here

$k$ is multiplied by $4$, means sizeof(dataype) is int.
$j$ is multiplied by $32$, means the inner most dimension of array is $32/4 = 8$ (we have to divide by the size of the inner dimension- which here is a simple integer)
$i$ is multiplied by $1024$, means the second dimension of array is $1024/32 = 32$ ($32 = 8*4$ is the size of the inner dimension here)

So, (A) is correct. The first dimension is not needed for code generation and that is why in C language while passing an array to a function, we can omit the value of the first dimension but not any others.

We can also do as follows:

$X[i][j][k] = *(*(*(X + i) + j) + k)$

In Integer arithmetic, this equals

$*(*(*(X + i * sizeof(*X) ) + j * sizeof(**X) + k * sizeof(***X) )$

as for every add to a pointer we have to multiply the size of the pointed value (to get a valid address)

So, from the given code we get

$sizeof(***X) = 4, -$ int
$sizeof(**X) = 32 -$ int  array  of size $8$
$sizeof(*X) = 1024 - 2$ $D$ int array of size $[32]$ havinf size of inner $1D$ array $32$.

So, the inner dimensions must be $32$ and $8$ and type must be integer. So, only option A matches.

edited by
0
0
Can anyone elaborate further did not understand
0
How is r1 calculated ?
2
See now..
0
@Das if u mean dimension one - that cant be calculated.. only assumed from choice..
0
Thank you Sir :)
0
Sir can u explain why we concluded that since k is multiplied by 4 the data type is int ????
0
Difference between option A) and C)?

0
Exactly... why c is wrong? It also has its outer dimensions 32 and 8 only
5

@srestha

why c is wrong? It also has its outer dimensions 32 and 8 only

This is because

Inner dimensions must be 32 and 8 and type must be integer

And option C is char type..so wrong.

0
@Arjun Suresh

Why only k is multiplied by 4 (size of each element), If 4 is size of each element of the array, then why multiply k alone, why not all the remaining elements in the 2D and 1D arrays (1024*i+32*j number of elements) we have surpassed to reach the desired element.
0
why the last element is 8. please explain the logic
3

Suppose given dimensions are X[a][b][c] and you have to find element at X[i][j][k] It will be done like

(i * b * c * size) + (j * c * size) + (k *size). Now in the code k is multiplied by 4 so we got size as 4. Now go in reverse way to calculate c (innermost dimension) we have

t1 = j ∗ 32 ----1

Our second term (j * c * size) ----2

c*size=32 and we know size is 4 so c is 8.

same we get b as 32.

Hope you got it. :)

0

For those asking about why it's an integer array, from the second explanation @Arjun da has given, since $sizeof(***X) = 4$, and $sizeof$ returns the size of a type in bytes, 4 bytes = 32 bits = integer type.

0

@Arjun

@Vikrant Singh

why we are access array like this,

actually 3d array address resolution  should be like,

FORMULA

**Row Major and Column Major for 3-D Array:
**ROW MAJOR OF A[I, J, K]=B+W[(K-Ko)*RC+(I-Io)*C+(J-Jo)]
COLUMN MAJOR OF A[I, J, K]=B+W[(K-Ko)*RC+(I-Io)+(J-Jo)*R]**

WHERE:
R=ROW
C=Column
K=Weidth
Ko=Lower Bound of Width
Io=Lower Bound of Row
Jo=Lower Bound of Column**

X is of type integer and dimensions of X are r1 X r2 X r3.

value of r2 = 32

r3 = 8

4
what can be said about r1?
0
0
So, if here t2= k*1 instead of k*4 then answer would be for Char array, is it?

For a while, assume that this 3-D array is of int type.

If I write int k = X[i][j][k]; Means I am looking for a particular integer value which is stored at the location *(X[i][j]+k) = *(*(X[i]+j)+k) = *(*(*(X+i)+j)+k)

Lets take an example of 1D array

if there is one 1D array A[10,20,30,40], Suppose, A is stored at 1000 location, intsize=4B
and If I write int k = A[2], means i am looking for an integer which is stored at *(A+2) location.

K = A[2]; Lets write intermediate code for this.

A[j] = *(A + j*intsize) = *( 1000 + 2*4) = *(1008) = 30 ( our element)

t1 = j*intsize
k = *(t2)  it will give 30 to us.

Now, take an example of 2D array.

Int k = B[3][5]; It will also assign k with an integer value. We have to find the location of that integer.

Suppose array B has x rows and y columns, and stored in memory in ROW MAJOR Order.

k = B[i][j] = *(B +([i*no.Of_Cols]+j)*intsize)
k = B[3][5] = *(B + ((3*y) + 5)*4)
Suppose number of rows = 30, number of columns =20
k=B[3][4]= *(Base address + ((3*20)+5)*4) = *(B.A + 3*20*4 + 5*4) = *(1000 + 240+ 20) = *(1260).
To access, B[3][5], i can also write B[260/4] = B[65] = *(B + 65*4) = *(1000 + 260) = *(1260)
Intermediate code for k = B[i][j];

t1 = j*intsize     = 5*4 = 20
t2 = i*#cols*instize  = 3*20*4 = 240
t3 = t1+t2  = 260
k = B[t3]; *(1000 + 260) = *(1260);

PS: Assume Array B is stored at memory location 1000.

Let's take 3-D array now.

int k = C[i][j][k].

It means we have to cross, i 2D arrays, j 1D arrays, and k elements to reach our required element.

= B.A + (i_2D_arrays*no._elements_In_1_2D_Array + j*no._elements_in_1_1D_Array + k)*intsize

=B.A + (i_2D_arrays*no._elements_In_1_2D_Array*instsize + j*no._elements_in_1_1D_Array*intsize + k*intsize)

Now, we can see in question that k is multiplied by 4, hence array X is of int type. options (C) and (D) are eliminated here.

j is multiplied by 32, and this calculation equals to j*no._elements_in_1_1D_Array*intsize=j*32 = j*8*4
it means there are 8 elements in one 1D array.

int X[][][8];  so far so good to eliminate option B.

Let's go further.

i*1024 = i*no._elements_In_1_2D_Array*intsize

number of columns in 2D arrays = 8
number of rows in 2D arrays 256/8 = 32

Hence, there 2D array is of [32][8] size.

i*1024 = i*32*8*4 = i is number of 2D arrays, 32x8 is size of one D array.

We can't calculate number of 2D arrays by the given code, and that is not even required for our question.

edited
0
@Manu Thanks lot :)
0
How 256/8 while calculating no. Of rows @Manu
2

But @Manu Thakur one question ,that is how you  can calculate number of columns in 2d array is 8 from number of elements of 1d array?

0
This should be the selected answer.
0
Thanks for such a wonderful answer.
0
Clearly explained

The final expression can be simplified in form ofi, j and k by following the intermediate code steps in reverse order

t5 = X[t4]
= X[t3 + t2]
= X[t1 + t0 + t2]
= X[i*1024 + j*32 + k*4]
= X + i*1024 + j*32 + k*4 

Since k is multiplied by 4, the array must be an int array. We are left with 2 choices (A and B) among the 4 given choices. X[i][j][k]'th element in one dimensional array is equivalent to X[i*M*L + j*L + k]'th element in one dimensional array (Note that multi-dimensional arrays are stored in row major order in C). So we get following equations

j*L*4 = j*32, we get L = 8 (4 is the sizeof(int))
i*1024 = i*M*L*4, we get M = 1024/32 = 32

## Therefore option A is the only correct option as M and L are 32 and 8 respectively only in option A.

0
Great and simple explanation !
0
What are M and L here?
0
It's size of data type mentioned in question.i.e., 32 and 8
0

### @Regina Phalange Ma'am why we are multiply j with L  like j*L and for i with M*L

Also how are you evaluating this   X + i*1024 + j*32 + k*4 to X[i*M*L + j*L + k]?

from where did this X[i*M*L + j*L + k] came?

0
This is answer for me. Thanks

If given permission , I would have up voted answer at least 10 times

Explanation -

Element needed - X[i][j][k]

A 3D array is a collection of 2D arrays and a 2D array is a collection of 1D arrays, and a 1D array is a collection of elements.

So, we need to first cross the required no. of 2D arrays(no. of elements in 1 2D array * i), then the required no. of 1D arrays(no. of elements in 1 1D array(no. of rows in 1 2D array) * j) in our reached 2D array, and then the required no. of elements in our reached 1D array(k).

1. We have t0 = i * 1024, which means that there are 1024 elements in 1 2D array.

2. We have t1 = j * 32, which means that we have 32 elements in 1 1D array of our 2D arrays or in other words, the no. of rows of our 2D array is 32, so the no. of columns can easily be found by 1024 / 32 = 32.

So now we have the dimensions of our 2D arrays = 32*32.

so clearly our answer is A (no other close option).

elaborating further,

3. We have calculated t3 of our 3-address code = (i * (32*32)) + (j * 32) + k.

4.We now need to multiply the above expression with the size of the datatype.

Since we have t2 = k * 4, it clearly means that the size of our datatype of each element is 4 bytes, hence an int.

And the expression t4 of our 3-address code in high level language is - ((i * (32*32)) + (j * 32) + k) * 4

5. t5 gives the specific element.

Conclusion - our required 3D array is - x[32][32][8] and it is of type integer.

Note - There is no way of finding out the 3rd dimension of our 3D array, here 8 with the help of our 3-address code, since its not required in the calculation of an element's location.

0
@ ravi_ssj4

Sir, I think u have made a mistake in point 2. j is the number of rows and 32 is the number of elements in each row, although this should not effect final answer.

And I could not understand why they have multiplied k by 4. If it is size of each element of the array, then why multiply k alone, why not all the remaining elements in the 2D and 1D arrays we have surpassed to reach the desired element.
 $int\ X$ $\underbrace{32}$ $\underbrace{32}$ $\underbrace{8}$ $Assume$ $streets$ $apartments$ $buildings$

According to question we need to find: $loc\ X[i][j][k]$

Size of int$:4B$

$Analogy:$ You want to go and meet your friend who lives in $k^{th}$ building of $j^{th}$ apartment which is on $i^{th}$ street.

1. First you will cross $i$ streets which contains $32$ apartments and in each apartment there are $8$ buildings

$\therefore\ 32\times 8\times 4=1024$

Hence $t_{0}=i\times 1024$

2. Now you will cross $j$ apartments which contains $8$ buildings

$\therefore\ 8\times 4=32$

Hence $t_{1}=j\times 32$

3. Now you will cross $k$ buildings

Hence $t_{2}=k\times 4$

Rest of the part everyone knows :)

3
Hmmm.. kiran sir haan! :)

Size of an integer = 32 bits = 4 Bytes
Size of a character = 8 bits = 1 Byte
Let array be

type x[A] [B] [C]
type  may be integer / character

we want  t5=x[t0+t1+t2]=x[i*1024 + j*32 + k*4 ] element,

From t0 = i *1024,
we can conclude that

B * C * (size of type) = 1024
From t1 = j *32, we can conclude that

C *(size of type) = 32
From t2 = k *4, we can conclude that

(size of type) = 4
therefore  type = int
C *4 = 32    => C = 8
B *8 * 4 = 1024 => B = 32

Choice (A)

Prerequisite: The visualisation of multidimensional arrays.

How do we get to $A[i][j]$ ? (in RMO)

From the base address, we skip $i$ rows and $j$ columns. This is quite well known.

See this or this for example.

Actually, a better perspective is to see it as skipping $i$ arrays and $j$ elements.

An even better perspective is to look at it as skipping $i$ $1D$ arrays, and $j$ elements.

By extending this, $A[i][j][k]$ is nothing but skipping $i$ $2D$ arrays, $j$ $1D$ arrays and $k$ elements. You can extend this generalised perspective to any number of dimensions.

Now,

t0 = i ∗ 1024
t1 = j ∗ 32
t2 = k ∗ 4 

This is nothing but "skipping". Start from the innermost index. We're skipping $k$ by multiples of $4$. So, single-elements in the array occupy space of $4$ (Bytes). Hence, we're dealing with ints.

We're skipping $j$ by multiples of $32$. This means the $1D$ "sub-arrays" are of size $32$ (Bytes).

//Visualisation of multidimensional arrays is needed. If you don't know how to picturise it, I'll draw that in the comments.

Size of the $1D$ array = $32$ .

Number of elements = $\frac{32}{4}=8$

So, the last array subscript has a size 8.

With this knowledge, Option A is the answer.

But let's continue.

We're skipping $i$ by multiples of $1024$. This means the $2D$ "sub-arrays" are of size $1024$ (Bytes).

Number of elements in $2D$ subarrays = $\frac{1024}{32}=32$

Hence, there are $32$ $1D$ subarrays.

So the middle subscript is of size 32.

Nothing can be concluded about the first subscript. (Why? Hint: we don't know the total number of 2D subarrays)

So, we conclude the array must have been declared like: $int X[?][32][8]$

## Related questions

1
3k views
Consider the expression tree shown. Each leaf represents a numerical value, which can either be $0$ or $1$. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.
Consider the grammar defined by the following production rules, with two operators $∗$ and $+$ $S\:\to\:T∗P$ $T\:\to\:U\mid T∗U$ $P\:\to\:Q+P\mid Q$ $Q\:\to Id$ $U\:\to Id$ Which one of the following is TRUE? $+$ is left associative, while $∗$ is right associative $+$ is right associative, while $∗$ is left associative Both $+$ and $∗$ are right associative Both $+$ and $∗$ are left associative
Suppose $n$ and $p$ are unsigned int variables in a C program. We wish to set p to $^nC_3$. If $n$ is large, which one of the following statements is most likely to set p correctly? $p = n * (n-1) * (n-2) / 6;$ $p = n * (n-1) / 2 * (n-2) / 3;$ $p = n * (n-1) / 3 * (n-2) / 2;$ $p = n * (n-1) * (n-2) / 6.0;$