shift right arithmetic
Karl Heuer
karl at haddock.ima.isc.com
Thu Sep 6 14:56:09 AEST 1990
In article <49160 at brunix.UUCP> tac at 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 at kelp.ima.isc.com or ima!kelp!karl), The Walking Lint
More information about the Comp.lang.c
mailing list