Bit Sequenzen erstellen / ausgeben



  • Ich habe eine Aufgabe, die ich nicht gelöst bekommen:
    Ich hab eine 32 bit Variable "data", erstelle ne zweite Variable "mask", da ich die indices 1,2,5,13,14,16,17,20
    überprüfen möchte, ob diese jeweils gesetzt sind(mit "&"" bitweise verknüpfen). Wie das geht, ist mir klar.

    Nun zu meinem Problem: Das Ergebnis (8 bit Wert = uint8_t) möchte ich in einer neuen Variable "retVal" abspeichern, so wie hier drunter in "Example" gezeigt.
    Hab aber keinen Peil, verknüpfe ich erst die beiden 32bit Variablen mit &, erhalte dann das Ergebnis in einer neuen 32 bit Variable und ziehe anschließend die besagten Indexe aus der Variable raus und speichere die 8 rausgezogenen indices Variable. Falls ja, wie ziehe ich denn die besagten raus?
    Irgendwie hab ich Brett vorm Kopf bzw. mangelhafte Erfahrung.

    • function extracts a sequence of bits from the argument data. see example
    • The set bits in mask are copied to an unsigned char variable.
    • Example:
    • data = 0101 0101 1010 1010 0101 0101 1010 1010 = 0x55aa55aa
    • mask = 0000 0000 0001 0011 0011 0000 0010 0110 = 0x00133026
    • retVal = 0 10 01 1 01 = 0x4d
    • PARAMETERS:

    • uint32_t data: a 32 bit integer that will be operated on
    • uint32_t mask: the bit packed data that indicates the bits to be copied to result
    • RETURNS:

    • The extracted sequence stored in a single unsigned char.

    */
    // Mein Code (wahrscheinlich völliger Murks):
    uint8_t op_bit_get_sequence(uint32_t data, uint32_t mask)
    {
    uint8_t retval = 0;
    uint32_t byte_mask = ((1 << 1) | (1 << 2) | (1 << 5) | (1 << 12) | (1 << 13) | (1 << 16) | (1 << 17) | (1 << 20));

    data = data & byte_mask;
    mask = mask & byte_mask;
    
    op_print_byte_hex(data);
    op_print_byte(data);
    printf("\n");
    op_print_byte_hex(mask);
    op_print_byte(mask);
    printf("\n");
    
    retval = mask & data;
    
    return retval;
    

    }

    int main(void)
    {
    printf("\n*** Testing your op_bit_get_sequence function..\n");

    printf("Getting sequence... Should be 0x4d, was 0x%02X\n", op_bit_get_sequence(0x55aa55aa, 0x00133026));
    
    return 0;
    

    }



  • So wie ich die Aufgabe anhand des Beispiels verstehe, sollst du nur die zu den in mask gesetzten Bits (d.h. die 1-Bits) überprüfen und dann die an gleichem Index in data zugehörigen Bits in retVal kopieren.
    Da der Rückgabetyp nur 8 Bit hat, darf die Maske auch nur (maximal) 8 gesetzte Bits haben (wie im Beispiel).

    Zum Lösen mußt du daher durch die Bits der mask mit einer Schleife "iterieren" (mit dem Index als Laufvariable und zwar vom höchsten Index 31 bis zum niedrigsten 0) und dann bei den gesetzten Bits die zugehörigen Bits aus data in retVal (von rechts) hereinrotieren (mit den Operatoren << und |).

    PS: In deinem bisherigen Code hast du die Maske ja doppelt angegeben (einmal als Hexwert und einmal in der Funktion per Indizes zusammengesetzt) - ist also unnötig.
    Außerdem hast du in der Beschreibung Indizes 13, 14 anstatt korrekt (wie im Code) 12, 13 angegeben - hat mich zuerst ein bißchen verwirrt.



  • Edit: Beschreibung des Algos ergänzt

    Im Prinzip ist das ziemlich simpel, du brauchst eine Bitmaske, in der nur ein einziges Bit gesetzt ist, und schiebst die in einer Schleife über den ganzen Wertebereich. In jedem Schleifendurchlauf prüfst du dann, ob in der Eingangsmaske das entsprechende Bit gesetzt ist. Falls das der Fall ist, musst du das Bit aus den Eingangsdaten in das Ergebnis übernehmen.
    Bitte versuch das selbst umzusetzen, bevor du den Code unten einfach kopierst.

    @Th69
    Besser?

    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    // Spoiler-Verhinderungs-Kommentar
    
    #include <cstdint>
    
    std::uint8_t op_get_bit_sequence( std::uint32_t data, std::uint32_t mask )
    {
       std::uint8_t result = 0;
    
       // von "links" anfangen zu testen
       std::uint32_t test_mask = 1 << 31;
      
       // Kompakter ginge auch
       // for( std::uint32_t test_mask = 1 << 31; test_mask > 0; test_mask >>= 1 )
    
       for( int i = 31; i >= 0; --i )
       {
          // ist das Bit relevant?
          if( mask & test_mask) 
          {
             // ja, bisheriges Ergebnis nach links schieben
             result <<= 1;
    
             // Zustand des relevanten Bits in Ergebnis übernehmen
             result |= (data & test_mask) ? 1 : 0;
          }
          // Testmaske nach rechts schieben
          test_mask >>= 1;
       }
       return result;
    }
    

    Normalerweise werden hier keine fertigen Lösungen gepostet, aber in diesem Fall sagt der Code mehr als 1000 Worte. Denke ich.



  • @DocShoe: So lernt der OP aber nicht, wie man Algorithmen selbst entwickelt...



  • Vielen Dank für die Antworten. Der Code hilft mir sehr. Jetzt habe ich eine Herangehensweise. Mein Hauptproblem war, das ich zwar theoretisch wusste, wie man shiftet, aber ich durch mangelnde Erfahrung nicht auf die Idee kam, den ersten Wert ganz nach rechts zu stecken und dann den ganzen Klumpatsch immer eins weiter nach links zu shiften. Jetzt, wo ichs gesehen habe, ists mir natürlich klar. Ich hatte nur im Kopf, ich muss über ein Array iterieren und dann Wert für Wert ins nächste Index speichern. Nochmals vielen Dank für die Unterstützung.



  • Hier nochmal ne alternative Variante. Nicht wirklich einfacher, aber vielleicht trotzdem interessant.

    unsigned extract_bits(unsigned data, unsigned mask) {
        unsigned result = 0;
        unsigned out_bit = 1;
        while (data & mask) {
            if (mask & 1) {
                if (data & 1) {
                    result |= out_bit;
                }
                out_bit <<= 1;
            }
            data >>= 1;
            mask >>= 1;
        }
        return result;
    }
    

    Kleine Vorteile:

    1. Bricht ab sobald es nichts mehr zu extrahieren gibt
    2. Ausser dem Variablen-Typ gibt es nichts anzupassen wenn der Code für andere Breiten (z.B. 64 Bit) verwendet werden soll

    Wobei beides vermutlich wörscht ist. Bzw. (1) kann sogar ein Nachteil sein (timing/side-channel Attacken).


Log in to reply