Efficient way to tell the 'sign' of a number? 
Author Message
 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  
 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 importability-land.

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  
 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 one-byte 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  
 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 one-byte 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  
 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 high-speed 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  
 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  
 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
    /* non-negative */

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  
 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
>     /* non-negative */

> 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  
 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/C-faq/top.html



Sun, 25 Aug 2002 03:00:00 GMT  
 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  
 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  
 Efficient way to tell the 'sign' of a number?


Quote:
> Or simpler yet:

>   if (i < 0)
>     /* negative */
>   else
>     /* non-negative */

> 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  
 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 bit-fields as the MAXIMUM range.  Karl M, chair.


Sun, 25 Aug 2002 03:00:00 GMT  
 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  
 
 [ 25 post ]  Go to page: [1] [2]

 Relevant Pages 

1. Trouble representing signed 16 bit number as two signed 8 bit numbers

2. warning C4018: '<=' : signed/unsigned mismatch

3. lint says 'questionably signed expression'

4. Don't tell me you can't clone between MDI and Desktop Application

5. Ways to obtain Device Handler if I'm not an administrator

6. How do I parse a string composed of a number with '%' sign

7. asking for help on 'random number'

8. Complex numbers in 'C'

9. what's efficient method to delete rows from db(oracle)

10. What's the most efficient way to ask for another input in a loop

11. Is CString as efficient as char* 's ?

12. Two's compliment and signed arithmetic.

 

 
Powered by phpBB® Forum Software