in Compiler Design edited by
32,886 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]}$.
in Compiler Design edited by
32.9k views

4 Comments

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.
7
7
edited by

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

16
16
Trial and error kind of method:
form the equation for address at A[i][j][k], which will be 1024i+32j+4k.

That makes A[0][0][0], 0.

similarly A[0][1][0] = 32, A[0][2][0] = 64, ie incrementing by 32 implying a 32 bit integer. (C and D eliminated)
Now A[1][0][0] = 1024, which means A[0][j_max][0] – 1024-32 = 992, and 992/32 = 31.
j_max = 31, and 31-0+1, 32 integers.
0
0

9 Answers

109 votes
109 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.

edited by
by

4 Comments

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

https://stackoverflow.com/questions/33463594/element-address-in-3-dimensional-array

0
0
$∗(∗(∗(X+i∗sizeof(∗X))+j∗sizeof(∗∗X){\color{Blue} )}+k∗sizeof(∗∗∗X))$

one closing bracket is missing :P
1
1
Awesome explanation,cleared my concepts regarding 3d array.
0
0
59 votes
59 votes

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

 value of r2 = 32

r3 = 8

3 Comments

what can be said about r1?
6
6
thanx for this answer.
0
0
So, if here t2= k*1 instead of k*4 then answer would be for Char array, is it?
0
0
56 votes
56 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). 

edited by

4 Comments

edited by

@Manu Thakur Sir,

Here , $j$ is multiplied by $32$ and as size of each element is $4$, Thus we get $8$ elements in one $1D$ array, so we get  $X[][][8]$.

Then, further , $i$ is multiplied by $1024$, so by dividing it by $32$ we can get size of $2D$ array(i.e the number of $1D$ arrays in $2D$ array)(which is $32$).

so we get $X[][32][8]$,

my doubt is that,

if in option $C$ the type is changed to $int$,

Then both $A$  and $C$ will be correct here right?

0
0

@Pranavpurkar yes in that codition answer willbe both A and C….

0
0

@Pranavpurkar yes in that codition answer will be both A and C….

0
0
20 votes
20 votes
$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 :)

1 comment

Hmmm.. kiran sir haan! :)
7
7
Answer:

Related questions