edited by
33,496 views
100 votes
100 votes

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 by

9 Answers

12 votes
12 votes

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.

11 votes
11 votes

Answer - A

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.

5 votes
5 votes

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]$

4 votes
4 votes

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)

Answer:

Related questions

44 votes
44 votes
7 answers
1
29 votes
29 votes
4 answers
4
go_editor asked Sep 28, 2014
9,178 views
Which one of the following is NOT performed during compilation?Dynamic memory allocationType checkingSymbol table managementInline expansion