Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!sun-barr!cs.utexas.edu!uunet!mcvax!ukc!etive!aiai!ken
From: ken@aiai.ed.ac.uk (Ken Johnson)
Newsgroups: comp.lang.c
Subject: How to multiply two ints and check overflow
Keywords: overflow
Message-ID: <434@skye.ed.ac.uk>
Date: 12 May 89 13:04:15 GMT
Reply-To: ken@aiai.UUCP (Ken Johnson)
Followup-To: comp.lang.c
Organization: AIAI, University of Edinburgh, Scotland
Lines: 104

/*
	The following program performs integer multiplication and
	detects overflow. It works on ints greater than or equal to 0.
	It is of course a very great deal slower than just using the
	* operator -- I have assumed you are prepared to spend all that
	time because you can't just stick the answer in a `long' and
	check the upper bits in the long are all empty!

	Note -- this worked on all the examples I threw at it, but I
	do not guarantee it at all. Let me know if you improve it.

	Ken Johnson, 12 May 1989. You may use this code freely, except
	that if you sell copies at a profit, I want a share.

	Here goes...
*/


#include <stdio.h>

#define	YES	1
#define	NO	0

#define	RTMOST_BIT	0x0001		/* These assume a 16-bit word */
#define	SIGN_BIT	0x8000

main(argc,argv)				/* Test harness, self explanatory */
int	argc;				/* :-)                            */
char	**argv;
{
	int	vmul( );		/* The function I'm interested in */

	if (argc != 3)
	{
		fprintf(stderr,"usage: VMUL N1 N2\n");
		exit(1);
	}

	{
		int	ovf;
		int	n1, n2, ans;

		n1 = atoi(*++argv);
		n2 = atoi(*++argv);

		if ( n1 < 0 || n2 < 0)
		{
			fprintf(stderr,"VMUL: both args must be >= 0\n");
			exit(1);
		}

		ans = vmul(n1,n2,&ovf);

		printf("%d * %d = %d, %s overflow\n",
			n1,  n2,  ans,  ((ovf == YES) ? "" : "no"));
	}
}

/*
	vmul(n1,n2,&ovf) returns the product of integers n1 and n2,
	setting the flag OVF to the constant YES or NO. If overflow
	occurs, then vmul always returns 0.

	It works on the Russian Multiplication algorithm. The number of
	passes through the loop will be the number of bits set in n2,
	that is, at most one less than the number of bits in an int.
*/

int	vmul(n1,n2,p_ovf)
int	n1;
int	n2;
int	*p_ovf;
{
	int	product;
	product = 0;

	while(n2)
	{
		if (n1 & SIGN_BIT)		/* Check multiplier is in */
		{				/* range.                 */
			*p_ovf = YES;
			return(0);
		}

		if (n2 & RTMOST_BIT)		/* Add n1 into product and */
		{				/* check overflow          */
			if ((product += n1) & SIGN_BIT)
			{
				*p_ovf = YES;
				return(0);
			}
		}

		n1 <<= 1;
		n2 >>= 1;
	}

	*p_ovf = NO;				/* Normal exit */
	return(product);
}
-- 
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
Half of what I have said in this article is rubbish. I don't know which half.