[解決済み】ビット単位のLess than or Equal to

質問内容

コンテストのためという誤解があるようです。 私はある課題を解決しようとしているのですが、もう1時間もこの問題で行き詰まっています。

 /*
     * 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 をその 2 の補数として設定することができます ( ~x +1 で追加します。 Y . マイナスの場合は X よりも大きい。 Y . したがって、それを否定することによって、私は逆の効果を得ることができます。

同様に、私は以下のことを知っています。 !(x^y) は、次のものと同等です。 x==y . しかし して !(greater)|(!(x^y)) は適切な値を返しません。

私はどこで混乱しているのでしょうか？ちょっとしたロジックが抜けているような気がするのですが。

解決方法は？

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

説明：全体的な戦略は、入力の符号ビットを残りのビット（"値ビット）とは論理的に異なるものとして扱い、前の例と同様に値ビットだけに対して減算を実行することである。この場合、2つの入力が両方とも負または両方とも非負である場合にのみ減算を実行すればよい。これにより、算術オーバーフローを回避することができます。

のサイズが小さいので int 厳密には実行時に不明なので std::numeric_limits<int>::max() を値ビットの便利なマスクとして使用します。符号ビットのマスクは，単に値ビットのビット単位の否定である。

の実際の表現に目を向けると <= を分解すると、ビット単位のマスク sm の符号ビットの演算を行い、式の外側に押し出す。論理式の第1項 x & ~y が真であるとき x が負で y は非負である。次の項の第1因子 ~(x ^ Y) は両方が負のとき、または両方が非負のときに真となる。第二因子 ~((y & vm) + ~(x & vm) + 1)) が真である場合 y - x は非負であり、言い換えれば x <= y , 符号ビットを無視する . この2つの項は、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);
}