Efficient way to tell the 'sign' of a number?
Author 
Message 
cosg.. #1 / 25

Efficient way to tell the 'sign' of a number?
I have the following: #include <stdio.h> #define MASK 128 int main(void) { int i = 1; if (MASK & i) printf("negative"); else printf("positive"); return 0; Quote: }
this simply bitwise ands the number with a mask of 128 (msb of 1) to see if the number is positive/negative on a two's complement machine. Obviously, this is a cheesed up way of implementing this, but my question is this. What happens if the number is 128? What's the most efficient way of getting the sign of a number? There may be more practical ways to do this, but I'm trying to understand how the sign bits are implemented. Thanks. Sent via Deja.com http://www.***.com/ Before you buy.

Sat, 24 Aug 2002 03:00:00 GMT 


Jus T. Eg #2 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> I have the following: > #include <stdio.h> > #define MASK 128 > int main(void) > { > int i = 1; > if (MASK & i) > printf("negative"); > else > printf("positive"); > return 0; > } > this simply bitwise ands the number with a mask of 128 (msb of 1) to > see if the number is positive/negative on a two's complement machine. > Obviously, this is a cheesed up way of implementing this, but my > question is this. What happens if the number is 128? What's the most > efficient way of getting the sign of a number?
If you are masking to 128, then you are assuming that the two's compliment is the eighth bit of a one byte number. The range would therefore be 127 to 128. Bit 7 6 5 4 3 2 1 0 Value 128 64 32 16 8 4 2 1 Examples 1 0 0 0 0 0 0 0 = 128 0 0 0 0 0 0 0 0 = 0 0 1 1 1 1 1 1 1 = 127 1 1 1 1 1 1 1 1 = 1 So a positive value of 128 wouldn't happen. Sadly, you can't make such assumptions. The size of your datatype should not really be a requirement of your program. My advice would be to use the abs(..) function from stdlib.h, as below: #include <stdio.h> #include <stdlib.h> int main(argc, argv) int argc; char *argv[]; { /* int i = 1; */ int i = 1; if (i == abs(i)) printf("Positive\n"); else printf("Negative\n"); return EXIT_SUCCESS; Quote: } > There may be more practical ways to do this, but I'm trying to > understand how the sign bits are implemented.
Sadly such work leads to importabilityland. You have to consider the size of your data types, the byte ordering and the method by which the negative is implemented, i.e 2's compliment. If this is a learning exercise then I'd recommend playing around with the different data types, i.e. short, int, long, float, double, and seeing which mask works over the full run of a loop. Then try it on a different machine / OS. Then again on another. Unless you really want to do this... I'd stick to reading about these things in the books, browsing through the C header files for different compilers, or using the standards functions. i.e. abs(..). Quote: > Thanks.
Hope something here was of use... Good luck, J.  "These thoughts, and the strain I am under."  TY Sent via Deja.com http://www.deja.com/ Before you buy.

Sat, 24 Aug 2002 03:00:00 GMT 


smade.. #3 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> I have the following: > #include <stdio.h> > #define MASK 128 > int main(void) > { > int i = 1; > if (MASK & i) > printf("negative"); > else > printf("positive"); > return 0; > } > this simply bitwise ands the number with a mask of 128 (msb of 1) to > see if the number is positive/negative on a two's complement machine. > Obviously, this is a cheesed up way of implementing this, but my > question is this. What happens if the number is 128? What's the most > efficient way of getting the sign of a number? > There may be more practical ways to do this, but I'm trying to > understand how the sign bits are implemented. > Thanks. > Sent via Deja.com http://www.deja.com/ > Before you buy.
The code above is only valid for a onebyte signed integer. I'm not sure why you need to do this and can't just use the > and < operators. This is something I came up with on the fly to shift the most significant bit down to the least and then AND it with 1. This probably is not the most efficient way: #define SIGN( x ) ( (x>>(sizeof(x) * 8 )1) & 1 ? "neg" : "pos" ) This should work for signed numbers, however, I haven't put it through a rigorous test. Sent via Deja.com http://www.deja.com/ Before you buy.

Sat, 24 Aug 2002 03:00:00 GMT 


