Compare sign in C++

[Rob Williscroft]

dwrayment wrote in

ok last post for me if some of you dont like it theres nothing more i
can say.

first off, im not trying to reinvent the multipy op by simulating it
with adding and bit shifts. the question posed was how can we compare
sign of numbers.

soultion 1 was a*b .... i posed a different solution simply !a xor
b >> 31. and now i think about it id rather do
a xor b & 0x70000000 == 0.

Well this is the *real* problem, all that bit-twideling and you've gone
and masked off the sign bit.

here multiplying is inefficient because
doing a simple xor and bitwise and is less work than doing a mulitpy
(on even the best of the best of machines).

Lets start by working with some correct code:

bool thing( int a, int b )
{
return (a * b) > 0;
}

We can write a truth table (N < 0 and P > 0):

a, b, return
------------
0, 0, false
0, P, false
0, N, false
P, 0, false
P, N, false
P, P, true
N, 0, false
N, P, false
N, N, true

Assuming we have 32 bit 2's compliment machine that is:

bool thing( int a, int b )
{
return (a || b) && ((a >> 31) == (b >> 31));
}

or (if you prefer):

bool thing( int a, int b )
{
return
(a || b)
&&
0 == ( ( unsigned(a) ^ unsigned(b) ) & 0x80000000U )
;
}

Assuming (again) that either of the above is faster than (a * b) < 0,
why wouldn't an optimizing C++ compiler make the change.

The reason others have objected to your assertion that "bit-twideling
is faster", is that not only can the compiler do the job for you, so
can modern CPU's and when the CPU does it you get a double hit as
the generated code is shorter too.


Rob.

 

[dwrayment]

my apologies it is a xor b & 0x80000000. typo

 

[Jeff Schwab]

my apologies it is a xor b & 0x80000000. typo

Why would you work at the bit level, tying yourself to a particular size
of integer, just to figure out whether two numbers (a and b) are greater
than a third number (zero)? C++ has built-in operators for this.

-Jeff

PS- Please stop top-posting.

 

[heinz baer]

Lets start by working with some correct code:

bool thing( int a, int b )
{
return (a * b) > 0;
}

What about overflow?

 

[Rob Williscroft]

heinz baer wrote in

What about overflow?

This was the starting point and thus is correct by defenition (it is
the defenition). I used meaningless name "thing" as I don't think its
a good implementation of any "Compare Sign" function.

But you're right my bit twideling alternatives didn't attempt to take
account of (or emmulate) thing()'s overflow behaviour. I may be wrong
but IIUC the result of calling thing( a, b ) when a * b would overflow
would be undefined (or maybe implementation defined) behaviour anyway.

Rob.

 

[dwrayment]

trying hard not to even look as this post anymore but new messages keep
coming up i guess i want to answer.

1. why restrict numbers to 32 bits

unless your planning on making your function a macro, your doing that
very thing anyway, as the parameter will likely be of type int.
the of course you might wanna make a second function for doubles etc.
you can however make it a macro if you want. in this case point taken
i would stlll choose my solution and make the (sacfrice) since most
number crunching is done with 32 bits anyway.


2. overflow

a xor b & 0x80000000 == 0 has no overflow and does not require checking
for such a thing as it is not a * b. the numbers do not grow larger by
any factor.


3. there no need to case a and b to unsigned as one gentlman did.



hooping this is the last last reply i need to do. hoping the orginal
sender got whatever solution he wants! the rest is all hogwash really.

 

[Nate Barney]

trying hard not to even look as this post anymore but new messages keep
coming up i guess i want to answer.

1. why restrict numbers to 32 bits

unless your planning on making your function a macro, your doing that
very thing anyway, as the parameter will likely be of type int.
the of course you might wanna make a second function for doubles etc.
you can however make it a macro if you want. in this case point taken
i would stlll choose my solution and make the (sacfrice) since most
number crunching is done with 32 bits anyway.

