按位小於或等於

似乎有某種誤解，認爲這是一場比賽。我正試圖完成一項任務，現在我一直堅持這一個小時。按位小於或等於

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

    }

我只能按照註釋中的說明使用按位運算符。我不知道如何解決x < = y;

我的思考過程是，我可以將x設置爲其二的補碼（〜x +1）並將其與Y相加。如果它是負數，則X大於Y.因此，通過否定我可以得到相反的結果影響。

同樣，我知道！（x^y）等價於x == y。但是，正在執行！（更大）|（！（x^y））不會返回正確的值。

我在哪裏搞亂了？我覺得我錯過了一點邏輯。

來源

2017-01-31 Whatamia

@SamVarshavchik難不成這是一個在線競賽...... 我卡上的分配，我不知道從哪裏搬到這裏。 – Whatamia

選民關閉：這個問題太廣泛了？似乎相當明確給我。 – ThomasMcLeod

如果x > y，然後y - x或(y + (~x + 1))將是負面的，因此，高位爲1，否則爲0。但是，我們希望x <= y，這是該否定。

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

更好的是，丟棄該移位運算符並在高比特使用一個位掩碼：

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

編輯：

作爲評論者指針移出，上述版本是易感算術溢出錯誤。這是覆蓋邊緣情況的另一個版本。

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

說明：整體策略是治療的輸入作爲邏輯上的位，所述的其餘部分不同的符號位「值的位」，並於剛剛值在前面的例子中執行減法位。在這種情況下，我們只需要在兩個輸入都是負數或兩個都是負數的情況下執行減法。這避免了算術溢出情況。

由於嚴格來說int的大小在運行時是未知的，我們使用std::numeric_limits<int>::max()作爲值位的方便掩碼。符號位的掩碼就是數值位的按位取反。

談到<=的實際表達式，我們計算出每個子表達式中符號位的按位掩碼sm，並將操作推送到表達式的外部。邏輯表達式x & ~y的第一項在x爲負數且y非負時爲真。下一期~(x^Y)的第一個因素在兩者均爲負數或兩者均爲非負時爲真。第二個因子~((y & vm) + ~(x & vm) + 1))在y - x爲非負值時爲真，換句話說x <= y,忽略符號位。這兩個詞進行邏輯或運算，因此，使用C++的邏輯表達式語法，我們有：

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

的!!最外運營商凸起符號位轉換爲1。最後，這裏是現代C++模板constexpr版本：

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

來源

2017-01-31 03:15:39 ThomasMcLeod

這很好，但是當'y'是補碼的最大值（0111 ... 111），'x'是補碼的最小值（1000 ... 000）時，它會崩潰。 –

@KennethWorden，編輯部分下的版本應該解決您的有效問題。 – ThomasMcLeod

這些功能並不完全是因爲溢出的工作，所以這就是我解決了這個問題。呃...

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;

來源

2017-02-03 03:34:45 Yanagar1

按位小於或等於

回答

相關問題