Is value of variable always negative in case of overflow

Question

It tried to solve this problem, given N,K amd M, find maximum integer T such that N*(K^T) <= M. N,K and M can be the values to 10^18. So long long is sufficient. I tried to solve it using iteration on T

int T = 0;
long long Kpow = 1;
while(1)
{
  long long prod = N*Kpow;
  if(prod > M)
    break;
  T++;
  Kpow = Kpow*K;
}

But since N*Kpow may go out of range of long long, there is need to handle the product using some big integer. But I found some other code which smartly handles this case

long long prod = N*Kpow;
if(prod < 0)
  break;

Even I have seen always, that in overflow, the value of variable becomes negative. Is it always the case or sometimes even positive values also occur in overflow case?

Answer 1

From the point of view of the language, the behaviour of signed integer overflow is undefined. Which means anythign could happen - it can be negative, it can be unchanged, the program can crash or it can order pizza online.

What will most likely happen in practice depends on the processor architecture on which you're running - so you'd have to consult the platform specs to know.

But I'd guess you can't guarantee overflow to be negative. As a contrived example:

signed char c = 127;
c += 255;
std::cout << (int)c << '\n';

This happens to print 126 on x86. But again, it could actually do anything.

Answer 2

No. The value of variable is not always negative in case of overflow.

With signed integers, C11dr §3.7.1 3 undefined behavior "An example of undefined behavior is the behavior on integer overflow." so there is no test to do after overflow that is certain to work across compilers and platforms.

Detect potential overflow before it can happen.

int T = 0;
long long Kpow = 1;
long long Kpow_Max = LLONG_MAX/K;
long long prod_Max = LLONG_MAX/N;

while(1)
{
  if (Kpow > prod_Max) Handle_Overflow();
  long long prod = N*Kpow;
  if(prod > M)
    break;
  T++;
  if (Kpow > Kpow_Max) Handle_Overflow();
  Kpow = Kpow*K;
}

Answer 3

Couldn't this problem be converted to K^T <= (M + N - 1) / N?

As far as overflow detection goes, normally addition and subtraction are performed as if the numbers were unsigned, with the overflow bit set based on signed math, and the carry / borrow bit set based on unsigned math. For multiplication, the low order of the result is the same for signed or unsigned multiply (this is why the ARM cpu only has a signed / unsigned multiply for 64 bit results from 32 bit operands). Overflow occurs if the product is too large to fit in the register that receives the product, like a 32 bit multiply that results in a 39 bit product, that is supposed to go into a 32 bit register. For divide, overflow can occur if the divisor is zero or if the quotient is too large to fit in the register that receives the quotient, for example a 64 bit dividend divided by a 32 bit divisor, resulting in a 40 bit quotient. For multiply and divide, it doesn't matter if the operands are signed or not, only if the size of the result will fit in the register that receives the result.

Answer 4

Just as in any other situation with signed integers of any length...overflow makes the number negative if and only if the specific bit which is overflowed into the sign bit is on.

Meaning if the result of your arithmetic would give you an overflow which, if you were to double the length of your variable word, would leave your current sign bit as off, you could quite possibly come up with an erroneous result which is positive.