What about this? (works only for signed integer types using two's complement)

#include <limits>

template <typename T>
inline bool same_sign(const T &a,const T &b)
{
// possibly do something here with
// std::numeric_limits<T>::is_integer or
// std::numeric_limits<T>::is_signed

return ((a ^ b) & std::numeric_limits<T>::min()) == 0;
}

This seems to solve the problem of dependence on word size... or am I mistaken?

 

[dwrayment]

looks great iff numeric_limits<T>::min() is what i think it is 0x80000000,
etc.. but then you specify within the function must be two-compliment
so my only quam granted its a tiny one is design what appears to be a
generic function but really isnt. but as far as making it work for chars,
and shorts
and _int64's it looks great. the only other thing id wonder about is what
::min() actually does, is it sacrificing efficiency for generic. if
::min() does more work then multiping or whatever then it defeats the
purpose of using xor.

"dwrayment" <[email protected]> wrote in message

What about this? (works only for signed integer types using two's complement)

#include <limits>

template <typename T>
inline bool same_sign(const T &a,const T &b)
{
// possibly do something here with
// std::numeric_limits<T>::is_integer or
// std::numeric_limits<T>::is_signed

return ((a ^ b) & std::numeric_limits<T>::min()) == 0;
}

This seems to solve the problem of dependence on word size... or am I

mistaken?

 

[Nate Barney]

looks great iff numeric_limits<T>::min() is what i think it is 0x80000000,

etc.. but then you specify within the function must be two-compliment

I'm not certain of this at all, but I seem to recall that the C standard
actually stipulates that signed integers are represented using two's
complement. I could be way off base, and I don't have a copy of the
standard... can anybody verify this one way or the other?

so my only quam granted its a tiny one is design what appears to be a
generic function but really isnt. but as far as making it work for chars,
and shorts
and _int64's it looks great. the only other thing id wonder about is what
::min() actually does, is it sacrificing efficiency for generic. if
::min() does more work then multiping or whatever then it defeats the
purpose of using xor.

It's my understanding that numeric_limits is usually implemented through the
use of template specialization, and as such, functions like min() can simply
return the appropriate value and quite probably are inlined as well. I
suppose it depends on the quality of the implementation though.

 

[Ron Natalie]

I'm not certain of this at all, but I seem to recall that the C standard
actually stipulates that signed integers are represented using two's
complement.

No, the current C standard says that : two's complement, one's complement,
and signed-magnitude are the allowable representations. The 1990 C standard
(the one that applies to C++), doesn't go even that far. All it says is that the
positive values have to be the same as their unsigned counterparts (i.e., straight
binary).

 

[dwrayment]

"dwrayment" <[email protected]> wrote in message

I'm not certain of this at all, but I seem to recall that the C standard
actually stipulates that signed integers are represented using two's
complement. I could be way off base, and I don't have a copy of the
standard... can anybody verify this one way or the other?

what i mean by that is the template function would allow programmers to
arbirtaliy try using doubles, floats and god knows what else structs of any
kind
each of which would have undefined behaviour. aka what is
same_sign<double>( a, b) ?

as opposed to intergers not being two-compliment ints

 

[Nate Barney]

what i mean by that is the template function would allow programmers to
arbirtaliy try using doubles, floats and god knows what else structs of any
kind

Well, doubles, yes, arbitrary structs, no. This function would only
compile for types for which the appropriate ^, &, and == are defined.
So most structs/classes would be right out. For doubles, I suppose
you could either throw an exception based on
std::numeric_limits<T>::is_integer, or take a cue from the FAQ (or
even the Standard itself!) and just document the types for which this
function should work. I prefer the second approach.

On the other hand, if someone developed an integer class using two's
complement, overloaded the appropriate operators, and specialized
std::numeric_limits<T> for the class, it should work correctly with
same_sign.

This algorithm is clever, but perhaps too clever. If you wanted it to
work with doubles, or regardless of representation scheme of integers,
I think you'd have to resort to a more arithmetic approach.

Nate

 

[dwrayment]

i wouldnt want to work with doubles, thats why i would choose to go with
the simpler 32 bits only, and not bother with generic coding.
but its up to the guy asking what he wants to do.

 

[EnTn]

Hi,

How can we compare sign of numbers in C++ ?

Bye,
Claude

I've been messing around with direct sign bit access for quick testing.
could be applied to floats or integer types too....

Seems to be stable on both BIG and LITTLE endian machines..
Seems to be quick too...


#if defined(WIN32) || defined(LINUX)
#pragma pack(push)

struct SignBit {
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 7; // padding
bool sign : 1; // sign bit access
};

#else // UNIX

struct SignBit {
bool sign : 1; // sign bit access
unsigned char : 7; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
unsigned char : 8; // padding
};
#endif


union DblSignBit {
double dbl;
SignBit bit;
};

#if defined(WIN32)
#pragma pack(pop)
#endif


But still gives me the shivers..

any good reasons why I shouldn't be doing this???

 

[Ron Natalie]

any good reasons why I shouldn't be doing this???

Yeah, despite your half hearted efforts, it's not portable in
the least. The packing of bit fields is highly implementation
defined. I've seen different compilers even on the same platform
using different packing orders.

 

[EnTn]

Yeah, despite your half hearted efforts, it's not portable in

the least. The packing of bit fields is highly implementation
defined. I've seen different compilers even on the same platform
using different packing orders.

ok, so specialise the bit field code for each compiler used..

 

[Old Wolf]

What about this? (works only for signed integer types using two's complement)

return ((a ^ b) & std::numeric_limits<T>::min()) == 0;

This seems to solve the problem of dependence on word size... or am I mistaken?

This is the same or worse in every respect than:
return (a < 0) ^ (b < 0);

 

[Ron Natalie]

This is the same or worse in every respect than:
return (a < 0) ^ (b < 0);

or even
a < 0 != b < 0

keeps the bool from being widened back to int