1

I came across this snippet in a book about Computer Organization

Treating signed numbers as if they were unsigned gives us a low cost way of checking if 0 ≤ x < y, which matches the index out-of-bounds check for arrays. The key is that negative integers in two's complement notation look like large numbers in unsigned notation; that is, the most significant bit is a sign bit in the former notation but a large part of the number in the latter. Thus, an unsigned comparison of x < y also checks if x is negative as well as if x is less than y.

As an example of this, let's say we have registers $t0, $t2 and $s1 want to jump to an instruction IndexOutOfBounds if $s1 ≥ $t2 or if $s1 is negative.

This can be done using the MIPS instructions

sltu $t0,$s1,$t2
beq $t0,$zero,IndexOutOfBounds

Why does this work?

evianpring
  • 3,316
  • 1
  • 25
  • 54
  • the quote already explained that. It's a common optimization that all modern compilers do. And there are many questions on SO explaining that too: [Fastest way to determine if an integer is between two integers (inclusive) with known sets of values](https://stackoverflow.com/a/17095534/995714), [Could type punning signed to unsigned integers make bounds checking faster by eliminating the need for >= comparison?](https://stackoverflow.com/q/28016931/995714) – phuclv Dec 20 '19 at 13:26

1 Answers1

1

As fas as I can tell, it is explained in the box you quote.

Signed integers use the most significant bit (MSB) as the sign bit, hence when converted to unsigned they will have at least the MSB set, which will make them quite large numbers.

Let's say we are talking about 32 bit integers, then -1 signed is the same as 1 << 31 unsigned (which is 2147483648). The largest unsigned 32-bit value is (1 << 32) -1 which is 4294967295.

Assuming the unsigned value of y is less than 2147483648, this will work as an array index bounds check.

I guess the "trick" here is to just assume that arrays can't hold 2147483648 elements or more.

edit: see OPs comment below which explains the trick correctly.

Morten Jensen
  • 5,818
  • 3
  • 43
  • 55
  • 2
    I think I understand now: when you want to check that x is inbounds (not negative, smaller than y), doing an unsigned comparison of x and y kills two birds with one stone, ie it only succeeds if x abides by both the inbounds conditions. The reason for this is that we are assuming x and y are actually signed. So the MSB bit of y is 0; therefore, any negative number will be larger than y in an unsigned comparison (because MSB is 1). Also, if x is a non-negative number, then it will only pass the comparison if it is in fact smaller than y. – evianpring Dec 20 '19 at 22:23