按位小于或等于

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 。但是，执行 !(greater)|(!(x^y)) 不会返回正确的值。

我在哪里搞砸了？我觉得我错过了一点逻辑。

原文由 user4049003 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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 ，这是对这个的否定。

     /*
     * 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 ， _忽略符号位_。这两个术语是 or’d，所以使用 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);
}

原文由 ThomasMcLeod 发布，翻译遵循 CC BY-SA 3.0 许可协议

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

原文由 Yanagar1 发布，翻译遵循 CC BY-SA 3.0 许可协议