rawc.. #4 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> > I have the following: > > #include <stdio.h> > > #define MASK 128 > > int main(void) > > { > > int i = 1; > > if (MASK & i) > > printf("negative"); > > else > > printf("positive"); > > return 0; > > } > > this simply bitwise ands the number with a mask of 128 (msb of 1) to > > see if the number is positive/negative on a two's complement machine. > > Obviously, this is a cheesed up way of implementing this, but my > > question is this. What happens if the number is 128? What's the most > > efficient way of getting the sign of a number? > > There may be more practical ways to do this, but I'm trying to > > understand how the sign bits are implemented. > The code above is only valid for a onebyte signed integer. I'm not > sure why you need to do this and can't just use the > and < operators. > This is something I came up with on the fly to shift the most > significant bit down to the least and then AND it with 1. This > probably is not the most efficient way: > #define SIGN( x ) ( (x>>(sizeof(x) * 8 )1) & 1 ? "neg" : "pos" ) > This should work for signed numbers, however, I haven't put it through > a rigorous test.
You should replace 8 with CHAR_BIT from <limits.h>. This of course assumes 2's complement representation, and no unused bits in an int; converting to unsigned int would force the highest used bit to be set if and only if x were negative. I would put the x in parentheses in case >> has higher precedence than an operator in x when the macro substitution occurs. Although subtraction has higher precedence than shifting, I would probably still write (x)>>((sizeof(x)*CHAR_BIT)1) in order to avoid thinking about it or forcing a reader to look it up. Shifting 1 up to the most significant bit and ANDing it would probably be more efficient (as the compiler would be more likely to optimize out the shift). The most efficient way to detect whether x is negative is likely to be x<0.  MJSR Sent via Deja.com http://www.deja.com/ Before you buy.

Sat, 24 Aug 2002 03:00:00 GMT 


Ross #5 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> I have the following:
[code snipped] Quote: > this simply bitwise ands the number with a mask of 128 (msb of 1) to > see if the number is positive/negative on a two's complement machine. > Obviously, this is a cheesed up way of implementing this,
Yup. Quote: > but my question is this. What happens if the number is 128? > What's the most efficient way of getting the sign of a number?
IF you are assuming an architecture that uses twos complement representation, checking the MSB would do it. This makes too many assumptions, though. Numbers need not be represented this way. The difference between any bit{*filter*}ing and: int x; ... if(x < 0) { ... Quote: }
else { ... Quote: }
in terms of cycles is not detectable in the vast majority of cases. If this is in some highspeed code that needs to be optimized, then you need to specialize the code according to the architecture and this may not be portable. Quote: > There may be more practical ways to do this, but I'm trying to > understand how the sign bits are implemented.
In twos complement, the MSB is set in a negative number; to get the absolute value of a negative number, switch all other bits and add one. Quote: > Thanks. > Sent via Deja.com http://www.***.com/ > Before you buy.

Sat, 24 Aug 2002 03:00:00 GMT 


John Winte #6 / 25

Efficient way to tell the 'sign' of a number?
Quote:
>I have the following: >#include <stdio.h> >#define MASK 128 >int main(void) >{ > int i = 1; > if (MASK & i) > printf("negative"); > else > printf("positive"); > return 0; >} >this simply bitwise ands the number with a mask of 128 (msb of 1) to >see if the number is positive/negative on a two's complement machine. >Obviously, this is a cheesed up way of implementing this, but my >question is this. What happens if the number is 128? What's the most >efficient way of getting the sign of a number?
if (i < 0) HTH John  John Winters. Wallingford, Oxon, England. The Linux Emporium  the source for Linux CDs in the UK See http://www.linuxemporium.co.uk/

Sat, 24 Aug 2002 03:00:00 GMT 


Steven Hua #7 / 25

Efficient way to tell the 'sign' of a number?
[...] Quote: > My advice would be to use the abs(..) function from stdlib.h, as below:
[...] Quote: > int i = 1; > if (i == abs(i)) > printf("Positive\n"); > else > printf("Negative\n");
[...] Or simpler yet: if (i < 0) /* negative */ else /* nonnegative */ Whoever wants to optimize this better think long and hard about it, because it's unlikely that the generated code will be terribly inefficient.

Sat, 24 Aug 2002 03:00:00 GMT 


Gergo Bara #8 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> [...] > > My advice would be to use the abs(..) function from stdlib.h, as below: > [...] > > int i = 1; > > if (i == abs(i)) > > printf("Positive\n"); > > else > > printf("Negative\n"); > [...] > Or simpler yet: > if (i < 0) > /* negative */ > else > /* nonnegative */ > Whoever wants to optimize this better think long and hard about it, > because it's unlikely that the generated code will be terribly > inefficient.
Someone (Morris Dovey, I believe) posted something like this about a year or so ago: int sgn(int x) { return (x > 0)  (x < 0); Quote: }
Obviously, if you have three possibilities (positive, negative, zero), one comparison will not be enough; if you only need two possibilities, your code is as good as one can get. Gergo  I saw Lassie. It took me four shows to figure out why the hairy kid never spoke. I mean, he could roll over and all that, but did that deserve a series?

Sat, 24 Aug 2002 03:00:00 GMT 


