home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / programm / 2431 < prev    next >
Encoding:
Internet Message Format  |  1992-08-22  |  2.6 KB
  1. Path: sparky!uunet!idacrd!desj@ccr-p.ida.org
  2. From: desj@ccr-p.ida.org (David desJardins)
  3. Newsgroups: comp.programming
  4. Subject: Re: Detecting Integer Overflow/Underflow
  5. Message-ID: <1572@idacrd.UUCP>
  6. Date: 22 Aug 92 20:44:12 GMT
  7. References: <1992Aug21.182206.15853@progress.com> <HUDGENS.92Aug22113851@sun13.SCRI.FSU.EDU>
  8. Sender: desj@idacrd.UUCP
  9. Organization: IDA Center for Communications Research, Princeton
  10. Lines: 59
  11.  
  12. Jim Hudgens <hudgens@SCRI.FSU.EDU> writes:
  13. >Sample code for adding two 16 bit integers and setting the overflow
  14. >flag based on the result (it's part of an 8086 emulator) follows.
  15.  
  16. >But there has *got* to be a better (i.e. faster) way.  This is one
  17. >of the major reasons I can't get >PC/XT speeds running on a Sun SS1.
  18.  
  19. Your code seems much too complicated to understand!  The following is
  20. much easier.  It just relies on the fact that overflow occurs iff a and
  21. b have the same sign, and a+b has the opposite sign.
  22.  
  23. I've also included code for unsigned overflow.  (It wasn't specified in
  24. the original posting which was required.)  This computes the same
  25. quantity that Jim called cc, but with four operations instead of five.
  26.  
  27. By the way, I think it is a shame that most computer scientists are
  28. taught that a good way to synthesize boolean functions is with a
  29. Karnaugh map.  This is somewhat reasonable for a hardware engineer using
  30. only NAND gates, but for a more general computational model, it's rarely
  31. a good idea.  I remember vividly scoring 110 out of 100 on a test at MIT
  32. on which one of the questions was, "Synthesize this function with the
  33. minimum number of gates," and I did better than the "correct" solution
  34. which used a Karnaugh map.)
  35.  
  36. I suspect the general problem is NP-hard, which is probably why they
  37. don't teach an optimal algorithm :-).
  38.  
  39.                                         David desJardins
  40.  
  41.  
  42. #define WORDSIZE 16
  43.  
  44. int addint (int a, int b, int &overflow) {
  45.   /* a and b are signed integers, WORDSIZE is the length of each.  The
  46.      return value is the sum of a and b, and the value of overflow is 1
  47.      if overflow occurred, or zero otherwise. */
  48.  
  49.   int sum;
  50.   unsigned int temp;
  51.  
  52.   sum = a + b;
  53.   temp = (a ^ sum) & (b ^ sum);
  54.   *overflow = temp >> (WORDSIZE - 1);
  55.   return sum;
  56. }
  57.  
  58. unsigned int adduint (unsigned int a, unsigned int b, int &overflow) {
  59.   /* a and b are unsigned integers, WORDSIZE is the length of each.  The
  60.      return value is the sum of a and b, and the value of overflow is 1
  61.      if overflow occurred, or zero otherwise. */
  62.  
  63.   unsigned int sum;
  64.   unsigned int temp;
  65.  
  66.   sum = a + b;
  67.   temp = ((a ^ sum) & (a ^ b)) ^ b;
  68.   *overflow = temp >> (WORDSIZE - 1);
  69.   return sum;
  70. }
  71.