Of all the ways in which a number can be wrong, being off by one is the most common. Usually, the cause is some subtle logic error, a miscounting. Gross errors tend to get noticed and fixed more quickly. Off by ones are certainly common enough to deserve special attention during testing.
I've found the best way to counter them is formal reasoning, especially loop invariants and induction proofs. Suppose you need some function of N, which you expect to be a simple arithmetic progression. Think what the answer is when N=0. Think again when N=1. Often, that's enough for you to get the code right. (It's worth trying N=100, or some such extreme value, as a check.)
See also:
FencePostError and
SourcesOfBugs
--
DaveHarris
Graphical Programming
This problem also occurs in graphical programming while specifying coordinates. For example, when you draw a line you have two alternatives:
- drawLine(left, top, right, bottom)
- drawLine(left, top, width, height)
what's the width of this line? In the first case, it's right-left+1.
Where does this line end? In the second case, it's left+width-1.
Of course, it'll be much more complicated in complex situations.
--
SavasAlparslan
Avoiding OffByOne Errors by Using Collections
Most of my
OffByOne errors seem to have disappeared. I suspect it's because most iterations are done to process collections of things, and in languages supporting iterators directly over collections, you always get the right number of iterations. I rarely write a loop over a set of integers ... and when counting things it's easy to remember to init to zero. --
RonJeffries
My
OffByOne errors vanished in 1984-85 when I encountered the book
TheScienceOfProgramming by Gries (the compiler textbook author). He had taken Dijkstra's (
EwDijkstra) program derivation to its next level and showed how to
derive programs (see
BinarySearch for an example). I tried his ideas, and found it was quicker to derive my code than to debug it, and all the
OffByOne errors went away. All I was left with were "didn't read the manual errors" (of which there were many).
When I switched from C to Smalltalk, they didn't come back, although I stopped deriving. The reason seems to be what
RonJeffries said - most of the
OffByOne situations are absent given the Collection classes and iterators. Many of the reasons for using
TheScienceOfProgramming have gone away, I reserve it for converting recursion to iteration (and avoiding
OffByOne errors there). --
AlistairCockburn
And before collections, array languages (APL), which apply functions and operators to data with little regard to the size, shape, or dimensions of the arguments, make it difficult to trip over
OffByOne problems. But it does make it obvious how much time programming scalar languages is wasted by creating, setting up, and testing loops. --
JimRussell
I always use
for loops with the following structure:
for (i=0; i<count; i++) ...
Since all
for loops are the same,
OffByOne errors don't occur and the coding is quick and easy.
For cases that don't involve looping, such as string manipulation, I try a small value and convince myself that the result is correct. --
JaredLevy
More on this on
FencePostError (maybe that content should be moved back here).
I always try to picture the way I would do the task manually, then base the loop on that.
This also helps dealing with border effects like initializing the loop, and detecting when it's reached its end.
-- MichaelH
Not to be confused with:
OffByOneWebBrowser
CategoryBug