2

I have a function that takes a string as input, and then assigns a product of weighted values to a variable, in the following manner: every letter of the alphabet corresponds to a prime number between 2 and 101, and the value for every character in the input string is multiplied and stored in an int variable, like so:

int result=1;
/* some other code */
result*=letterweight[index];

There are sufficiently long strings that cause an overflow. My question, then, is the following:

How can I determine the possible correct values, given a result?

For instance: if result == 1066849907, what other value could result have had, neglecting the values range of int in C?

I do not have control of the original code and cannot determine if an overflow occurred. I am only interested in finding out the series of possible results, however big the numbers might be.

user3002111
  • 21
  • 1

2 Answers2

5

Signed integer overflow (in C as well as C++) results in undefined behavior, so you cannot reason about your code in this way. You can only test your specific compiler/version and see what it produces.

However, this is a horrible way to write code and will bite you in the future. Your proposal is not a solution. How about pre-processing the data and removing values which would cause overflow?

Ed S.
  • 122,712
  • 22
  • 185
  • 265
1

Signed integer overflow - unlike unsigned integer overflow - is undefined behaviour in C and C++ (see this response).

If you make the arithmetic unsigned int however, the standard guarantees modulo 2 arithmetic, in other words, the range of possible, real values is result + 2^(sizeof(unsigned int) * 8) * a for any a.

Community
  • 1
  • 1
Alexander Gessler
  • 45,603
  • 7
  • 82
  • 122
  • The set described in this answer is not the set of possible values; it includes some that are not possible. As Dukeling noted, any number with a prime factor greater than 101 is not possible. (Additionally, the multiplier should be `CHAR_BIT` rather than 8.) – Eric Postpischil Nov 17 '13 at 17:43
  • 2
    The range of possible values you quoted is incorrect: There is no guarantee that `char` uses 8 bit. The correct upper bound is `std::numeric_limits::max()` which will be some power of 2. – Dietmar Kühl Nov 17 '13 at 17:46