Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

How was it decided that if you have an array/struct or anything similiar in a programming language it should be zero-based? Wouldn't it have been easier if it was 1-based. Afer all, when we are taught to count, we start with one.

share|improve this question
9  
+1 for asking a question most thinking developers wonder about but didnt bother to ask. –  DPD Apr 23 '11 at 2:37
3  
Because binary numbers start at zero. –  rwong Apr 23 '11 at 4:43
10  
Afer all, when we are taught to count, we start with one. - this is exactly the problem with basic math education, they are on a pre-Peano/Frege/Dedekind level still. –  Ingo Apr 23 '11 at 12:10
6  
@rwong There's no thing like binary number. There are just numbers and their representations. Unsigned integers starts at 0. –  maaartinus Apr 24 '11 at 11:12
    
@maaartinus: yes you're right. In any base-n numeral system, a string of zeros (in base-n) will give you zero, the lowest non-negative number. Zero is also the additive identity, so it is required to be present for calculations. If, however, a programming language choose to start with one, it's just as simple - skip the element [0]. –  rwong Apr 24 '11 at 20:04
show 1 more comment

9 Answers

up vote 33 down vote accepted

All good answers. A good part of my "career" was spent in Fortran, where all arrays are 1-based. It's OK if you're writing math algorithms over vectors and matrices, where indices naturally go 1 .. N.

But as soon as you start trying to do computer-science type algorithms, where you have a big array and you are working on pieces of it, as in binary search, or heap sort, or if it is a memory array and you are writing memory allocation and freeing algorithms, or starting to act like parts of it are actually multidimensional arrays that you have to calculate indices in, that 1-based stuff gets to be a real source of confusion.

For example, if you have a 1-dimensional array A, and you want to treat it as a 2-dimensional NxM array, where I and J are the index variables, in C you just say:

A[ I + N*J ]

but in Fortran you say

A( (I-1) + N*(J-1) + 1 )
       or
A( I + N*(J-1) )

If it was 3-dimensional, you had to do

A( I + N*(J-1) + N*M*(K-1) )

(That's if it was column-major order, as opposed to row-major order which is more common in C.)

What I learned to do in Fortran, when doing string manipulation algorithms, was never to think of an index I as being the position of an element in an array. Rather I would think of a "distance" N as being the number of elements coming before the element of interest. In other words, always think in terms of "number of elements" rather that "index of element". That enabled me to work within what was an unnatural indexing scheme.

share|improve this answer
14  
+1 - the bottom line is that indexing from zero results in simpler programs overall. Once programming language design stopped being overly influenced by mathematical convention, common sense prevailed. –  Stephen C Apr 23 '11 at 3:19
1  
@Mike On the other hand, with 0-based arrays you always have to do a[pos-1] to get what you want. The only case where 0-base feels natural is when looping, but that's only because the idiom for(i=0;i<len;i++) a[i]; works. –  Martin Wickman Apr 23 '11 at 9:29
    
In my opinion, this is the "correct" answer, but there are trade-offs. One trade-off, as you mention, is its use in 1 dimensional vs. multidimensional arrays. Base 0 indexing if of huge benefit when calculating multidimensional indexes. In higher-level programming, however, the use of 1 dimensional arrays, however, vastly outweighs the usage of multidimensional arrays. Further, the complexities of multidimensional indexing can be written once and encapsulated within a method (or indexer). [Continued...] –  Mike Rosenblum Apr 23 '11 at 14:37
1  
In low level programming, however, say asm or C, where performance is at a premium and inlining might not be available, the use of encapsulation might not be desirable or possible; so the benefits of base 0 indexing really manifests itself. So base 0 indexing is superior at the low end, while base 1 indexing is superior at the higher, more abstracted level. [Cont...] –  Mike Rosenblum Apr 23 '11 at 14:37
1  
The problem is, where does one make the switch? The switchover from base 0 at a low level to base 1 at a higher level is extremely dangerous and fraught with innumerable places to forget to add or subtract 1 when making a conversion. So the bottom line is that it's not worth the risk of making the shift. Usually the "shift" occurs only in the output, where the user is shown a list that is (hopefully) numbered 1 to N and not numbered 0 to N-1. (But I've seen plenty of displays that mess this up!) –  Mike Rosenblum Apr 23 '11 at 14:37
show 3 more comments

Think of an array index just as an offset from the start.

share|improve this answer
4  
That's the real reason. In languages like C the index of an array is actually kind of an offset. E.g. the offset is the index times the data type length. With 1-based arrays this would be much more complicated. –  EricSchaefer Apr 24 '11 at 6:56
    
Yes. I think C started with the mentality of an assembly programmer. And in assembly it was convenient to use a pointer to the adrress of the zeroth element, and add size times the index to that. –  Omega Centauri Apr 24 '11 at 15:55
2  
I think the main reason C was able to adopt and maintain this convention is that it did not have a marketing department. –  Mike Dunlavey Apr 24 '11 at 22:06
add comment

