tac@cs.brown.edu (Theodore A. Camus) (09/06/90)
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)
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.
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.
For most compilers, '>>' will differentiate between signed and unsigned
arguments, but again K&R and ANSI allows it to be implementation-defined.
Any answers ?
- Ted
CSnet: tac@cs.brown.edu Ted Camus
ARPAnet: tac%cs.brown.edu@relay.cs.net Box 1910 CS Dept
BITnet: tac@browncs.BITNET Brown University
"An ounce of example is worth a pound of theory." Providence, RI 02912karl@haddock.ima.isc.com (Karl Heuer) (09/06/90)
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
henry@zoo.toronto.edu (Henry Spencer) (09/06/90)
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. In a word (well, three words): can't be done. -- TCP/IP: handling tomorrow's loads today| Henry Spencer at U of Toronto Zoology OSI: handling yesterday's loads someday| henry@zoo.toronto.edu utzoo!henry
throopw@sheol.UUCP (Wayne Throop) (09/10/90)
> From: henry@zoo.toronto.edu (Henry Spencer) >> tac@cs.brown.edu (Theodore A. Camus) >>I would like to do a portable arithmetic right shift in C. >In a word (well, three words): can't be done. Well, I can phrase the answer in only TWO words: im possible. -- Wayne Throop <backbone>!mcnc!rti!sheol!throopw or sheol!throopw@rti.rti.org