Bitweise Weniger als oder Gleich

Wenn x > y, dann y - x oder (y + (~x + 1)) negativ sein wird, daher die hohe bit auf 1, andernfalls ist es 0. Aber wir wollen x <= y, das ist die negation dieser.

    /*
     * 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);
    }

Besser noch, löschen Sie den shift-operator und verwenden eine bit-Maske, die auf die hohe bit:

    int isLessOrEqual(int x, int y)
    {
        return !((y + (~x + 1)) & 0x80000000);
    }

EDIT:

Als Kommentator Zeiger aus, die obige version ist anfällig für arithmetischen überlauf Fehler. Hier ist eine andere version, die sich über die Grenzfälle.

#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);
}

Erläuterung: die Allgemeine Strategie zur Behandlung der Vorzeichen-bit der Eingänge als logisch getrennt von dem rest der bits, die "Wert-bits", und führen Sie die Subtraktion wie im vorherigen Beispiel, sich nur auf die Wert-bits. In diesem Fall brauchen wir nur die Subtraktion, wo die beiden Eingänge sind entweder beide negativ oder beide nicht-negativ. Dies vermeidet die arithmetischen überlauf.

Da die Größe der int streng genommen ist unbekannt, zur Laufzeit, verwenden wir std::numeric_limits<int>::max() als eine bequeme Maske für den Wert-bits. Die Maske des Vorzeichen-bit ist einfach die bit-Weise negation der Wert-bits.

Drehen, um das eigentliche Ausdruck für <= wir Faktor der bit-wise Maske sm des Vorzeichen-bit in jedem der sub-Ausdrücke und schieben Sie den Vorgang auf der Außenseite des Ausdrucks. Der erste Ausdruck des logischen Ausdrucks x & ~y ist wahr, wenn x negativ ist und y ist nicht-negativ. Der erste Faktor, der neben Begriff ~(x ^ Y) ist wahr, wenn beide negativ sind oder beide nicht negativ sind. Der zweite Faktor ~((y & vm) + ~(x & vm) + 1)) ist wahr, wenn y - x ist nicht-negativ, in anderen Worten x <= y, ignorieren das Vorzeichen-bit. Die beiden Begriffe sind oder würde, also mit c++ logische Ausdruck-syntax, die wir haben:

x < 0 && y >= 0 || (x < 0 && y < 0 || x >= 0 && y >= 0) && y - x >= 0

Den !! äußersten Operatoren konvertieren die erhöhte Vorzeichen-bit auf ein 1. Schließlich, hier ist der Modernen C++ - Vorlagen 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);
}

Wirklich genossen Yanagar1 Antwort, die ist sehr einfach zu verstehen.

Eigentlich können wir entfernen, die shift-Operatoren und die Verwendung De-Morgan-Gesetze, die zu einer Verringerung der Anzahl der Betreiber von 15 auf 11.

long isLessOrEqual(long x, long y) {
  long sign = (x ^ y);               //highest bit will be 1 if different sign
  long diff = sign & x;              //highest bit will be 1 if diff sign and neg x
  long same = sign | (y + (~x + 1)); //De Morgan's Law with the following ~same
                                     //highest bit will be 0 if same sign and y >= x
  long result = !!((diff | ~same) & 0x8000000000000000L); //take highest bit(sign) here
  return result;
}