The difference is that it's not a human counting, it's the computer. It is easier for computers to think of 0 as the first item, as it is usually just an offset from the memory location. It's logical to start at 0000, then 0001, then 0010. If you started at 1, you would either lose available index (acting like 0000 isn't valid) or have awkwardness to make sure that the compiler always knows it should decrement the index by one before it actually works.

Plus it isn't that hard to pick up after your first programming class and you are told this is the way things work.

share|improve this answer
7  
It is easier for computers to think... - really??? Programming languages are designed for human comprehension first. A compiler can easily handle the detail of 1-based vs 0-based arrays. –  btilly Apr 23 '11 at 2:10
11  
@bitlly: 0-based indexes date back to when the extra decrement required to implement 1-based array lookup was a significant performance hit. –  Bevan Apr 23 '11 at 3:04
4  
@Bevan: Why would there be an extra decrement with 1-based array lookups? The trivial solution is of course to take the indexing into account in defining your base pointer, thus removing altogether any requirements for extra decrementation. –  Schedler Apr 23 '11 at 6:02
3  
@Schedler that only works if you know in advance what the pointer is going to be used for. Unfortunately, this only works when you have strong typing, which you don't really have in C or assembly language. Throw in the fact that you don't normaly have the luxury of keeping the base pointer around (due to lack of registers and/or stack space), and you end up with having to recalculate the address every time. –  Bevan Apr 23 '11 at 9:36
4  
@Bevan: Citation needed. Also please explain why FORTRAN, invented decades before any currently used 0-based language, managed to get away with 1-based array indexes. –  btilly Apr 24 '11 at 6:13
show 3 more comments

Dijkstra answered this very clearly in http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html - though Pascal programmers didn't agree.

share|improve this answer
9  
answered, yes. clearly, no. –  Steven A. Lowe Apr 23 '11 at 2:11
16  
I think Dijkstra's eplanation suits fine. The reason people get peeved at zero-based indices is that they count from 1 and feel that indexing should also start from 1. They fail to understand that indexing is not the same as counting. –  DPD Apr 23 '11 at 2:41
1  
+1, Dijkstra nailed it. –  Job Apr 23 '11 at 3:42
2  
Although it's rarely profitable to disagree with EWD, I reject his assumptions as well as his conclusions. In his example, I prefer C) much more than A). –  red-dirt Apr 23 '11 at 12:50
2  
@Mike: I disagree that [0, -1] is 100% clear. It definitely wasn't intuitive to one of my co-workers who wrote an HTTP server that needed to deal with empty ranges. –  dan04 Apr 23 '11 at 15:14
show 12 more comments

From a modern standpoint (i.e. interpreted languages or recently developed languages such as C#) this is likely due to developers and thus language designers learned to develop since languages such as C make use of zero indexed arrays. As to why languages have made use of the zero index for arrays, the index is due to how the array is stored. In C, the use of the array index array[1] is the same as using the pointer reference, i.e. array + 1. Wikipedia also has a bit more on the subject, but that is one reason in a nutshell.

share|improve this answer
add comment

In mathematics for centuries the subscript of a series has been chosen for convenience and meaning. For example in a polynomial, the coefficients are usually labelled a0, a1, a2, a3, etc. because the zero represents the power of the corresponding term. In computer science, the subscript represents the offset relative to the beginning of the array.

share|improve this answer
    
Yes, but that means in C you have to remember to dimension your coefficient array by n+1, which is oh so easy to forget. –  Omega Centauri Apr 24 '11 at 15:56
    
It helps to remember to index by the offset but allocate by the length. Alternatively the length is just the offset to the first unused element. –  Rick Sladkey Apr 24 '11 at 20:29
add comment

As has been pointed out, not all languages use 0-based indexing. For example in Ada you can define your indexing basis freely. For String type for example 1-based indexing is used.

The benefit of this is that you can define the indexing to best match the intended usage. In some cases it might sense to for example define the array bounds as -1..+1.

For example a symmetric 5x5 kernel for convolution could be defined as

type KernelT is array (-2..+2, -2..+2) of Real;

Similary enumerated types can be used directly for array indexing.

share|improve this answer
1  
I have seen this (ab)used to create some very unclear code (admittedly, in Algol 68 but the principle is the same). What was worse, the code looked clear at first glance; it was only when trying to convert into a different language that it became clear that things were obscure… –  Donal Fellows Apr 23 '11 at 14:32
add comment

The simple answer is zero is simpler when one tries to calculate the actual address in memory. If an array starts at location 12345 and you wish to access element 678 then adding the two gives the location that needs to be read. Note the above assumes the array holds bytes and is of course bigger than 678. If you used 1 based indexing then an additional subtract 1 would be required. This quickly becomes a pain andall things said 1 does not really buy anything.

share|improve this answer
add comment

I see two reasons:

The low level one. If you start with 0, than the pointer element indicated by index is pointer of array + index (a[i] and a + i point to the same memory address). This is very convenient.

On a bit higher level of abstraction -- very often you will have to use modulo function for indices. Modulo n always returns values from 0 to n-1. So it's also more convenient when indices start with 0.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.