按位小于或等于 [英] Bitwise Less than or Equal to

问题描述

似乎有些误解，认为这是为了比赛. 我正在尝试完成一项任务，而现在我已经坚持了一个小时.

There seems to be some kind of misconception that this is for a contest. I'm trying to work through an assignment and I've been stuck on this for an hour now.

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

I'm only able to use bitwise operators, as instructed in the comments. I cannot figure out how to solve x <= y;

我的思维过程是，我可以将x设置为其补码(~x +1)，然后将其与Y相加.如果它为负，则X大于Y.因此，通过否定我可以得到相反的效果.

My thought process is that I can set x as its two's complement (~x +1) and add it with Y. If it is negative, X is greater than Y. Therefore, by negating that I can get the opposite effect.

同样，我知道!(x^y)等同于x==y. 然而， !(greater)|(!(x^y))不能返回正确的值.

Similarly, I know that !(x^y) is equivalent to x==y. However, doing !(greater)|(!(x^y)) does not return the proper value.

我在哪里弄糟?我觉得我缺少一点逻辑.

Where am I messing up? I feel like I'm missing a small bit of logic.

推荐答案

如果x > y，则y - x或(y + (~x + 1))将为负，因此高位将为1，否则将为0.但是我们想要x <= y，这就是它的取反.

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, which is the negation of this.

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

更好的是，删除移位运算符并在高位使用位掩码:

Even better, drop the shift operator and use a bit mask on the high bit:

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

作为注释者的指示，上述版本容易出现算术溢出错误.这是涵盖极端情况的另一个版本.

As a commenter pointer out, the above version is susceptible to arithmetic overflow errors. Here is another version that covers the edge cases.

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

说明:总体策略是将输入的符号位与其余的位(值位)在逻辑上区别对待，并像前面的示例一样仅对值位执行减法.在这种情况下，我们只需要在两个输入均为负或均为非负的情况下进行减法运算.这样可以避免算术溢出情况.

Explanation: the overall strategy is to treat the sign bit of the inputs as logically distinct from the rest of the bits, the "value bits," and perform the subtraction as in the previous example on just the value bits. In this case, we need only perform the subtraction where the two inputs are either both negative or both non-negative. This avoids the arithmetic overflow condition.

由于严格来讲int的大小在运行时未知，因此我们将std::numeric_limits<int>::max()用作值位的便捷掩码.符号位的掩码只是值位的按位求反.

Since the size of int strictly speaking is unknown at run time, we use std::numeric_limits<int>::max() as a convenient mask for the value bits. The mask of the sign bit is simply the bit-wise negation of the value bits.

转到<=的实际表达式，我们将每个子表达式中符号位的按位掩码sm分解出来，并将操作推到表达式的外部.当x为负且y为非负时，逻辑表达式x & ~y的第一项为true.当下一项~(x ^ Y)的第一个因子均为负或均为非负时，则为true.当y - x为非负数时，换句话说，x <= y，忽略符号位，第二个因子~((y & vm) + ~(x & vm) + 1))为真.这两个术语是或"的，因此使用c ++逻辑表达式语法可以得到:

Turning to the actual expression for <=, we factor out the bit-wise mask sm of the sign bit in each of the sub-expressions and push the operation to the outside of the expression. The first term of the logical expression x & ~y is true when x is negative and y is non-negative. The first factor of the next term ~(x ^ Y) is true when both are negative or both are non-negative. The second factor ~((y & vm) + ~(x & vm) + 1)) is true when y - x is non-negative, in other words x <= y, ignoring the sign bit. The two terms are or'd, so using c++ logical expression syntax we have:

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

!!最外面的运算符将升高的符号位转换为1.最后，这是现代C ++模板化的constexpr版本:

The !! outermost operators convert the raised sign bit to a 1. Finally, here is the Modern C++ templated 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);
}

这篇关于按位小于或等于的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！