Bitweise kleiner als oder gleich

Question

Es scheint eine Art Missverständnis zu sein, dass dies für einen Wettbewerb ist. Ich versuche, eine Aufgabe zu bearbeiten, und ich stehe jetzt seit einer Stunde fest.

/* 
    * 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) 
    { 
     int greater = (x + (~y + 1))>>31 & 1; 
     return !(greater)|(!(x^y)); 

    } 

Ich bin nur in der Lage, bitweise Operatoren zu verwenden, wie in den Kommentaren angewiesen. Ich kann nicht herausfinden, wie zu lösen x < = y;

Mein Denkprozess ist, dass ich x als sein Zweierkomplement (~ x +1) setzen und mit Y hinzufügen kann. Wenn es negativ ist, ist X größer als Y. Indem ich das negiere, kann ich das Gegenteil erreichen bewirken.

Ebenso weiß ich, dass! (X^y) ist äquivalent zu x == y. doing! (Größer) | (! (X^y)) gibt jedoch nicht den richtigen Wert zurück.

Wo verarsche ich? Ich habe das Gefühl, dass mir ein bisschen Logik fehlt.

Answer 1

Wenn x > y, dann y - x oder (y + (~x + 1)) negativ sein wird, damit das hohe Bit wird 1 sein, sonst ist es 0 sein wird, aber wir wollen x <= y, welche die Negation dieser ist.

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

Noch besser ist, den Shift-Operator fallen und eine Bitmaske auf dem hohe Bit verwenden:

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

EDIT:

Als Kommentator aus Zeigern, die obige Version ist anfällig zu arithmetischen Überlauffehlern. Hier ist eine weitere Version, die die Randfälle abdeckt.

#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 Gesamtstrategie ist das Vorzeichenbit der Eingänge als logisch getrennt vom Rest der Bits, der „Wert Bits“, und führen Sie die Subtraktion, wie im vorherigen Beispiel auf nur den Wert zu behandeln Bits. In diesem Fall müssen wir nur die Subtraktion durchführen, wo die zwei Eingaben entweder beide negativ oder beide nicht negativ sind. Dies vermeidet die arithmetische Überlaufbedingung.

Da die Größe von int streng genommen zur Laufzeit unbekannt ist, verwenden wir std::numeric_limits<int>::max() als eine bequeme Maske für die Wert-Bits. Die Maske des Vorzeichenbits ist einfach die bitweise Negation der Wertbits.

Wir wenden uns dem tatsächlichen Ausdruck für <= zu, faktorieren die bitweise Maske sm des Vorzeichen-Bits in jedem der Unterausdrücke aus und schieben die Operation nach außerhalb des Ausdrucks. Der erste Ausdruck des logischen Ausdrucks x & ~y ist wahr, wenn x negativ ist und y nicht negativ ist. Der erste Faktor des nächsten Terms ~(x^Y) gilt, wenn beide negativ oder beide nicht negativ sind. Der zweite Faktor ~((y & vm) + ~(x & vm) + 1)) ist wahr, wenn y - x nicht negativ ist, mit anderen Worten , ignoriert das Vorzeichenbit. Die beiden Begriffe ODER-verknüpft werden, so C++ logische Ausdruck Syntax haben wir:

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

Die !! äußersten Operatoren wandeln die erhöhte Vorzeichenbit zu einem 1.Schließlich ist hier die Moderne C++ Templat 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); 
} 

Answer 2

Diese Funktionen nicht vollständig, weil der Überlauf arbeiten, also das ist, wie ich das Problem gelöst. Eh ...

int isLessOrEqual(int x, int y) { 
int diff_sgn = !(x>>31)^!(y>>31);  //is 1 when signs are different 
int a = diff_sgn & (x>>31);   //diff signs and x is neg, gives 1 
int b = !diff_sgn & !((y+(~x+1))>>31); //same signs and difference is pos or = 0, gives 1 
int f = a | b; 
return f;