23

私は、2つのintのどちらが大きいかを本質的に確認する関数に取り組んでいます。渡されるパラメーターは232ビットintです。トリックは、許可される唯一の演算子です! ~ | & << >> ^（キャストなし、signed int、*、/、-など以外の他のデータ型）。

これまでの私の考えは^、2つのバイナリを一緒にして、1共有していない値のすべての位置を確認することです。次に、その値を取得して、1最も左にあるものを分離します。次に、そのうちのどれがその価値を持っているかを確認します。その場合、その値は大きくなります。（32ビットではなく8ビットのintを使用するとします）。渡された2つの値がで01011011あり、それらを01101001 使用^してを取得した場合00100010。 それから00100000言い換えれば、最初の数字 で結果を出して返したいと思います。の場合、最初の方が大きくなります。01xxxxxx -> 01000000&!!1#

助ける方法01xxxxxx -> 01000000や他の何かについて何か考えはありますか？

注意するのを忘れた：ifs、whiles、forsなどはありません...

4

8 に答える 8

20

これは、O（lg b）演算で符号なし整数を比較するループフリーバージョンです。ここで、bはマシンのワードサイズです。OPには、以外のデータ型は記載signed intされていないため、この回答の上部がOPの仕様を満たしていない可能性が高いことに注意してください。（下のスポイラーバージョン。）

キャプチャしたい動作は、最上位ビットの不一致が1foraと0forである場合であることに注意してくださいb。これについての別の考え方はa、平均の対応するビットよりも大きいビットは、の対応するビットよりも小さい前のビットがない限り、より大きいbということです。abab

そのためにa、の対応するビットよりも大きいすべてのビットを計算bし、同様に、の対応するビットaよりも小さいすべてのビットを計算しbます。ここで、「より小さい」ビットの下にあるすべての「より大きい」ビットをマスクしたいので、すべての「より小さい」ビットを取得し、それらをすべて右側に塗りつぶしてマスクを作成します。最上位ビットはすべてを設定します。最下位ビットまでの道は今1です。

ここで行う必要があるのは、単純なビットマスキングロジックを使用して、設定された「より大きい」ビットを削除することだけです。

結果の値は、の場合は0 、。のa <= b場合は非ゼロですa > b。後者の場合に使用したい1場合は、同様のスミアリングトリックを実行して、最下位ビットを確認することができます。

#include <stdio.h>

// Works for unsigned ints.
// Scroll down to the "actual algorithm" to see the interesting code.

// Utility function for displaying binary representation of an unsigned integer
void printBin(unsigned int x) {
    for (int i = 31; i >= 0; i--) printf("%i", (x >> i) & 1);
    printf("\n");
}
// Utility function to print out a separator
void printSep() {
    for (int i = 31; i>= 0; i--) printf("-");
    printf("\n");
}

int main()
{
    while (1)
    {
        unsigned int a, b;

        printf("Enter two unsigned integers separated by spaces: ");
        scanf("%u %u", &a, &b);
        getchar();

        printBin(a);
        printBin(b);
        printSep();

            /************ The actual algorithm starts here ************/

        // These are all the bits in a that are less than their corresponding bits in b.
        unsigned int ltb = ~a & b;

        // These are all the bits in a that are greater than their corresponding bits in b.
        unsigned int gtb = a & ~b;

        ltb |= ltb >> 1;
        ltb |= ltb >> 2;
        ltb |= ltb >> 4;
        ltb |= ltb >> 8;
        ltb |= ltb >> 16;

        // Nonzero if a > b
        // Zero if a <= b
        unsigned int isGt = gtb & ~ltb;

        // If you want to make this exactly '1' when nonzero do this part:
        isGt |= isGt >> 1;
        isGt |= isGt >> 2;
        isGt |= isGt >> 4;
        isGt |= isGt >> 8;
        isGt |= isGt >> 16;
        isGt &= 1;

            /************ The actual algorithm ends here ************/

        // Print out the results.
        printBin(ltb); // Debug info
        printBin(gtb); // Debug info
        printSep();
        printBin(isGt); // The actual result
    }
}

注：これは、両方の入力の最上位ビットを反転する場合、符号付き整数でも機能するはずですa ^= 0x80000000。

ネタバレ

すべての要件（25人以下のオペレーターを含む）を満たす回答が必要な場合：

int isGt(int a, int b)
{
    int diff = a ^ b;
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;

    diff &= ~(diff >> 1) | 0x80000000;
    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);

    return !!diff;
}