Richard Heathfiel #9 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> > Someone (Morris Dovey, I believe) posted something like this about a > > year or so ago: > > int sgn(int x) > > { > > return (x > 0)  (x < 0); > > } > > Obviously, if you have three possibilities (positive, negative, zero), > > one comparison will not be enough; if you only need two possibilities, > > your code is as good as one can get. > Lawrence Kirby's cutie only uses 1.5 comparisons on average. > return (x > 0) ? 1 : (x < 0) ? 1 : 0;
Probably fewer than that, actually. Most numbers in actual use are positive. That's not to say that nobody uses negative numbers, or that they are unimportant. But most programs deal mainly with positive numbers. (Admittedly, programs which care about which sign a number has are perhaps more likely to be dealing with negatives than most other programs, but I would venture to suggest that even such programs use positives considerably more than negatives.) I think the mean average number of comparisons in Mr Kirby's technique would be closer to 1.2 or even 1.1. Had he reversed the order of the tests, of course, the average would be correspondingly higher. For details of my exhaustive and painstaking research in this area, check out /dev/null  Richard Heathfield "Usenet is a strange place."  Dennis M Ritchie, 29 July 1999. comp.lang.c FAQ: http://www.eskimo.com/~scs/Cfaq/top.html

Sun, 25 Aug 2002 03:00:00 GMT 


Malcol #10 / 25

Efficient way to tell the 'sign' of a number?
Lawrence Kirby's cutie only uses 1.5 comparisons on Quote: > average. > return (x > 0) ? 1 : (x < 0) ? 1 : 0;
return x >> ( sizeof(x) * CHAR_BIT  1) will do it without any comparisons at all. Sadly you are only almost guaranteed an arithmetic shift right, so this isn't totally portable (usual quibble about twos complement machines applies). * Sent from AltaVista http://www.altavista.com Where you can also find related Web Pages, Images, Audios, Videos, News, and Shopping. Smart is Beautiful

Sun, 25 Aug 2002 03:00:00 GMT 


Dik T. Winte #11 / 25

Efficient way to tell the 'sign' of a number?
> > return (x > 0)  (x < 0); ... > Lawrence Kirby's cutie only uses 1.5 comparisons on average. > return (x > 0) ? 1 : (x < 0) ? 1 : 0; But Lawrence's version might actually be slower on some machines when compiled literally. Especially on those where a jump is expensive and a comparison yields a 0 or 1 in a general register. There are machines where the first would compile to (Ri are registers) something like: R2 = R1 > R0 R3 = R0 > R1 R4 = R2  R3  dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Sun, 25 Aug 2002 03:00:00 GMT 


Jus T. Eg #12 / 25

Efficient way to tell the 'sign' of a number?
Quote: > Or simpler yet: > if (i < 0) > /* negative */ > else > /* nonnegative */ > Whoever wants to optimize this better think long and hard about it, > because it's unlikely that the generated code will be terribly > inefficient.
Doh! *shifty look around* Well, yeah you could do that... *blush* J.  "These thoughts, and the strain I am under."  TY Sent via Deja.com http://www.deja.com/ Before you buy.

Sun, 25 Aug 2002 03:00:00 GMT 


karl malbrai #13 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> Lawrence Kirby's cutie only uses 1.5 comparisons on > > average. > > return (x > 0) ? 1 : (x < 0) ? 1 : 0; > return x >> ( sizeof(x) * CHAR_BIT  1) > will do it without any comparisons at all. Sadly you are > only almost guaranteed an arithmetic shift right, so this > isn't totally portable (usual quibble about twos complement > machines applies).
QUIBBLES are not allowed onto the agenda here. We deal only with bytes as the MINIMUM unit, and bitfields as the MAXIMUM range. Karl M, chair.

Sun, 25 Aug 2002 03:00:00 GMT 


karl malbrai #14 / 25

Efficient way to tell the 'sign' of a number?
Quote:
> > > Someone (Morris Dovey, I believe) posted something like this about a > > > year or so ago: > > > int sgn(int x) > > > { > > > return (x > 0)  (x < 0); > > > } > > > Obviously, if you have three possibilities (positive, negative, zero), > > > one comparison will not be enough; if you only need two possibilities, > > > your code is as good as one can get. > > Lawrence Kirby's cutie only uses 1.5 comparisons on average. > > return (x > 0) ? 1 : (x < 0) ? 1 : 0; > Probably fewer than that, actually. Most numbers in actual use are > positive. That's not to say that nobody uses negative numbers, or that they > are unimportant. But most programs deal mainly with positive numbers.
This is an EQUIVOCATION. Karl M, chair.

Sun, 25 Aug 2002 03:00:00 GMT 


Page 1 of 2

[ 25 post ] 

Go to page:
[1]
[2] 
