webentwicklung-frage-antwort-db.com.de

Bitweise Operationen, die größer als Operator sind

Ich arbeite an einer Funktion, die im Wesentlichen sieht, welcher von zwei Ints größer ist. Die übergebenen Parameter sind 2 32-Bit-Werte. Der Trick besteht darin, dass die einzigen Operatoren ! ~ | & << >> ^ sind (kein Casting, andere Datentypen außer "int", *, /, - usw.).

Meine bisherige Idee ist, die beiden Binärdateien zusammen zu ^, um alle Positionen der 1-Werte zu sehen, die sie nicht gemeinsam haben. Ich möchte dann diesen Wert nehmen und den 1 am weitesten links von Ihnen isolieren. Dann sehen Sie, von wem dieser Wert diesen Wert hat. Dieser Wert ist dann der größere Wert. (Angenommen, wir verwenden 8-Bit-Ints anstelle von 32-Bit.). Wenn die beiden übergebenen Werte 01011011 und 01101001 Waren, verwendete ich ^. Um sie zu bekommen 00100010. Ich möchte dann 00100000 mit anderen Worten 01xxxxxx -> 01000000 machen. Dann & mit der ersten Nummer !! das Ergebnis und das Ergebnis zurückgeben. Wenn es 1 ist, ist der erste # größer.

Irgendwelche Gedanken, wie man 01xxxxxx -> 01000000 oder irgendetwas anderes helfen kann?

Vergessen zu beachten: kein Wenn, Whiles, Fors etc ...

18
Gekctek

Hier ist eine schleifenfreie Version, die vorzeichenlose Ganzzahlen in O (lg b) -Vorgängen vergleicht, wobei b die Wortgröße der Maschine ist. Beachten Sie, dass das OP keine anderen Datentypen als signed int enthält. Daher ist es wahrscheinlich, dass der obere Teil dieser Antwort nicht den Spezifikationen des OP entspricht. (Spoiler-Version wie unten.)

Beachten Sie, dass das Verhalten, das wir erfassen möchten, ist, wenn der signifikanteste Bitunterschied 1 für a und 0 für b ist. Eine andere Möglichkeit, darüber nachzudenken, ist, dass jedes Bit in a größer ist als das entsprechende Bit in b bedeutet, dass a größer ist als b, sofern in a kein früheres Bit vorhanden war, das weniger als das entsprechende Bit in b war.

Zu diesem Zweck berechnen wir alle Bits in a, die größer als die entsprechenden Bits in b sind, und berechnen auch alle Bits in a weniger als die entsprechenden Bits in b. Wir möchten nun alle "Größer" -Bits ausblenden, die unter allen "Weniger als" -Bits liegen. Deshalb nehmen wir alle "Weniger als" -Bits und schmieren sie alle nach rechts, wobei eine Maske entsteht: das höchstwertige Bit setzt alles Der Weg zum niederwertigsten Bit ist jetzt 1.

Jetzt müssen wir nur noch die 'Größer als' Bits entfernen, indem Sie die einfache Bitmaskierungslogik verwenden.

Der resultierende Wert ist 0, wenn a <= b und ungleich Null, wenn a > b. Wenn wir möchten, dass es 1 ist, können wir im letzteren Fall einen ähnlichen Trick ausführen und einfach das niedrigstwertige Bit betrachten.

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

Hinweis: Dies sollte auch für vorzeichenbehaftete Ganzzahlen funktionieren, wenn Sie das oberste Bit auf beide der Eingänge setzen, z. a ^= 0x80000000.

Spoiler

Wenn Sie eine Antwort wünschen, die alle Anforderungen erfüllt (einschließlich 25 oder weniger Operatoren):

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

Ich werde erklären, warum es bei Ihnen funktioniert.

18
Kaganar

Ein ohne Vorzeichen Variante, da man logisch (&&, ||) und Vergleich (! =, ==) verwenden kann.

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. */
}

!= und == können leicht eliminiert werden, d. h .:

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

Zum unterzeichnet man könnte dann so etwas erweitern:

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

Kann kompakter sein/Operationen eliminieren. (mindestens eine), aber zur Klarheit so formulieren.

Anstelle von 0x80000000 könnte man sagen:

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

Verwenden Sie dies zum Testen:

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!");
}

Ergebnis:

         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!
5
Morpfh

Um 001xxxxx in 00100000 zu konvertieren, führen Sie zuerst Folgendes aus:

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

(Dies ist für 8 Bits; um es auf 32 zu erweitern, fügen Sie zu Beginn der Sequenz Verschiebungen um 8 und 16 hinzu).

Dies führt zu 00111111 (diese Technik wird manchmal als "Bit-Smearing" bezeichnet). Wir können dann alle außer dem ersten 1 Bit abhacken:

x ^= x >> 1;

uns mit 00100000 verlassen.

4
caf

Eine vollständig branchless version von Kaganars kleinere isGt-Funktion könnte folgendermaßen aussehen:

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

Dies entspricht rund 60 Anweisungen für die eigentliche Berechnung (MSVC 2010-Compiler auf einem x86-Arch) sowie weitere 10 Stack-Operationen für den Prolog/Epilog der Funktion.

2
Philip Conrad

So sehr ich auch nicht die Hausaufgaben eines anderen machen möchte, ich konnte dieser nicht widerstehen .. :) Ich bin sicher, dass sich andere eine kompaktere vorstellen können ... aber hier ist meine Arbeit gut, einschließlich negativer Zahlen. .

Edit: Es gibt jedoch ein paar Fehler. Ich werde es dem OP überlassen, es zu finden und zu reparieren.

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

Ich denke, ich habe eine Lösung mit 3 Operationen:

Fügen Sie der ersten Zahl eine hinzu, und ziehen Sie sie von der größtmöglichen Zahl ab, die Sie darstellen können (alle 1). Fügen Sie diese Nummer zur zweiten Nummer hinzu. Wenn es überläuft, ist die erste Zahl kleiner als die zweite.

Ich bin nicht 100% sicher, ob dies richtig ist. Das heißt, Sie müssen möglicherweise keine 1 hinzufügen, und ich weiß nicht, ob es möglich ist, den Überlauf zu überprüfen (wenn nicht, dann reservieren Sie das letzte Bit und testen Sie, ob es am Ende 1 ist.)

0
Houshalter

BEARBEITEN:

Okay, es gab einige Probleme mit dem Code, aber ich habe ihn überarbeitet und die folgenden Arbeiten funktionieren.

Diese Hilfsfunktion vergleicht die Zahlen 'n'-te signifikante Ziffer:

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
}

Die folgende Zahl sollte rekursiv die größere Zahl zurückgeben:

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
}
0
Luchian Grigore