Address Calculation in an Array

This tutorial is written for the GATE aspirants. At first, we discuss how to calculate an address in an array, and then we understand the concepts with some examples.

Arrays can be of two types: one-dimensional and two-dimensional. The address calculation takes different formula for these two types of arrays.

One-dimensional Array

Let $A[lb,ub]$ be a one-dimensional array, where $lb$ and $ub$ are the starting and ending indices.

Suppose $b$ represents the base address of the array $A$, and $c$ is the size of each element in $A$.

Now, the address of the $i$-th element in $A$ can be computed using the following formula:

$$Address(A[i]) = b + (i - lb)*c.$$

Two-dimensional Array

Let $A[lb_1,ub_1][lb_2,ub_2]$ be a two-dimensional array of order $m \times n$, where $lb_1$ and $ub_1$ are the starting and ending row indices, and $lb_2$ and $ub_2$ are the starting and ending column indices.

Suppose $b$ represents the base address of the array $A$, and $c$ is the size of each element in $A$.

The address of the $i$-th element of $A$ can be found using the following two formula, depending on how the array $A$ stored in the memory:

Row Major Order

$$Address(A[i][j]) = b + [i - lb_1]*n + (j - lb_2)*c.$$

Column Major Order

$$Address(A[i][j]) = b + [j - lb_2]*m + (j - lb_1)*c.$$

Now, let us apply the above formula in some examples.

Example 1: Consider the array $A[1, 100]$, base address = 200, size of each element = 3 bytes. Find the address of the element $A[57]$.

Answer:

Here, $b = 200$, $c = 3$, $lb = 1$, $i = 57$.

$Address(A[i])$

$= b + (i - lb)*c$

$= 200 + (57 - 1)*3$

$= 368$

Example 2: Consider the array $A[10, 100][20, 150]$, base address = 150, size of each element = 2 bytes. Find the address of the element $A[35][50]$ by row major order.

Answer:

Here, $b = 150$, $lb_1 = 10$, $lb_2 = 20$, $ub_1 = 100$, $ub_2 = 150$, $c = 2$, $n = (ub_2 - ub_1) + 1 = 51$, $i = 35$, $j = 50$.

$Address(A[i][j]) = b + [i - lb_1]*n + (j - lb_2)*c$

$= 150 + (35 - 10)*51 + (50 - 20)*2$

$= 1485$