Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is it safe to shift 1-based numbering to 0-based numbering by subtracting 1 if unsigned integers are used?

Tags:

c++

c

In a system I am maintaining, users request elements from a collection from a 1-based indexing scheme. Values are stored in 0-based arrays in C++ / C.

Is the following hypothetical code portable if 0 is erroneously entered as the input to this function? Is there a better way to validate the user's input when converting 1-based numbering schemes to 0-based?

const unsigned int arraySize;
SomeType array[arraySize];    

SomeType GetFromArray( unsigned int oneBasedIndex )
{
  unsigned int zeroBasedIndex = oneBasedIndex - 1;

  //Intent is to check for a valid index.
  if( zeroBasedIndex < arraySize )
  {
    return array[zeroBasedIndex];
  }

  //else... handle the error
}

My assumption is that (unsigned int)( 0 - 1 ) is always greater than arraySize; is this true?

The alternative, as some have suggested in their answers below, is to check oneBasedIndex and ensure that it is greater than 0:

const unsigned int arraySize;
SomeType array[arraySize];    

SomeType GetFromArray( unsigned int oneBasedIndex )
{
  if( oneBasedIndex > 0 && oneBasedIndex <= arraySize )
  {
    return array[oneBasedIndex - 1];
  }

  //else... handle the error
}
like image 600
Kaiged Avatar asked Dec 06 '22 15:12

Kaiged


2 Answers

For unsigned types, 0-1 is the maximum value for that type, so it's always >= arraySize. In other words, yes that is absolutely safe.

like image 103
Daniel Fischer Avatar answered Feb 22 '23 23:02

Daniel Fischer


Unsigned integers never overflow in C++ and in C.

For C++ language:

(C++11, 3.9.1p4) "Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer. 46)"

and footnote 46):

"46) This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type."

and for C language:

(C11, 6.2.5p9) "A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type."

like image 44
ouah Avatar answered Feb 23 '23 00:02

ouah