Velocity Reviews > Java > I thought that array bounds checking needed two comparisons; however, ...

# I thought that array bounds checking needed two comparisons; however, ...

Casey Hawthorne
Guest
Posts: n/a

 06-04-2004
I thought that array bounds checking needed two comparisons; however,
I see bounds checking can be done with one comparison:

n - number of array items -- indexed from 0 to n-1

to see if 0 <= i < n do the following comparison

if (i < n) then inbounds;

where '<' is an unsigned '<'

from "Hacker's Delight" Henry S. Warren, Jr. page 51

--
Regards,
Casey

Thomas Weidenfeller
Guest
Posts: n/a

 06-04-2004
Casey Hawthorne wrote:
> I thought that array bounds checking needed two comparisons; however,
> I see bounds checking can be done with one comparison:
>
> n - number of array items -- indexed from 0 to n-1
>
> to see if 0 <= i < n do the following comparison
>
> if (i < n) then inbounds;
>
> where '<' is an unsigned '<'

Only that there are no unsigned integral types and no corresponding
operators in Java. Better luck next time.

/Thomas

Andy Fish
Guest
Posts: n/a

 06-04-2004

"Thomas Weidenfeller" <(E-Mail Removed)> wrote in message
news:c9pcoj\$l3s\$(E-Mail Removed)...
> Casey Hawthorne wrote:
> > I thought that array bounds checking needed two comparisons; however,
> > I see bounds checking can be done with one comparison:
> >
> > n - number of array items -- indexed from 0 to n-1
> >
> > to see if 0 <= i < n do the following comparison
> >
> > if (i < n) then inbounds;
> >
> > where '<' is an unsigned '<'

>
> Only that there are no unsigned integral types and no corresponding
> operators in Java. Better luck next time.
>

if the bounds of the array are H and L, simply check that

abs (i - ( (H+L)/2) ) <= (H-L)/2

)

n.b. I haven't tested it - it might not work for odd numbers or not even
numbers (or not either)

Andy

> /Thomas

Michael Borgwardt
Guest
Posts: n/a

 06-04-2004
Thomas Weidenfeller wrote:

> Only that there are no unsigned integral types and no corresponding
> operators in Java. Better luck next time.

Only that array bounds checking is done by the JVM, which is
*not* written in Java.

Thomas Weidenfeller
Guest
Posts: n/a

 06-04-2004
Michael Borgwardt wrote:
> Only that array bounds checking is done by the JVM, which is
> *not* written in Java.

Congratulations if you never ever had the need to check an index against
an array size in your own code. Oh, you use exceptions exclusively for
that? Ah well, ...

/Thomas

Roedy Green
Guest
Posts: n/a

 06-04-2004
On Fri, 04 Jun 2004 10:46:21 +0200, Thomas Weidenfeller
<(E-Mail Removed)> wrote or quoted :

>Only that there are no unsigned integral types and no corresponding
>operators in Java. Better luck next time.

But that does not mean a JVM cannot use the unsigned compares of the
underlying machine hardware to do the bounds checking.

The bounds checking is neither written in Java nor in byte code. It is
a side effect of various JVM instructions.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Roedy Green
Guest
Posts: n/a

 06-04-2004
On Fri, 04 Jun 2004 11:40:50 GMT, "Andy Fish"
<(E-Mail Removed)> wrote or quoted :

>if the bounds of the array are H and L, simply check that

In Java L is always 0.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Michael Borgwardt
Guest
Posts: n/a

 06-04-2004
Thomas Weidenfeller wrote:

> Congratulations if you never ever had the need to check an index against
> an array size in your own code. Oh, you use exceptions exclusively for
> that?

Indeed I cannot remember any code where such a condition would not have
resulted from a bug in the code.

Andy Fish
Guest
Posts: n/a

 06-04-2004

"Roedy Green" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Fri, 04 Jun 2004 11:40:50 GMT, "Andy Fish"
> <(E-Mail Removed)> wrote or quoted :
>
> >if the bounds of the array are H and L, simply check that

>
> In Java L is always 0.
>

But a good mathematician would never quote a result over a narrower range
than he new it to be true - that would be a waste of maths

> --
> Canadian Mind Products, Roedy Green.
> Coaching, problem solving, economical contract programming.
> See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Roedy Green
Guest
Posts: n/a

 06-04-2004
On Fri, 04 Jun 2004 14:19:50 +0200, Thomas Weidenfeller
<(E-Mail Removed)> wrote or quoted :

>Congratulations if you never ever had the need to check an index against
>an array size in your own code. Oh, you use exceptions exclusively for
>that? Ah well, ...

In your own code you don't worry about the negative case. If that has
happened, something is REALLY wrong. Overflowing the other way is a
check, for example, that ArrayList does all the time explicitly.

The JVM of course has to worry about the negative case too since it
can't trust the programmer at all. There, it can use an unsigned
machine language compare to effectively pull off the lower and upper
bounds check in one go. Sometimes it might do it with a built in
hardware instruction that does the bounds check.

The important thing to understand is that the bounds checking that
triggers ArrayIndexOutOfBounds exceptions is not written in explicit
Java or byte codes, so it is not subject to those limitations.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.