Sign in to follow this  
yahastu

which is larger?

Recommended Posts

I have two integral variables "a" and "b" having types "A" and "B", respectively. The types may differ in sign and/or storage size. What is the simplest way in C++ to determine if "a > b" that will never fail?

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Define "never fail".


Give the logically correct result regardless of the sign and storage size of the types.

example:

If they are both signed or both unsigned, then casting the smaller type to the larger type before making the comparison should work.

If one of them is signed and the other unsigned, and the signed variable is positive, and the signed variable is not larger than what fits in the unsigned type, then it can be cast to the unsigned type for comparison. Similarly, if its negative, it can be multiplied by -1 before casting and the result can be inverted.

Another case is if one variable is signed and the other unsigned, but the signed value is too large to fit in the unsigned value...in which case the unsigned value can be cast to the signed value.

So, there seem to be a lot of special cases...

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu
I have two integral variables "a" and "b" having types "A" and "B", respectively. The types may differ in sign and/or storage size. What is the simplest way in C++ to determine if "a > b" that will never fail?


In theory, I believe this should work:

template <typename typea, typename typeb>
bool Is_A_GT_B(typea a, typeb b)
{
if(sizeof(typea) >= sizeof(typeb))
return a > (typea)b;
return (typeb)a > b;
}



Let's consider the cases

A = unsigned __int64
B = char
sizeof A > sizeof B, B is typecast into A's type, comparison of like values

B = unsigned __int64
A = char
sizeof A < sizeof B, A is typecast into B's type, comparison of like values

A = char
B = char
sizeof A >= sizeof B, B is typecast into A's type (irrelevant), comparison of like values

Anyone see any problems?

Share this post


Link to post
Share on other sites
Here's a comparison of a naive approach and a somewhat better approach (except to eliminate warnings one should use a type trait like make_unsigned on a signed that is greater than or equal to 0.

Also note how the naive approach fails on types that should be the same size (unsinged long/signed long) but differ in signedness (an implicit cast to the larger type should happen anyway if the sizes differ):


#include <iostream>
#include <limits>

template <class A, class B>
bool bad_greater(A a, B b)
{
return a > b;
}

template <class A, class B, bool ASigned, bool BSigned>
struct safe_greater
{
static bool compare(A a, B b) { return a > b; }
};

template <class A, class B>
struct safe_greater<A, B, true, false>
{
static bool compare(A a, B b) {
return !a < 0 && a > b;
}
};

template <class A, class B>
struct safe_greater<A, B, false, true>
{
static bool compare(A a, B b)
{
return b < 0 || a > b;
}
};

template <class A, class B>
bool better_greater(A a, B b)
{
return safe_greater<A, B, std::numeric_limits<A>::is_signed, std::numeric_limits<B>::is_signed>::compare(a, b);
}

#define COMPARE(a, b) std::cout << (a) << " > " << (b) << ": " << bad_greater((a), (b)) << ' ' << better_greater((a), (b))<< '\n'
int main()
{
long l = -1L;
unsigned long ul = std::numeric_limits<unsigned long>::max() - 1UL;
unsigned long other_ul = 437682;
std::cout << std::boolalpha;
COMPARE(l, ul);
COMPARE(ul, l);
COMPARE(other_ul, ul);
COMPARE(ul, other_ul);
}




Share this post


Link to post
Share on other sites
Quote:
Original post by Drew_Benton
Anyone see any problems?


If typea = signed int, typeb = unsigned int, then this would cast the unsigned int to int before comparison, which could result in incorrect result because the unsigned type may be larger than INT_MAX

EDIT: visitor, your "better_greater" function also has this problem.

[Edited by - yahastu on September 14, 2009 3:02:21 PM]

Share this post


Link to post
Share on other sites
Quote:

EDIT: visitor, your "better_greater" function also has this problem.


Can you post a concrete example where this fails. As far as I see no unsafe casts should happen, because types with mixed signness are handled separately. (I may be mistaken, but in case of mixed signness, isn't the signed implicitly cast to unsigned, not the other way round.)

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
Quote:

EDIT: visitor, your "better_greater" function also has this problem.


Can you post a concrete example where this fails. As far as I see no unsafe casts should happen, because types with mixed signness are handled separately. (I may be mistaken, but in case of mixed signness, isn't the signed implicitly cast to unsigned, not the other way round.)


In the following specialized code A is signed and B is unsigned, assume b is greater than MAX_INT, so b will be cast to signed int in order to make the comparison, causing it to wraparound and then "a>b" will evaluate to true, even though b > a.


template <class A, class B>
struct safe_greater<A, B, true, false>
{
static bool compare(A a, B b) {
return !a < 0 && a > b;
}
};




this should fix that problem


template <class A, class B>
struct safe_greater<A, B, true, false>
{
static bool compare(A a, B b) {
if( a < 0 ) return false;
if( b > (B)std::numeric_limits<A>::max() ) return false;
return a > b;
}
};




but this still assumes that the unsigned B type is large enough to hold the largest positive signed value of the A type...which might not be the case

Share this post


Link to post
Share on other sites
You've got the basic idea, yeah. Comparisons between signed and unsigned are unsafe unless the signed value is known to be nonnegative. (This is the most common case for signed/unsigned comparisons, but warnings are still in order.) Any two signed or any two unsigned types can be safely compared, because the domain in which the comparison is performed is a superset of the domain of each operand.

As to your point about clever tricks for comparison: The simplest method is an early-out for a negative signed operand, followed by the regular comparison.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
You've got the basic idea, yeah. Comparisons between signed and unsigned are unsafe unless the signed value is known to be nonnegative. (This is the most common case for signed/unsigned comparisons, but warnings are still in order.) Any two signed or any two unsigned types can be safely compared, because the domain in which the comparison is performed is a superset of the domain of each operand.

As to your point about clever tricks for comparison: The simplest method is an early-out for a negative signed operand, followed by the regular comparison.


Ah ha! Good idea, I was trying to figure out how to cast them into the same type. So, something like this should work?

template <typename typea, typename typeb>
bool Is_A_GT_B(typea a, typeb b)
{
bool isASigned = std::numeric_limits<typea>::is_signed;
bool isBSigned = std::numeric_limits<typeb>::is_signed;
if((isASigned && isBSigned) || (!isASigned && !isBSigned))
{
return a > b;
}
else
{
if(isASigned)
{
if(a < 0)
return false;
else
return a > b;
}
else
{
if(b < 0)
return false;
else
return a > b;
}
}
}


Share this post


Link to post
Share on other sites
Quote:

In the following specialized code A is signed and B is unsigned, assume b is greater than MAX_INT, so b will be cast to signed int in order to make the comparison, causing it to wraparound and then "a>b" will evaluate to true, even though b > a.


This doesn't appear to be a problem for better_greater. If operands are different, the compiler performs an implicit cast based on both operands (I don't think this depends on the order of operands). This behavior should be entirely standardized and it appears that in case of mixed signed-ness the signed operand is cast to unsigned. Since we have already checked that it is not negative, casting it to unsigned should be OK.

There should be zero doubt if you used a make_unsigned type trait on the signed operand if it is positive, which also suppresses a compiler warning. boost::make_unsigned however doesn't appear to work with non-integral types, if you are interested in those as well.

A full example of what I had in mind:


#include <iostream>
#include <limits>

template <class T>
struct make_unsigned {};

template <>
struct make_unsigned<char> { typedef unsigned char type; };
template <>
struct make_unsigned<unsigned char> { typedef unsigned char type; };
template <>
struct make_unsigned<signed char> { typedef unsigned char type; };
template <>
struct make_unsigned<short> { typedef unsigned short type; };
template <>
struct make_unsigned<unsigned short> { typedef unsigned short type; };
template <>
struct make_unsigned<int> { typedef unsigned int type; };
template <>
struct make_unsigned<unsigned int> { typedef unsigned int type; };
template <>
struct make_unsigned<long> { typedef unsigned long type; };
template <>
struct make_unsigned<unsigned long> { typedef unsigned long type; };

//can't make these unsigned but there shouldn't be problems?
template <>
struct make_unsigned<float> { typedef float type; };
template <>
struct make_unsigned<double> { typedef double type; };


template <class A, class B>
bool bad_greater(A a, B b)
{
return static_cast<B>(a) > b;
}

template <class A, class B, bool ASigned, bool BSigned>
struct safe_greater
{
static bool compare(A a, B b) { return a > b; }
};

template <class A, class B>
struct safe_greater<A, B, true, false>
{
static bool compare(A a, B b) {
return !a < 0 && static_cast<typename make_unsigned<A>::type>(a) > b;
}
};

template <class A, class B>
struct safe_greater<A, B, false, true>
{
static bool compare(A a, B b)
{
return b < 0 || a > static_cast<typename make_unsigned<B>::type>(b);
}
};

template <class A, class B>
bool better_greater(A a, B b)
{
return safe_greater<A, B, std::numeric_limits<A>::is_signed, std::numeric_limits<B>::is_signed>::compare(a, b);
}

#define COMPARE(a, b) std::cout << (a) << " > " << (b) << ": " << bad_greater((a), (b)) << ' ' << better_greater((a), (b))<< '\n'
int main()
{
long l = -1L;
unsigned long ul = std::numeric_limits<unsigned long>::max() - 1UL;
unsigned long other_ul = 437682;

std::cout << std::boolalpha;
COMPARE(l, ul);
COMPARE(ul, l);
COMPARE(other_ul, ul);
COMPARE(ul, other_ul);
long other_long = 1;
COMPARE(other_long, ul); //your counter-example
COMPARE(ul, other_long);
}




[Edited by - visitor on September 14, 2009 5:27:10 PM]

Share this post


Link to post
Share on other sites
Quote:
In the following specialized code A is signed and B is unsigned, assume b is greater than MAX_INT, so b will be cast to signed int in order to make the comparison,

b will not be cast to int as b is either unsigned int or unsigned long as it is bigger than INT_MAX, depending on the a's type, b maybe left as it is or will be cast to unsigned long or other which I will cover after looking at visitor's quote.

The next quote is taken out of context as I disregard that b is greater than INT_MAX just for fullness:
Quote:
it appears that in case of mixed signed-ness the signed operand is cast to unsigned

Not strictly true. Both operands can be promoted to int or long on the prerequisite that the type can represent both operands. It really depends on the operand types.

Now if b is greater then INT_MAX and a is not a floating point type then it leaves a couple of possibilities which promote the operands to unsigned.
If a is long then both are promoted to unsigned long.
if a is int and b is unsigned int both a is promoted to unsigned int.
if a is int and b is unsigned long, a is promoted to unsigned long.
else a is promoted to b's type (given that a is not a floating point).

Then there is also the possibility that a or b is float, double or long double which overrides all of the above. In which case both operands are cast to the larger floating point type which one of the operands is.

I do hope I got that all correct. :)

Share this post


Link to post
Share on other sites
Should/could such a comparison also be made to work if one of the operands is of a class type such as a home made bigint class?
Is it okay for a such a class to give specialisations for numeric_limits, like we can with std::swap? Or is it kinda bad to do that?

Share this post


Link to post
Share on other sites
Quote:
Not strictly true. Both operands can be promoted to int or long on the prerequisite that the type can represent both operands. It really depends on the operand types.
That's true for int, though I don't believe it's true for long. However, since short is not required to be shorter than int, it's not a-priori okay to compare unsigned short and signed whatever; the promotion from unsigned short may be to unsigned int, even when comparing with a signed int.

Of course, the bestest of all solution is this: Never ever ever* use unsigned numbers. Even when you know that something will never be negative. They don't keep you safe; they just make bugs stranger.


*ever ever ever. Except xyz.

Share this post


Link to post
Share on other sites
Quote:
Original post by Drew_Benton
Ah ha! Good idea, I was trying to figure out how to cast them into the same type. So, something like this should work?


Looks fine to me, although c'mon, man, if(isASigned == isBSigned).[grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by Drew_Benton
Ah ha! Good idea, I was trying to figure out how to cast them into the same type. So, something like this should work?


Looks fine to me, although c'mon, man, if(isASigned == isBSigned).[grin]


Oh geeze! I don't even know what to say. [lol] I had to think about that logic too, my C++ skills (or so the skills I thought I once had) are really evading me in this thread.

Thanks for the original idea though. I had a harder time understanding the problem and a solution than I thought I would. I need to be more signed-aware in my programs because I've never really given this stuff a second thought. I mean I read about program exploits due to signed issues, but it's not something I've actively been on the lookout for.

Share this post


Link to post
Share on other sites
I sure hope the third times the charm! I've reduced the logic a bit and cleaned up the things you pointed out.


template <typename typea, typename typeb>
bool Is_A_GT_B(typea a, typeb b)
{
bool isASigned = std::numeric_limits<typea>::is_signed;
bool isBSigned = std::numeric_limits<typeb>::is_signed;
if(isASigned != isBSigned)
{
if(isASigned)
{
if(a < 0)
return false;
}
else
{
if(b < 0)
return true;
}
}
return a > b;
}

Share this post


Link to post
Share on other sites
That looks right. Though the sadist in me wants to write:

template <typename typea, typename typeb>
bool Is_A_GT_B(typea a, typeb b)
{
bool isASigned = std::numeric_limits<typea>::is_signed;
bool isBSigned = std::numeric_limits<typeb>::is_signed;
if(isASigned != isBSigned && (isASigned ? a : b) < 0) return isBSigned;
return a > b;
}

Share this post


Link to post
Share on other sites
Thanks for the discussion.

The signedness checks can be done statically to improve upon efficiency:


template <class A, class B, bool ASigned, bool BSigned>
struct greater_impl
{
static inline bool call(A a, B b) { return a > b; }
};

template <class A, class B>
struct greater_impl<A, B, true, false>
{
static inline bool call(A a, B b) {
if( a < 0 ) return false;
return a > b;
}
};

template <class A, class B>
struct greater_impl<A, B, false, true>
{
static inline bool call(A a, B b)
{
if( b < 0 ) return true;
return a > b;
}
};

template<class A, class B>
inline bool safe_greater(A a, B b)
{
return greater_impl<A,B, std::numeric_limits<A>::is_signed, std::numeric_limits<B>::is_signed >::call(a,b);
}


Share this post


Link to post
Share on other sites
Because the is_signed field is a static const, there's no need to use template specialization here -- any sane compiler will remove the static branch automatically.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this