Question

多维数组和线性数组在本质上是一样的。 因为计算机内存是线性的，它是一维数组。但是一维数组可以很容易用来表现多维的。 比如数组 a[3][4]元素可以放置在一维数组的 12 个单元中：

#!bash
[0][0]
[0][1]
[0][2]
[0][3]
[1][0]
[1][4]
[1][5]
[1][6]
[2][0]
[2][7]
[2][8]
[2][9]

该二维数组在内存中用一维数组索引表示为：

	1	2	3
4	5	6	7
8	9	10	11

为了计算我们需要的元素地址，首先，第一个索引乘以 4（矩阵宽度），然后加上第二个索引。这种被称为行优先，C/C++和 Python 常用这种方法。行优先的意思是：先写入第一行，接着是第二行，…，最后是最后一行。 另一种方法就是列优先，主要用在 FORTRAN,MATLAB,R 等。列优先的意思是：先写入第一列，然后是第二列，…，最后是最后一列。 多维数组与此类似。 我们看个例子： Listing 16.4: simple example

#!cpp
#include <stdio.h>

int a[10][20][30];

void insert(int x, int y, int z, int value)
{
    a[x][y][z]=value;
};

16.5.1 x86

MSVC 2010：

Listing 16.5: MSVC 2010

#!bash
_DATA   SEGMENT
COMM    _a:DWORD:01770H
_DATA   ENDS
PUBLIC  _insert
_TEXT   SEGMENT
_x$ = 8         ; size = 4
_y$ = 12        ; size = 4
_z$ = 16        ; size = 4
_value$ = 20    ; size = 4
_insert     PROC
    push    ebp
    mov     ebp, esp
    mov     eax, DWORD PTR _x$[ebp]
    imul    eax, 2400                   ; eax=600*4*x
    mov     ecx, DWORD PTR _y$[ebp]
    imul    ecx, 120                    ; ecx=30*4*y
    lea     edx, DWORD PTR _a[eax+ecx]  ; edx=a + 600*4*x + 30*4*y
    mov     eax, DWORD PTR _z$[ebp]
    mov     ecx, DWORD PTR _value$[ebp]
    mov     DWORD PTR [edx+eax*4], ecx  ; *(edx+z*4)=value
    pop     ebp
    ret     0
_insert ENDP
_TEXT ENDS

多维数组计算索引公式： address=600*4*x+30*4*y+4z 。因为 int 类型为 32-bits（4 字节），所以要乘以 4。

Listing 16.6: GCC 4.4.1

#!bash
        public insert
insert  proc near
x       = dword ptr 8
y       = dword ptr 0Ch
z       = dword ptr 10h
value   = dword ptr 14h
        push    ebp
        mov     ebp, esp
        push    ebx
        mov     ebx, [ebp+x]
        mov     eax, [ebp+y]
        mov     ecx, [ebp+z]
        lea     edx, [eax+eax] ; edx=y*2
        mov     eax, edx ; eax=y*2
        shl     eax, 4 ; eax=(y*2)<<4 = y*2*16 = y*32
        sub     eax, edx ; eax=y*32 - y*2=y*30
        imul    edx, ebx, 600 ; edx=x*600
        add     eax, edx ; eax=eax+edx=y*30 + x*600
        lea     edx, [eax+ecx] ; edx=y*30 + x*600 + z
        mov     eax, [ebp+value]
        mov     dword ptr ds:a[edx*4], eax ; *(a+edx*4)=value
        pop     ebx
        pop     ebp
        retn
insert  endp

GCC 使用的不同的计算方法。为计算第一个操作值 30y，GCC 没有使用乘法指令。GCC 的做法是：(???? + ????) ? 4 ? (???? + ????) = (2????) ? 4 ? 2???? = 2 ? 16 ? ???? ? 2???? = 32???? ? 2???? = 30????。因此 30y 的计算仅使用加法和移位操作，这样速度更快。