Побитовое меньше или равно

Question

Кажется, что есть какое-то заблуждение, что это для конкурса. Я пытаюсь выполнить задание, и я застрял на нем в течение часа.

/* 
    * 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)) не возвращает правильное значение.

Куда я перепутаю? Я чувствую, что у меня мало логики.

Answer 1

Если 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); 
    } 

EDIT:

Как комментатора указатель вне, выше версия восприимчив к арифметическим ошибкам переполнения. Вот еще одна версия, которая охватывает случаи краев.

#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, игнорируя знак знака. Эти два термина OR-нут, поэтому использование C++ логический синтаксис выражения мы имеем:

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

В !! внешние операторы преобразуют поднятую знаковый бит в 1.Наконец, здесь Modern 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); 
} 

Answer 2

Эти функции не в полной мере работать из-за переполнения, так что, как я решил проблему. Эх ...

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;