Path: utzoo!utgpu!watserv1!watmath!att!rutgers!usc!snorkelwacker!mintaka!spdcc!ima!haddock!karl
From: karl@haddock.ima.isc.com (Karl Heuer)
Newsgroups: comp.lang.c
Subject: Re: shift right arithmetic
Message-ID: <17642@haddock.ima.isc.com>
Date: 6 Sep 90 04:56:09 GMT
References: <49160@brunix.UUCP>
Reply-To: karl@kelp.ima.isc.com (Karl Heuer)
Organization: Interactive Systems, Cambridge, MA 02138-5302
Lines: 47

In article <49160@brunix.UUCP> tac@cs.brown.edu (Theodore A. Camus) writes:
>I would like to do a portable arithmetic right shift in C.
>Possible solutions and problems :
>1) '>>' will _not_ guarantee the result on a signed argument (ANSI & K&R)

True.  I've used a machine where ">>" was logical shift even on signed int.

>2) dividing by a power of 2 will often compile to arithmetic shifts, but
>   only for the smaller powers of 2, not for the full 2^1 - 2^31 shift range.

If negative divide rounds toward zero (as is very common but not required),
you don't even get the right answer: -1 / 2 == 0, -1 >> 1 = -1.  (Check for a
compiler bug here!)  To do this portably you'd have to mask off the low bits
before you divide.

>3) One could test for a negative argument, and if it was negative, use a
>   negate / shift / negate sequence, but there should be a better way.

Well, how about:
	#include <limits.h>
	#define INT_BIT        (CHAR_BIT*sizeof(int))
	#define INT_HIGHBIT    ((unsigned)1 << (INT_BIT-1))
	unsigned int ashr(unsigned int i, int nb) {
	    if (~3 >> 1 == ~1) {
		return ((unsigned int)((signed int)i >> nb));
	    } else {
	#if USE_BRANCH
		return ((i & INT_HIGHBIT) == 0 ? i >> nb :
			(i >> nb) | (~0 << (INT_BIT-nb)));
	#else
		return ((i >> nb) - ((i & INT_HIGHBIT) >> (nb-1)));
	#endif
	    }
	}

This uses ">>" if it's available (you could test for it with the preprocessor
instead of the compiler, if you trust them to be using the same arithmetic),
else it will use either a branching test or a straight-line hack.  The latter
may be faster if a branch would screw up the instruction pipeline.

The argument is declared `unsigned int' so as to produce consistent results
without depending on two's complement non-overflowing arithmetic.  I'm
assuming the specification is to propagate the high-order bit of a bitmap,
regardless of the integer value it happens to represent.  (Have you considered
what you want it to do on a one's complement or sign-magnitude machine?)

Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint