If x > y, then y - x or (y + (~x + 1)) will be negative, hence the high bit will be 1, otherwise it will be 0. But we want x <= y, which is the negation of this.
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y)
{
return !(((y + (~x + 1)) >> 31) & 1);
}
Even better, drop the shift operator and use a bit mask on the high bit:
int isLessOrEqual(int x, int y)
{
return !((y + (~x + 1)) & 0x80000000);
}
EDIT:
As a commenter pointer out, the above version is susceptible to arithmetic overflow errors. Here is another version that covers the edge cases.
#include <limits>
int isLessOrEqual(int x, int y)
{
static int const vm = std::numeric_limits<int>::max();
static int const sm = ~vm;
return !! ((x & ~y | ~(x ^ y) & ~((y & vm) + ~(x & vm) + 1)) & sm);
}
Explanation: the overall strategy is to treat the sign bit of the inputs as logically distinct from the rest of the bits, the "value bits," and perform the subtraction as in the previous example on just the value bits. In this case, we need only perform the subtraction where the two inputs are either both negative or both non-negative. This avoids the arithmetic overflow condition.
Since the size of int strictly speaking is unknown at run time, we use std::numeric_limits<int>::max() as a convenient mask for the value bits. The mask of the sign bit is simply the bit-wise negation of the value bits.
Turning to the actual expression for <=, we factor out the bit-wise mask sm of the sign bit in each of the sub-expressions and push the operation to the outside of the expression. The first term of the logical expression x & ~y is true when x is negative and y is non-negative. The first factor of the next term ~(x ^ Y) is true when both are negative or both are non-negative. The second factor ~((y & vm) + ~(x & vm) + 1)) is true when y - x is non-negative, in other words x <= y, ignoring the sign bit. The two terms are or'd, so using c++ logical expression syntax we have:
x < 0 && y >= 0 || (x < 0 && y < 0 || x >= 0 && y >= 0) && y - x >= 0
The !! outermost operators convert the raised sign bit to a 1. Finally, here is the Modern C++ templated constexpr version:
template<typename T>
constexpr T isLessOrEqual(T x, T y)
{
using namespace std;
// compile time check that type T makes sense for this function
static_assert(is_integral<T>::value && is_signed<T>::value, "isLessOrEqual requires signed integral params");
T vm = numeric_limits<T>::max();
T sm = ~vm;
return !! ((x & ~y | ~(x ^ y) & ~((y & vm) + ~(x & vm) + 1)) & sm);
}