なぜそれがあなたにうまくいくのか説明は残しておきます。

于 2012-04-10T22:07:06.227 に答える
6

に変換する001xxxxxに00100000は、最初に以下を実行します。

x |= x >> 4;
x |= x >> 2;
x |= x >> 1;

（これは8ビット用です。32に拡張するには、シーケンスの開始時に8と16のシフトを追加します）。

これは私たちに残します00111111（このテクニックは「ビットスミアリング」と呼ばれることもあります）。次に、最初の1ビットを除くすべてを切り落とすことができます。

x ^= x >> 1;

を残し00100000ます。

于 2012-04-11T07:30:18.697 に答える
5

論理（&&、||）と比較（！=、==）を使用できる場合の符号なしバリアント。

int u_isgt(unsigned int a, unsigned int b)
{
    return a != b && (    /* If a == b then a !> b and a !< b.             */
               b == 0 ||  /* Else if b == 0 a has to be > b (as a != 0).   */
               (a / b)    /* Else divide; integer division always truncate */
           );             /*              towards zero. Giving 0 if a < b. */
}

!===簡単に削除できます。つまり、次のようになります。

int u_isgt(unsigned int a, unsigned int b)
{
    return a ^ b && (
               !(b ^ 0) ||
               (a / b)
           );
}

署名された場合は、次のように拡張できます。

int isgt(int a, int b)
{
    return
    (a != b) &&
    (
        (!(0x80000000 & a) && 0x80000000 & b) ||  /* if a >= 0 && b < 0  */
        (!(0x80000000 & a) && b == 0) ||
        /* Two more lines, can add them if you like, but as it is homework
         * I'll leave it up to you to decide. 
         * Hint: check on "both negative" and "both not negative". */
    )
    ;
}

よりコンパクトにすることができます/操作を排除します。（少なくとも1つ）しかし、わかりやすくするためにこのように配置します。

代わりに、0x80000000すなわち：

#include <limits.h>
static const int INT_NEG = (1 << ((sizeof(int) * CHAR_BIT) - 1));

これを使用してテストします。

void test_isgt(int a, int b)
{
    fprintf(stdout,
        "%11d > %11d = %d : %d %s\n",
        a, b,
        isgt(a, b), (a > b),
        isgt(a, b) != (a>b) ? "BAD!" : "OK!");
}

結果：

         33 >           0 = 1 : 1 OK!
        -33 >           0 = 0 : 0 OK!
          0 >          33 = 0 : 0 OK!
          0 >         -33 = 1 : 1 OK!
          0 >           0 = 0 : 0 OK!
         33 >          33 = 0 : 0 OK!
        -33 >         -33 = 0 : 0 OK!
         -5 >         -33 = 1 : 1 OK!
        -33 >          -5 = 0 : 0 OK!
-2147483647 >  2147483647 = 0 : 0 OK!
 2147483647 > -2147483647 = 1 : 1 OK!
 2147483647 >  2147483647 = 0 : 0 OK!
 2147483647 >           0 = 1 : 1 OK!
          0 >  2147483647 = 0 : 0 OK!
于 2012-04-10T23:49:06.423 に答える
2

Kaganarの小さいisGt関数の完全にブランチレスバージョンは次のようになります。

int isGt(int a, int b)
{
    int diff = a ^ b;
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;

    //1+ on GT, 0 otherwise.
    diff &= ~(diff >> 1) | 0x80000000;
    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);

    //flatten back to range of 0 or 1.
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff &= 1;

    return diff;
}

これは、実際の計算（MSVC 2010コンパイラ、x86アーチ上）用に約60命令でクロックインし、さらに関数のプロローグ/エピローグ用に10スタック操作程度を追加します。

于 2013-01-06T07:19:55.667 に答える
0

編集：

さて、コードに問題がありましたが、修正して以下の作業を行いました。

この補助関数は、数値のn番目の有効数字を比較します。

int compare ( int a, int b, int n )
{
    int digit = (0x1 << n-1);
    if ( (a & digit) && (b & digit) )
       return 0; //the digit is the same

    if ( (a & digit) && !(b & digit) )
       return 1; //a is greater than b

    if ( !(a & digit) && (b & digit) )
       return -1; //b is greater than a
}

以下は、より大きな数を再帰的に返す必要があります。

