445,849 Members | 2,164 Online Need help? Post your question and get tips & solutions from a community of 445,849 IT Pros & Developers. It's quick & easy.

# integer multiplication

 P: n/a What happens if you multiple two integers and the result overflows the MAX_INT in C? Is there a way to trap the condition when it happens? Mar 10 '07 #1
31 Replies

 P: n/a Pesso wrote: What happens if you multiple two integers and the result overflows the MAX_INT in C? Behaviour when signed integers overflow is implementation dependant. Unsigned integers do not overflow, but exhibit "wrap-around" behaviour according to modulo 2^n arithmetic. Is there a way to trap the condition when it happens? You'll have to see your implementation's documentation for this. The Standard doesn't insist on a trap. Note though, that you can easily check if a particular operation will cause overflow or wrap-around before attempting it. It's tedious, but it can be done. Mar 10 '07 #2

 P: n/a santosh wrote: Pesso wrote: What happens if you multiple two integers and the result overflows the MAX_INT in C? Behaviour when signed integers overflow is implementation dependant. [ ... ] Sorry, it's actually undefined behaviour, according to the Standard. Mar 10 '07 #3

 P: n/a Pesso said: What happens if you multiple two integers and the result overflows the MAX_INT in C? Assuming you mean ints and INT_MAX, the behaviour is undefined. Is there a way to trap the condition when it happens? Not portably, no. The proper technique is not to let it happen in the first place. It's easy enough to avoid. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Mar 10 '07 #4

 P: n/a Richard Heathfield What happens if you multiple two integers and the result overflows theMAX_INT in C? Assuming you mean ints and INT_MAX, the behaviour is undefined. >Is there a way to trap the condition when it happens? Not portably, no. The proper technique is not to let it happen in the first place. It's easy enough to avoid. I wouldn't call it easy in general, unless you know some trick that I'm not familiar with. For example, it's certainly possible to implement a function like this: int safe_multiply(int x, int y, int *overflow) { if (/* multiplication would overflow */) { *overflow = 1; return INT_MAX; /* or whatever */ } else { *overflow = 0; return x * y; } } but the condition is non-trivial, it's likely to be more computationally expensive than the multiplication itself, and using this function in place of the "*" operator makes your code more difficult to write and to read, especially if you're doing a lot of multiplications. You can *sometimes* write your code in a way that just avoids multiplications that would overflow, but that's very application-specific and not always feasible. Many CPUs set a condition code on overflow, but C doesn't provide a way to get at it. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Mar 10 '07 #5

 P: n/a "Keith Thompson" Not portably, no. The proper technique is not to let it happen in thefirst place. It's easy enough to avoid. I wouldn't call it easy in general, unless you know some trick that I'm not familiar with. For example, it's certainly possible to implement a function like this: int safe_multiply(int x, int y, int *overflow) { if (/* multiplication would overflow */) { *overflow = 1; return INT_MAX; /* or whatever */ } else { *overflow = 0; return x * y; } } but the condition is non-trivial, it's likely to be more computationally expensive than the multiplication itself, and using this function in place of the "*" operator makes your code more difficult to write and to read, especially if you're doing a lot of multiplications. The obvious strategy of if(x * y < INT_MAX) has a fatal flaw as far as C is concerned. However you can cast to double if ((double) x * y < INT_MAX) that begs the question of why not use doubles for everything and solve the problem that way. You can *sometimes* write your code in a way that just avoids multiplications that would overflow, but that's very application-specific and not always feasible. Many CPUs set a condition code on overflow, but C doesn't provide a way to get at it. The OPs question seemed to be whether it was possible to intecerpt the error handler, for instance to print out a "hey man, these images are way too big. On strike chum." message rather than just crash with a crytic compaint about mathematical exceptions. It is perfectly reasonable thing to ask, but in fact you can't, certainly not in ANSI C. Even if you know your platform it is a difficult fiddly thing to do - in DOS you used to be able to chain on to the interrupt handlers, but those salad days are long gone. Of course if ints are 64 bits then 99% of the time you can sanity check very easily. -- Free games and programming goodies. http://www.personal.leeds.ac.uk/~bgy1mm Mar 10 '07 #6

 P: n/a Malcolm McLean wrote: "Keith Thompson" >Not portably, no. The proper technique is not to let it happen in thefirst place. It's easy enough to avoid. I wouldn't call it easy in general, unless you know some trick thatI'm not familiar with. The obvious strategy of if(x * y < INT_MAX) has a fatal flaw as far as C is concerned. However you can cast to double if ((double) x * y < INT_MAX) that begs the question of why not use doubles for everything and solve the problem that way. I think that it's better to use integer types rather than doubles if you care about precission. You can use x >You can *sometimes* write your code in a way that just avoidsmultiplications that would overflow, but that's veryapplication-specific and not always feasible.Many CPUs set a condition code on overflow, but C doesn't provide away to get at it. The OPs question seemed to be whether it was possible to intecerpt the error handler, for instance to print out a "hey man, these images are way too big. For image sizes you'd use unsigned integers which is easier and faster to handle. On strike chum." message rather than just crash with a crytic compaint about mathematical exceptions. It is perfectly reasonable thing to ask, but in fact you can't, certainly not in ANSI C. Even if you know your platform it is a difficult fiddly thing to do - in DOS you used to be able to chain on to the interrupt handlers, but those salad days are long gone. Of course if ints are 64 bits then 99% of the time you can sanity check very easily. What do you mean? -- Ioan - Ciprian Tandau tandau _at_ freeshell _dot_ org (hope it's not too late) (... and that it still works...) Mar 10 '07 #7

 P: n/a Malcolm McLean wrote: "Keith Thompson" >For example, it's certainly possible to implement a function likethis: .... snip ... >>but the condition is non-trivial, it's likely to be morecomputationally expensive than the multiplication itself, and usingthis function in place of the "*" operator makes your code moredifficult to write and to read, especially if you're doing a lot ofmultiplications. The obvious strategy of if(x * y < INT_MAX) has a fatal flaw as far as C is concerned. However you can cast to double if ((double) x * y < INT_MAX) Just use: if ((INT_MAX / x) < y) ans = x * y; else overflow(__LINE__, __FILE__); It is unfortunate that compilers don't normally implement a trap on integer overflow, so without taking care you can get nonsense results. -- "A man who is right every time is not likely to do very much." -- Francis Crick, co-discover of DNA "There is nothing more amazing than stupidity in action." -- Thomas Matthews -- Posted via a free Usenet account from http://www.teranews.com Mar 11 '07 #8

 P: n/a CBFalconer With recent GCC versions you can use -ftrapv to get a trap on integer overflow. -- Peter Seebach on C99: "[F]or the most part, features were added, not removed. This sounds great until you try to carry a full-sized printout of the standard around for a day." Mar 11 '07 #9

 P: n/a CBFalconer wrote: Malcolm McLean wrote: >"Keith Thompson" >For example, it's certainly possible to implement a function likethis: ... snip ... >>but the condition is non-trivial, it's likely to be morecomputationally expensive than the multiplication itself, and usingthis function in place of the "*" operator makes your code moredifficult to write and to read, especially if you're doing a lot ofmultiplications. The obvious strategy of if(x * y < INT_MAX)has a fatal flaw as far as C is concerned.However you can cast to double if ((double) x * y < INT_MAX) Just use: if ((INT_MAX / x) < y) ans = x * y; else overflow(__LINE__, __FILE__); Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won't work for long int on many popular implementations, not just on DS09876). Yevgen Mar 11 '07 #10

 P: n/a Yevgen Muntyan wrote: CBFalconer wrote: >Malcolm McLean wrote: >>"Keith Thompson" >>For example, it's certainly possible to implement a function likethis: ... snip ... >>>but the condition is non-trivial, it's likely to be morecomputationally expensive than the multiplication itself, and usingthis function in place of the "*" operator makes your code moredifficult to write and to read, especially if you're doing a lot ofmultiplications.The obvious strategy of if(x * y < INT_MAX)has a fatal flaw as far as C is concerned.However you can cast to double if ((double) x * y < INT_MAX) Just use: if ((INT_MAX / x) < y) ans = x * y; else overflow(__LINE__, __FILE__); Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won't work for long int on many popular implementations, not just on DS09876). For pedants: "won't work" is clearly false; it will work but will falsely claim overflow for some pairs x,y if INT_MAX isn't a prime integer. Furthermore, if x and y are negative, then inequality should be reversed, i.e. it should be something like INT_MAX / ABS(x) < ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0) to detect whether x*y <= INT_MAX in normal arithmetic (INT_MIN would require one more thing like this). I wonder what I missed here. Yevgen Mar 11 '07 #11

 P: n/a Yevgen Muntyan wrote: Yevgen Muntyan wrote: >CBFalconer wrote: >>Malcolm McLean wrote:"Keith Thompson" ... snip ...but the condition is non-trivial, it's likely to be morecomputationally expensive than the multiplication itself, and usingthis function in place of the "*" operator makes your code moredifficult to write and to read, especially if you're doing a lot ofmultiplications.The obvious strategy of if(x * y < INT_MAX)has a fatal flaw as far as C is concerned.However you can cast to double if ((double) x * y < INT_MAX)Just use: if ((INT_MAX / x) < y) ans = x * y; else overflow(__LINE__, __FILE__); Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won'twork for long int on many popular implementations, not just on DS09876). For pedants: "won't work" is clearly false; it will work but will falsely claim overflow for some pairs x,y if INT_MAX isn't a prime integer. And of course 1 * INT_MAX == INT_MAX. Yevgen Mar 11 '07 #12

 P: n/a Ben Pfaff wrote: CBFalconer It is unfortunate that compilers don't normally implement a trap oninteger overflow, so without taking care you can get nonsenseresults. With recent GCC versions you can use -ftrapv to get a trap on integer overflow. I'm still using 3.2.1, but I might install 4.1 shortly. I thought that didn't work for x86 code. -- "A man who is right every time is not likely to do very much." -- Francis Crick, co-discover of DNA "There is nothing more amazing than stupidity in action." -- Thomas Matthews -- Posted via a free Usenet account from http://www.teranews.com Mar 11 '07 #13

 P: n/a Yevgen Muntyan wrote: Yevgen Muntyan wrote: >CBFalconer wrote: >>Malcolm McLean wrote:"Keith Thompson" ... snip ...but the condition is non-trivial, it's likely to be morecomputationally expensive than the multiplication itself, and usingthis function in place of the "*" operator makes your code moredifficult to write and to read, especially if you're doing a lot ofmultiplications.The obvious strategy of if(x * y < INT_MAX)has a fatal flaw as far as C is concerned.However you can cast to double if ((double) x * y < INT_MAX)Just use: if ((INT_MAX / x) < y) ans = x * y; else overflow(__LINE__, __FILE__); Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won'twork for long int on many popular implementations, not just onDS09876). For pedants: "won't work" is clearly false; it will work but will falsely claim overflow for some pairs x,y if INT_MAX isn't a prime integer. Furthermore, if x and y are negative, then inequality should be reversed, i.e. it should be something like There are actually three cases to worry about. 0, 1, or 2 operands negative. 0 is already handled, 1 requires use of INT_MIN, and 2 requires comparison reversal. All barring the equality condition you brought up above. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. -- Posted via a free Usenet account from http://www.teranews.com Mar 11 '07 #14

 P: n/a Yevgen Muntyan wrote: Yevgen Muntyan wrote: >CBFalconer wrote: >>Malcolm McLean wrote:"Keith Thompson" ... snip ...but the condition is non-trivial, it's likely to be morecomputationally expensive than the multiplication itself, and usingthis function in place of the "*" operator makes your code moredifficult to write and to read, especially if you're doing a lot ofmultiplications.The obvious strategy of if(x * y < INT_MAX)has a fatal flaw as far as C is concerned.However you can cast to double if ((double) x * y < INT_MAX)Just use: if ((INT_MAX / x) < y) ans = x * y; else overflow(__LINE__, __FILE__); Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won'twork for long int on many popular implementations, not just on DS09876). For pedants: "won't work" is clearly false; It's actually clearly true. The inequality should be reversed. Full version, to check both top and bottom: x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (INT_MAX / ABS(x) ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) || ((x 0 && y < 0 || x < 0 && y 0) && ((-INT_MIN) / ABS(x) ABS(y) || ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0))); I wonder if there is simple portable one-expression form of it. Yevgen Mar 11 '07 #15

 P: n/a CBFalconer wrote: Yevgen Muntyan wrote: >Yevgen Muntyan wrote: >>CBFalconer wrote:Malcolm McLean wrote:"Keith Thompson" ... snip ...>For example, it's certainly possible to implement a function like>this:>>... snip ...>but the condition is non-trivial, it's likely to be more>computationally expensive than the multiplication itself, and using>this function in place of the "*" operator makes your code more>difficult to write and to read, especially if you're doing a lot of>multiplications.The obvious strategy of> if(x * y < INT_MAX)>has a fatal flaw as far as C is concerned.However you can cast to double if ((double) x * y < INT_MAX)Just use: if ((INT_MAX / x) < y) ans = x * y; else overflow(__LINE__, __FILE__);Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won'twork for long int on many popular implementations, not just onDS09876). For pedants: "won't work" is clearly false; it will work but willfalsely claim overflow for some pairs x,y if INT_MAX isn't a primeinteger.Furthermore, if x and y are negative, then inequality should bereversed, i.e. it should be something like There are actually three cases to worry about. 0, 1, or 2 operands negative. 0 is already handled, 1 requires use of INT_MIN, and 2 requires comparison reversal. All barring the equality condition you brought up above. Well, I talked about checking whether x*y INT_MAX (snipped text: "to detect whether x*y <= INT_MAX in normal arithmetic"). Case of 1 negative operand is not interesting: product is always less than INT_MAX. But there is fourth case: x == 0 :) Yevgen Mar 11 '07 #16

 P: n/a "Nelu" >Of course if ints are 64 bits then 99% of the time you can sanity checkvery easily. What do you mean? Numbers represent something. Let's say we want to multiply the number of employees by the number of products we sell. Both of these numbers are probably in the low thousands if not low hundreds. However a big company might have more than 64,000 employees and a few companies, like retailers, might offer more than 64,000 products. On the other hand a supermarket, with lots of employees and lots of products, probably wouldn't want to do the calculation if, for instance, we want to create a matrix of each employee's contribution to each product. It simply doesn't make sense in supermarket business model terms. So we know that 32 bits for the result is safe. So we cannot quite sanity test by saying that if(employees 64000 || products 64000) bail(); However no company is going to have 4 billion employees, or offer 4 billion different products. So we can easily sanity test, and know that the result will never overflow 64 bits. -- Free games and programming goodies. http://www.personal.leeds.ac.uk/~bgy1mm Mar 11 '07 #17

 P: n/a Malcolm McLean wrote: "Nelu" However no company is going to have 4 billion employees, or offer 4 billion different products. So we can easily sanity test, and know that the result will never overflow 64 bits. Yes, that's the real issue. If you've chosen the appropriate data type beforehand, for a particular calculation, then overflow shouldn't occur except as a result of a bug or bad input. The former can be corrected by compile-time checking and debugging while the latter can be avoided by validating all input before using them. Mar 11 '07 #18

 P: n/a On Mar 11, 7:04 pm, Yevgen Muntyan wrote: > x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (INT_MAX / ABS(x) ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) || ((x 0 && y < 0 || x < 0 && y 0) && ((-INT_MIN) / ABS(x) ABS(y) || ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0))); I wonder if there is simple portable one-expression form of it. What is the purpose of the (INT_MAX % ABS(x) == 0) expression? If INT_MAX / x == y (with x 0) then x*y will be less than or equal to INT_MAX so there is no overflow. Mar 11 '07 #19

 P: n/a Old Wolf wrote: On Mar 11, 7:04 pm, Yevgen Muntyan wrote: > x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (INT_MAX / ABS(x) ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) || ((x 0 && y < 0 || x < 0 && y 0) && ((-INT_MIN) / ABS(x) ABS(y) || ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));I wonder if there is simple portable one-expression form of it. What is the purpose of the (INT_MAX % ABS(x) == 0) expression? If INT_MAX / x == y (with x 0) then x*y will be less than or equal to INT_MAX so there is no overflow. No purpose, I was fooled by the initial wrong 'INT_MAX / x < y' condition. So, it's gonna be x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) || ((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y)) Is this one right? Yevgen Mar 12 '07 #20

 P: n/a On Mar 12, 3:56 pm, Yevgen Muntyan wrote: > x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) || ((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y)) Is this one right? No, (-INT_MIN) causes an integer overflow. You have to use INT_MIN and negate the divisor (and get the inequality direction right). I would eschew the differentiation between INT_MIN and INT_MAX, unless the code really did need to use INT_MIN as a valid value: (x == 0) || (INT_MAX / ABS(x) ABS(y)) Is there any way to implement ABS without evaluating the argument twice? If not then I would make this an inline function. Here's another way: STATIC_ASSERT( sizeof(long long) >= 2 * sizeof(int) ) ( 1LL * x * y <= INT_MAX && 1LL * x * y >= INT_MIN ) I wonder if any compiler would optimize: if ( 1LL * ........ ) x *= y; else /* error handling */ to do a multiplication followed by an overflow check (obv for CPUs which can overflow a multiplication and not trap). Mar 12 '07 #21

 P: n/a Yevgen Muntyan wrote: Old Wolf wrote: >On Mar 11, 7:04 pm, Yevgen Muntyan wrote: >> x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (INT_MAX / ABS(x) ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) || ((x 0 && y < 0 || x < 0 && y 0) && ((-INT_MIN) / ABS(x) ABS(y) || ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));I wonder if there is simple portable one-expression form of it. What is the purpose of the (INT_MAX % ABS(x) == 0) expression?If INT_MAX / x == y (with x 0) then x*y will be less than orequal to INT_MAX so there is no overflow. No purpose, I was fooled by the initial wrong 'INT_MAX / x < y' condition. So, it's gonna be x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) || ((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y)) Is this one right? If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 then ABS(x) cannot be represented. -- Ioan - Ciprian Tandau tandau _at_ freeshell _dot_ org (hope it's not too late) (... and that it still works...) Mar 12 '07 #22

 P: n/a Old Wolf wrote: On Mar 12, 3:56 pm, Yevgen Muntyan wrote: >x == 0 ||((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) ||((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y))Is this one right? No, (-INT_MIN) causes an integer overflow. You have to use INT_MIN and negate the divisor (and get the inequality direction right). Good point. So it's even worse than what you said, since you can't safely negate an operand here. I would eschew the differentiation between INT_MIN and INT_MAX, unless the code really did need to use INT_MIN as a valid value: (x == 0) || (INT_MAX / ABS(x) ABS(y)) Here you also ignore x*y == INT_MAX. I have no idea if one ever needs this case, but I tried to make it correct, hence the distinction between INT_MIN and INT_MAX. Is there any way to implement ABS without evaluating the argument twice? If not then I would make this an inline function. This is not important, ABS may be a macro or a function, I used it because (hopefully) everybody understands what it means. Say, if I used some SIGN thing (which would be nicer here, IMO), it'd immediately provoke a question about SIGN(0). Here's another way: STATIC_ASSERT( sizeof(long long) >= 2 * sizeof(int) ) ( 1LL * x * y <= INT_MAX && 1LL * x * y >= INT_MIN ) Breaks on windows; and won't work if you want to detect overflow in long long multiplication. I'd think a production macro/function would likely use bit fiddling or something, i.e. be non-portable. The point of my exercise was to make something portable and correct. Another point was that it's not as simple as if (INT_MAX / ABS(x) < ABS(y)) { /* no overflow here */ } :) I wonder if any compiler would optimize: if ( 1LL * ........ ) x *= y; else /* error handling */ to do a multiplication followed by an overflow check (obv for CPUs which can overflow a multiplication and not trap). It would need to be a very smart compiler probably :) Yevgen Mar 12 '07 #23

 P: n/a Nelu wrote: Yevgen Muntyan wrote: >Old Wolf wrote: >>On Mar 11, 7:04 pm, Yevgen Muntyan wrote: x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (INT_MAX / ABS(x) ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) || ((x 0 && y < 0 || x < 0 && y 0) && ((-INT_MIN) / ABS(x) ABS(y) || ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));I wonder if there is simple portable one-expression form of it.What is the purpose of the (INT_MAX % ABS(x) == 0) expression?If INT_MAX / x == y (with x 0) then x*y will be less than orequal to INT_MAX so there is no overflow. No purpose, I was fooled by the initial wrong 'INT_MAX / x < y'condition. So, it's gonna bex == 0 ||((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) ||((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y))Is this one right? If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 then ABS(x) cannot be represented. Yeah, as well as (-INT_MIN). x == 0 || (x 0 && y >= 0 && INT_MAX / x >= y) || (x < 0 && y <= 0 && INT_MAX / x <= y) || (x < 0 && INT_MIN / x >= y) || (x 0 && INT_MIN / y >= x) Yevgen Mar 12 '07 #24

 P: n/a Yevgen Muntyan wrote: Nelu wrote: >Yevgen Muntyan wrote: >>Old Wolf wrote:On Mar 11, 7:04 pm, Yevgen Muntyan wrote: x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (INT_MAX / ABS(x) ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) || ((x 0 && y < 0 || x < 0 && y 0) && ((-INT_MIN) / ABS(x) ABS(y) || ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));>I wonder if there is simple portable one-expression form of it.What is the purpose of the (INT_MAX % ABS(x) == 0) expression?If INT_MAX / x == y (with x 0) then x*y will be less than orequal to INT_MAX so there is no overflow.No purpose, I was fooled by the initial wrong 'INT_MAX / x < y'condition. So, it's gonna bex == 0 ||((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) ||((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y))Is this one right? If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 thenABS(x) cannot be represented. Yeah, as well as (-INT_MIN). x == 0 || (x 0 && y >= 0 && INT_MAX / x >= y) || (x < 0 && y <= 0 && INT_MAX / x <= y) || (x < 0 && INT_MIN / x >= y) || (x 0 && INT_MIN / y >= x) This is broken too, for the same reasons. I can't get this thing though: result of -a should be int if a is of type int. So how one can get -a value if it overflows? In other words, how do you do unsigned foo = -INT_MIN; (or unsigned long long foo = -LLONG_MIN so we can't escape to bigger type)? Yevgen Mar 12 '07 #25

 P: n/a Yevgen Muntyan wrote: Nelu wrote: >Yevgen Muntyan wrote: >>Old Wolf wrote:On Mar 11, 7:04 pm, Yevgen Muntyan wrote: x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (INT_MAX / ABS(x) ABS(y) || (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) || ((x 0 && y < 0 || x < 0 && y 0) && ((-INT_MIN) / ABS(x) ABS(y) || ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));>I wonder if there is simple portable one-expression form of it.What is the purpose of the (INT_MAX % ABS(x) == 0) expression?If INT_MAX / x == y (with x 0) then x*y will be less than orequal to INT_MAX so there is no overflow.No purpose, I was fooled by the initial wrong 'INT_MAX / x < y'condition. So, it's gonna bex == 0 ||((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) ||((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y))Is this one right? If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 thenABS(x) cannot be represented. Yeah, as well as (-INT_MIN). x == 0 || (x 0 && y >= 0 && INT_MAX / x >= y) || (x < 0 && y <= 0 && INT_MAX / x <= y) || (x < 0 && INT_MIN / x >= y) || (x 0 && INT_MIN / y >= x) This is correct. Keith Thompson was right, as usual. It's not trivial and it seems computationally expensive. Well, it seems trivial once you know how to do it :-). -- Ioan - Ciprian Tandau tandau _at_ freeshell _dot_ org (hope it's not too late) (... and that it still works...) Mar 12 '07 #26

 P: n/a Yevgen Muntyan wrote: Yevgen Muntyan wrote: >Nelu wrote: >>Yevgen Muntyan wrote:Old Wolf wrote:On Mar 11, 7:04 pm, Yevgen Muntyan wrote:> x == 0 ||> ((x 0 && y >= 0 || x < 0 && y <= 0) &&> (INT_MAX / ABS(x) ABS(y) ||> (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) ||> ((x 0 && y < 0 || x < 0 && y 0) &&> ((-INT_MIN) / ABS(x) ABS(y) ||> ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));>>>I wonder if there is simple portable one-expression form of it.What is the purpose of the (INT_MAX % ABS(x) == 0) expression?If INT_MAX / x == y (with x 0) then x*y will be less than orequal to INT_MAX so there is no overflow.No purpose, I was fooled by the initial wrong 'INT_MAX / x < y'condition. So, it's gonna bex == 0 ||((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) ||((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y))Is this one right?If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 thenABS(x) cannot be represented. Yeah, as well as (-INT_MIN). unsigned abs (int x) { if (x >= 0) return x; else return UINT_MAX - (unsigned)x; } int nooverflow (int x, int y) { unsigned ux = abs (x); unsigned uy = abs (y); return x == 0 || ((x 0 && y >= 0 || x < 0 && y <= 0) && (unsigned) INT_MAX / ux >= uy) || ((x 0 && y < 0 || x < 0 && y 0) && abs(INT_MIN) / ux >= uy); } Can we assume INT_MAX and magnitude of INT_MIN are not greater than UINT_MAX? Yevgen Mar 12 '07 #27

 P: n/a Nelu wrote: Yevgen Muntyan wrote: >Nelu wrote: >>Yevgen Muntyan wrote:Old Wolf wrote:On Mar 11, 7:04 pm, Yevgen Muntyan wrote:> x == 0 ||> ((x 0 && y >= 0 || x < 0 && y <= 0) &&> (INT_MAX / ABS(x) ABS(y) ||> (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) ||> ((x 0 && y < 0 || x < 0 && y 0) &&> ((-INT_MIN) / ABS(x) ABS(y) ||> ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));>>>I wonder if there is simple portable one-expression form of it.What is the purpose of the (INT_MAX % ABS(x) == 0) expression?If INT_MAX / x == y (with x 0) then x*y will be less than orequal to INT_MAX so there is no overflow.No purpose, I was fooled by the initial wrong 'INT_MAX / x < y'condition. So, it's gonna bex == 0 ||((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) ||((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y))Is this one right?If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 thenABS(x) cannot be represented. Yeah, as well as (-INT_MIN).x == 0 ||(x 0 && y >= 0 && INT_MAX / x >= y) ||(x < 0 && y <= 0 && INT_MAX / x <= y) ||(x < 0 && INT_MIN / x >= y) ||(x 0 && INT_MIN / y >= x) This is correct. Unfortunately no, division overflows :( Yevgen Mar 12 '07 #28

 P: n/a Yevgen Muntyan wrote: Nelu wrote: >Yevgen Muntyan wrote: >>Nelu wrote:Yevgen Muntyan wrote:Old Wolf wrote:>On Mar 11, 7:04 pm, Yevgen Muntyan >wrote:>> x == 0 ||>> ((x 0 && y >= 0 || x < 0 && y <= 0) &&>> (INT_MAX / ABS(x) ABS(y) ||>> (INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) ||>> ((x 0 && y < 0 || x < 0 && y 0) &&>> ((-INT_MIN) / ABS(x) ABS(y) ||>> ((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));>>>>>I wonder if there is simple portable one-expression form of it.>What is the purpose of the (INT_MAX % ABS(x) == 0) expression?>If INT_MAX / x == y (with x 0) then x*y will be less than or>equal to INT_MAX so there is no overflow.No purpose, I was fooled by the initial wrong 'INT_MAX / x < y'condition. So, it's gonna be>x == 0 ||((x 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >=ABS(y)) ||((x < 0 && y >= 0 || x 0 && y <= 0) && (-INT_MIN) / ABS(x) >=ABS(y))>Is this one right?If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 thenABS(x) cannot be represented.Yeah, as well as (-INT_MIN).x == 0 ||(x 0 && y >= 0 && INT_MAX / x >= y) ||(x < 0 && y <= 0 && INT_MAX / x <= y) ||(x < 0 && INT_MIN / x >= y) ||(x 0 && INT_MIN / y >= x) This is correct. Unfortunately no, division overflows :( Oooops. My mistake. And this was the exact problem I was trying to solve a few minutes ago :-)). -- Ioan - Ciprian Tandau tandau _at_ freeshell _dot_ org (hope it's not too late) (... and that it still works...) Mar 12 '07 #29

 P: n/a On Mar 10, 7:37 pm, CBFalconer With recent GCC versions you can use -ftrapv to get a trap on integer overflow. I'm still using 3.2.1, but I might install 4.1 shortly. I thought that didn't work for x86 code. Assuming Mingw, here are some unofficial 4.x builds (I use them and they seem fine): http://www.thisiscool.com/gcc_mingw.htm -- "A man who is right every time is not likely to do very much." -- Francis Crick, co-discover of DNA "There is nothing more amazing than stupidity in action." -- Thomas Matthews -- Posted via a free Usenet account fromhttp://www.teranews.com Mar 12 '07 #30

 P: n/a On Mar 10, 7:37 pm, CBFalconer With recent GCC versions you can use -ftrapv to get a trap on integer overflow. I'm still using 3.2.1, but I might install 4.1 shortly. I thought that didn't work for x86 code. Assuming Mingw, here are some unofficial 4.x builds (I use them and they seem fine): http://www.thisiscool.com/gcc_mingw.htm -- "A man who is right every time is not likely to do very much." -- Francis Crick, co-discover of DNA "There is nothing more amazing than stupidity in action." -- Thomas Matthews -- Posted via a free Usenet account fromhttp://www.teranews.com Mar 12 '07 #31

 P: n/a user923005 wrote: On Mar 10, 7:37 pm, CBFalconer Ben Pfaff wrote: >>CBFalconer >>It is unfortunate that compilers don't normally implement a trap oninteger overflow, so without taking care you can get nonsenseresults. >>With recent GCC versions you can use -ftrapv to get a trap oninteger overflow. I'm still using 3.2.1, but I might install 4.1 shortly. I thoughtthat didn't work for x86 code. Assuming Mingw, here are some unofficial 4.x builds (I use them and they seem fine): http://www.thisiscool.com/gcc_mingw.htm I was referring to the effectiveness of -ftrapv. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. -- Posted via a free Usenet account from http://www.teranews.com Mar 12 '07 #32

### This discussion thread is closed

Replies have been disabled for this discussion. 