Wie erstellt man Maske mit den wenigsten signifikanten Bits auf 1 in C

Question

Kann mir bitte jemand diese Funktion erklären?

Eine Maske mit dem am wenigsten signifikanten n Bits auf 1 gesetzt

Ex:

n = 6 -> 0x2F, n = 17 -> 0x1FFFF // Ich bekomme diese nicht an alle, vor allem wie n = 6 -> 0x2F

Auch was ist eine Maske?

Answer 1

Der übliche Weg ist ein 1 zu nehmen, und verschiebe es nach links n Bits. Das gibt Ihnen etwas wie: 00100000. Dann subtrahiere eins davon, was das gesetzte Bit löscht, und setze alle weniger signifikanten Bits, so dass wir in diesem Fall erhalten würden: 00011111.

Normalerweise wird eine Maske mit bitweisen Operationen verwendet, insbesondere and. Sie würden die obige Maske verwenden, um die 5 niedrigstwertigen Bits selbst zu erhalten, isoliert von allem anderen, was möglicherweise vorhanden ist. Dies ist insbesondere üblich, wenn es sich um Hardware handelt, die oft ein einziges Hardware-Register aufweist, das Bits enthält, die eine Anzahl von völlig getrennten, nicht verwandten Mengen und/oder Flags darstellen.

Answer 2

Ich glaube, Ihr erstes Beispiel sollte 0x3f sein.

0x3f ist hexadezimale Notation für die Nummer, die 63111111 in binär ist, so dass im letzten 6 Bits (die niedrigstwertigen 6 Bits) an 1 eingestellt sind.

Das folgende kleine C-Programm wird die richtige Maske berechnen:

#include <stdarg.h> 
#include <stdio.h> 

int mask_for_n_bits(int n) 
{ 
    int mask = 0; 

    for (int i = 0; i < n; ++i) 
     mask |= 1 << i; 

    return mask; 
} 

int main (int argc, char const *argv[]) 
{ 
    printf("6: 0x%x\n17: 0x%x\n", mask_for_n_bits(6), mask_for_n_bits(17)); 
    return 0; 
} 

Answer 3

0x2F ist 0010 1111 binär - die 0x3f sein soll, die 0011 1111 binär ist und welches die 6 am wenigsten signifikanten Bits gesetzt.

In ähnlicher Weise ist 0x1FFFF0001 1111 1111 1111 1111 im Binärformat, das die 17 niedrigstwertigen Bits gesetzt hat.

A „Maske“ ist ein Wert, der einen bitweise Operator mit einem anderen Wert kombiniert werden sollte, verwendet, wie &, | oder ^ individuell eingestellt, ungesetzt, flip oder unverändert lassen, die Bits in dem anderen Wert.

Zum Beispiel, wenn Sie die Maske 0x2F mit einem Wert kombinieren n mit dem & Operator, wird das Ergebnis hat Nullen in alle, aber die sechs am wenigsten signifikanten Bits, und die 6 Bits vom Wert n unverändert kopiert werden.

Im Fall einer & Maske ein binäres 0 in der Maske bedeutet „bedingungslos das Ergebnis Bit auf 0 gesetzt“ und ein 1 bedeutet „zum Eingangswert Bit das Ergebnis gesetzt“. Für eine | Maske setzt eine 0 in der Maske das Ergebnis Bit dem Eingangsbit und eine 1 setzt bedingungslos das Ergebnisbit zu 1 und für eine ^ Maske, ein 0 setzt das Ergebnisbit mit dem Eingangsbit und eine 1 setzt der Ergebnisbit zum Komplement des Eingangsbits.

Answer 4

Eine Maske ist eine gebräuchliche Bezeichnung für einen ganzzahligen Wert, der bitweise ANDed, ORed, XORed usw. mit einem anderen ganzzahligen Wert ist.

Wenn Sie beispielsweise die 8 niedrigstwertigen Ziffern einer int-Variablen extrahieren möchten, tun Sie variable & 0xFF. 0xFF ist eine Maske. Wenn Sie die Bits 0 und 8 setzen möchten, müssen Sie variable | 0x101 eingeben, wobei 0x101 eine Maske ist.

Oder wenn Sie die gleichen Bits invertieren möchten, tun Sie variable^0x101, wobei 0x101 eine Maske ist.

Um eine Maske für Ihren Fall zu generieren, sollten Sie die einfache mathematische Tatsache ausnutzen, wenn Sie 1 zu Ihrer Maske hinzufügen (die Maske hat alle niedrigstwertigen Bits auf 1 gesetzt und der Rest auf 0), erhalten Sie einen Wert ist eine Potenz von 2.

Also, wenn Sie die nächste Potenz von 2 generieren, dann können Sie 1 davon abziehen, um die Maske zu erhalten.

Positive Potenzen von 2 sind leicht mit dem linken Schiebe << Operator in C. erzeugt

Daher 1 << n Ausbeuten 2 ⁿ. Im Binärformat ist es 10 ... 0 mit n 0s.

(1 << n) - 1 wird eine Maske mit n niedrigsten Bits auf 1

Nun setzen produzieren, müssen Sie in der linken Verschiebungen bei Überflutungen achten. In C (und in C++) können Sie eine Variable nicht um so viele Bitpositionen verschieben, wie die Variable hat. Wenn also Ints 32-Bit sind, wird 1<<32 in undefined behavior zurückgegeben. Vorzeichenbehaftete ganzzahlige Überläufe sollten ebenfalls vermieden werden, daher sollten Sie vorzeichenlose Werte verwenden, z. 1u << 31.

Answer 5

Für die Korrektheit und Leistung hat sich der beste Weg, dies zu erreichen, geändert, seit diese Frage 2012 aufgrund der Einführung von BMI-Anweisungen in modernen x86-Prozessoren, speziell BLSMSK, gestellt wurde.

Hier ist eine gute Möglichkeit, dieses Problem anzugehen, während die Abwärtskompatibilität mit älteren Prozessoren erhalten bleibt.

Diese Methode ist korrekt, während die aktuellen Topantworten in Randfällen undefiniertes Verhalten erzeugen.

Clang und GCC, wenn sie mithilfe von BMI-Anweisungen optimiert werden können, werden gen_mask() auf nur zwei Operationen kondensieren. Mit Hardware-Unterstützung, müssen Sie Compiler-Flags für BMI Anweisungen hinzuzufügen: -mbmi -mbmi2

#include <inttypes.h> 
#include <stdio.h> 

uint64_t gen_mask(const uint_fast8_t msb) { 
    const uint64_t src = (uint64_t)1 << msb; 
    return (src - 1)^src; 
} 

int main() { 
    uint_fast8_t msb; 
    for (msb = 0; msb < 64; ++msb) { 
    printf("%016" PRIx64 "\n", gen_mask(msb)); 
    } 
    return 0; 
}