int larger ( int a, int b )
{
    for ( int i = 8*sizeof(a) - 1 ; i >= 0 ; i-- )
    {
       if ( int k = compare ( a, b, i ) )
       {
           return (k == 1) ? a : b;
       }
    }
    return 0; //equal
}
于 2012-04-10T21:39:35.813 に答える
0

他の人の宿題をやりたくないのと同じくらい、これに抵抗できませんでした。:)他の人がもっとコンパクトなものを考えることができると確信しています。しかし、ここに私のものがあります。 。

編集：しかし、いくつかのバグがあります。私はそれをOPに任せて見つけて修正します。

    #include<unistd.h>
    #include<stdio.h>
    int a, b, i, ma, mb, a_neg, b_neg, stop;

    int flipnum(int *num, int *is_neg) {
        *num = ~(*num) + 1;
        *is_neg = 1;

        return 0;
    }

    int print_num1() {
        return ((a_neg && printf("bigger number %d\n", mb)) ||
             printf("bigger number %d\n", ma));
    }

    int print_num2() {
        return ((b_neg && printf("bigger number %d\n", ma)) ||
             printf("bigger number %d\n", mb));
    }

    int check_num1(int j) {
        return ((a & j) && print_num1());
    }

    int check_num2(int j) {
        return ((b & j) && print_num2());
    }

    int recursive_check (int j) {
        ((a & j) ^ (b & j)) && (check_num1(j) || check_num2(j))  && (stop = 1, j = 0);

        return(!stop && (j = j >> 1) && recursive_check(j));
    }

    int main() {
        int j;
        scanf("%d%d", &a, &b);
        ma = a; mb = b;

        i = (sizeof (int) * 8) - 1;
        j = 1 << i;

        ((a & j) && flipnum(&a, &a_neg));

        ((b & j) && flipnum(&b, &b_neg));

        j = 1 << (i - 1);

        recursive_check(j);

        (!stop && printf("numbers are same..\n"));
    }
于 2012-04-11T06:55:31.710 に答える
0

私は3つの操作で解決策があると思います：

最初の数値に1を加算し、表現できる最大の数値（すべて1）から減算します。その番号を2番目の番号に追加します。オーバーフローした場合、最初の数値は2番目の数値よりも小さくなります。

これが正しいかどうかは100％わかりません。つまり、1を追加する必要はないかもしれません。オーバーフローをチェックできるかどうかはわかりません（そうでない場合は、最後のビットを予約して、最後に1かどうかをテストしてください）。

于 2015-05-11T05:23:32.600 に答える
-1

編集：制約により、下部の単純なアプローチは無効になります。より大きな値を検出するために、バイナリ検索関数と最終比較を追加しています。

unsigned long greater(unsigned long a, unsigned long b) {
    unsigned long x = a;
    unsigned long y = b;
    unsigned long t = a ^ b;
    if (t & 0xFFFF0000) {
        x >>= 16;
        y >>= 16;
        t >>= 16;
    }
    if (t & 0xFF00) {
        x >>= 8;
        y >>= 8;
        t >>= 8;
    }
    if (t & 0xf0) {
        x >>= 4;
        y >>= 4;
        t >>= 4;
    }
    if ( t & 0xc) {
        x >>= 2;
        y >>= 2;
        t >>= 2;
    }
    if ( t & 0x2) {
        x >>= 1;
        y >>= 1;
        t >>= 1;
    }
    return (x & 1) ? a : b;
}

アイデアは、関心のある単語の最も重要な半分から始めて、そこにセットビットがあるかどうかを確認することです。ある場合は、最下位の半分は必要ないため、不要なビットをシフトします。そうでない場合は、何もしません（とにかく半分はゼロなので、邪魔になりません）。シフトされた量を追跡できないため（加算が必要になります）、元の値もシフトして、最終的andに大きな数を決定できるようにします。対象のビットをビット位置0に折りたたむまで、前のマスクの半分のサイズでこのプロセスを繰り返します。

ここでは、わざと同じケースを追加しませんでした。

古い答え：

宿題にはおそらく最も簡単な方法が最適です。不一致のビット値を取得したら、0x80000000（またはワードサイズに適した最大ビット位置）の別のマスクから始めて、不一致の値に設定されているビットに到達するまでこれを右にシフトし続けます。右シフトが0になる場合、不一致値は0です。

より大きな数を決定するために必要な最後のステップをすでに知っていると思います。

于 2012-04-10T21:41:33.937 に答える