The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+45 votes
5.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]}$.
asked in Compiler Design by Veteran (113k points)
edited by | 5.3k views
0
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 Answers

+60 votes
Best answer

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

answered by Veteran (379k points)
edited by
0
Any Reference link for this Answer?
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)?

Why C) cannot be answer?
0
Exactly... why c is wrong? It also has its outer dimensions 32 and 8 only
+3

@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
0

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. :)

+37 votes

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

 value of r2 = 32

r3 = 8

answered by Boss (13.6k points)
+4
what can be said about r1?
0
thanx for this answer.
0
So, if here t2= k*1 instead of k*4 then answer would be for Char array, is it?
+16 votes

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]=*(Base Address + j*intsize)

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

t1 = j*intsize
t2 = baseAddress + t1
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.

So, the answer is (A). 

answered by Boss (42.3k points)
edited ago by
0
@Manu Thanks lot :)
0
How 256/8 while calculating no. Of rows @Manu
+1

This is the best answer.

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.
+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.

answered by Active (3.4k points)
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.
+7 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.

answered by Loyal (9.2k points)
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?

Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,241 questions
51,468 answers
178,539 comments
66,754 users