Algorithmus zur Erzeugung von Bitmasken

Question

Ich stand vor dem einzigartigen Problem, eine Bitmaske auf der Grundlage des Eingabeparameters zu erzeugen. Zum Beispiel,

wenn param = 2, dann wird die Maske 0x3 (11b) sein wenn param = 5, dann wird die Maske 0x1F (1 1111b) sein

Dies habe ich mit einer for-Schleife in C implementiert, etwa so

int nMask = 0;
for (int i = 0; i < param; i ++) {

    nMask |= (1 << i);
}

Ich würde gerne wissen, ob es einen besseren Algorithmus gibt ~~~

Answer 1

Eine Sache, die man bei solchen Bitmasken beachten sollte, ist, dass sie immer um eins kleiner sind als eine Zweierpotenz.

Der Ausdruck 1 << n ist der einfachste Weg, die n-te Potenz von zwei zu erhalten.

Sie wollen nicht, dass Zero eine Bitmaske von 00000001 wollen Sie, dass sie Null ergibt. Sie müssen also eine subtrahieren.

mask = (1 << param) - 1;

Edit :

Wenn Sie einen Sonderfall für param > 32 wünschen:

int sizeInBits = sizeof(mask) * BITS_PER_BYTE; // BITS_PER_BYTE = 8;
mask = (param >= sizeInBits ? -1 : (1 <<  param) - 1);

Diese Methode sollte für 16-, 32- oder 64-Bit-Ganzzahlen funktionieren, aber möglicherweise müssen Sie die '1' explizit eingeben.

Answer 2

Effiziente, verzweigungsfreie, portable und generische (aber hässliche) Implementierung

C:

#include <limits.h>     /* CHAR_BIT */

#define BIT_MASK(__TYPE__, __ONE_COUNT__) \
    ((__TYPE__) (-((__ONE_COUNT__) != 0))) \
    & (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__)))

C++:

#include <climits>

template <typename R>
static constexpr R bitmask(unsigned int const onecount)
{
//  return (onecount != 0)
//      ? (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount))
//      : 0;
    return static_cast<R>(-(onecount != 0))
        & (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount));
}

Verwendung (Erzeugen von Kompilierzeitkonstanten)

BIT_MASK(unsigned int, 4) /* = 0x0000000f */

BIT_MASK(uint64_t, 26) /* = 0x0000000003ffffffULL */

Beispiel

#include <stdio.h>

int main()
{
    unsigned int param;
    for (param = 0; param <= 32; ++param)
    {
        printf("%u => 0x%08x\n", param, BIT_MASK(unsigned int, param));
    }
    return 0;
}

Ausgabe

0 => 0x00000000
1 => 0x00000001
2 => 0x00000003
3 => 0x00000007
4 => 0x0000000f
5 => 0x0000001f
6 => 0x0000003f
7 => 0x0000007f
8 => 0x000000ff
9 => 0x000001ff
10 => 0x000003ff
11 => 0x000007ff
12 => 0x00000fff
13 => 0x00001fff
14 => 0x00003fff
15 => 0x00007fff
16 => 0x0000ffff
17 => 0x0001ffff
18 => 0x0003ffff
19 => 0x0007ffff
20 => 0x000fffff
21 => 0x001fffff
22 => 0x003fffff
23 => 0x007fffff
24 => 0x00ffffff
25 => 0x01ffffff
26 => 0x03ffffff
27 => 0x07ffffff
28 => 0x0fffffff
29 => 0x1fffffff
30 => 0x3fffffff
31 => 0x7fffffff
32 => 0xffffffff

Erläuterung

Zunächst einmal, wie bereits in anderen Antworten erörtert, >> verwendet wird, statt << um das Problem zu vermeiden, dass die Anzahl der Verschiebungen gleich der Anzahl der Bits des Speichertyps des Wertes ist. (Dank Antwort von Julien oben für die Idee)

Zur Vereinfachung der Diskussion "instanziieren" wir das Makro mit unsigned int comme __TYPE__ und sehen Sie, was passiert (wobei wir im Moment von 32-Bit ausgehen):

((unsigned int) (-((__ONE_COUNT__) != 0))) \
& (((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))

Konzentrieren wir uns darauf:

((sizeof(unsigned int) * CHAR_BIT)

Erstens. sizeof(unsigned int) zur Kompilierzeit bekannt ist. Sie ist gleich 4 nach unseren Annahmen. CHAR_BIT steht für die Anzahl der Bits pro char auch bekannt als "pro Byte". Sie ist auch zur Kompilierzeit bekannt. Sie ist gleich 8 auf den meisten Maschinen der Erde. Da dieser Ausdruck zur Kompilierzeit bekannt ist, würde der Compiler wahrscheinlich die Multiplikation zur Kompilierzeit durchführen und sie als Konstante behandeln, was gleichbedeutend ist mit 32 in diesem Fall.

Gehen wir weiter zu:

((unsigned int) -1)

Sie ist gleich 0xFFFFFFFF . Gießen -1 zu einem beliebigen vorzeichenlosen Typ erzeugt einen Wert von "all-1s" in diesem Typ. Dieser Teil ist auch eine Kompilierzeitkonstante.

Bis jetzt war der Ausdruck:

(((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))

ist in der Tat dasselbe wie:

0xffffffffUL >> (32 - param)

was mit der Antwort von Julien übereinstimmt. Ein Problem mit seiner Antwort ist, dass wenn param ist gleich 0 und ergibt den Ausdruck 0xffffffffUL >> 32 wäre das Ergebnis des Ausdrucks 0xffffffffUL anstelle des erwarteten 0 ! (Deshalb nenne ich meinen Parameter als __ONE_COUNT__ um seine Absicht zu unterstreichen)

Um dieses Problem zu lösen, könnten wir einfach einen Sonderfall für __ONE_COUNT ist gleich 0 mit if-else o ?: etwa so:

#define BIT_MASK(__TYPE__, __ONE_COUNT__) \
    (((__ONE_COUNT__) != 0) \
    ? (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__)))
    : 0)

Aber verzweigungsfreier Code ist doch viel cooler, oder?! Lassen Sie uns zum nächsten Teil übergehen:

((unsigned int) (-((__ONE_COUNT__) != 0)))

Beginnen wir mit dem innersten Ausdruck und dem äußersten. ((__ONE_COUNT__) != 0) produziert 0 wenn der Parameter 0 , oder 1 sonst. (-((__ONE_COUNT__) != 0)) produziert 0 wenn der Parameter 0 , oder -1 anders. Für ((unsigned int) (-((__ONE_COUNT__) != 0))) der Trick mit dem Typ-Cast ((unsigned int) -1) wurde bereits oben erläutert. Merken Sie jetzt den Trick? Der Ausdruck:

((__TYPE__) (-((__ONE_COUNT__) != 0)))

ist gleich "all-0s", wenn __ONE_COUNT__ Null ist und ansonsten "alle-1s". Er dient als Bitmaske für den im ersten Schritt berechneten Wert. Wenn also __ONE_COUNT__ ungleich Null ist, hat die Maske keine Wirkung und entspricht der Antwort von Julien. Wenn __ONE_COUNT__ es 0 werden alle Teile von Juliens Antwort maskiert, so dass eine konstante Null entsteht. Zur Veranschaulichung sehen Sie sich das an:

__ONE_COUNT__ :                           0                Other
                                          -------------    --------------
(__ONE_COUNT__)                           0 = 0x000...0    (itself)
((__ONE_COUNT__) != 0)                    0 = 0x000...0     1 = 0x000...1
((__TYPE__) (-((__ONE_COUNT__) != 0)))    0 = 0x000...0    -1 = 0xFFF...F

Answer 3

Alternativ können Sie auch eine Rechtsverschiebung verwenden, um das in der (1 << param) - 1 Lösung.

unsigned long const mask = 0xffffffffUL >> (32 - param);

unter der Annahme, dass param <= 32 natürlich.

Answer 4

Für diejenigen, die es interessiert, ist dies die Nachschlagetabellen-Alternative, die in den Kommentaren zu der anderen Antwort diskutiert wurde - mit dem Unterschied, dass sie für ein param von 32 korrekt funktioniert. Es ist einfach genug, um auf die 64 Bit zu erweitern unsigned long long Version, wenn Sie das brauchen, und sollte sich in der Geschwindigkeit nicht wesentlich unterscheiden (wenn es in einer engen inneren Schleife aufgerufen wird, bleibt die statische Tabelle zumindest im L2-Cache, und wenn es no in einer engen inneren Schleife aufgerufen wird, ist der Leistungsunterschied nicht so groß).

unsigned long mask2(unsigned param)
{
    static const unsigned long masks[] = {
        0x00000000UL, 0x00000001UL, 0x00000003UL, 0x00000007UL,
        0x0000000fUL, 0x0000001fUL, 0x0000003fUL, 0x0000007fUL,
        0x000000ffUL, 0x000001ffUL, 0x000003ffUL, 0x000007ffUL,
        0x00000fffUL, 0x00001fffUL, 0x00003fffUL, 0x00007fffUL,
        0x0000ffffUL, 0x0001ffffUL, 0x0003ffffUL, 0x0007ffffUL,
        0x000fffffUL, 0x001fffffUL, 0x003fffffUL, 0x007fffffUL,
        0x00ffffffUL, 0x01ffffffUL, 0x03ffffffUL, 0x07ffffffUL,
        0x0fffffffUL, 0x1fffffffUL, 0x3fffffffUL, 0x7fffffffUL,
        0xffffffffUL };

    if (param < (sizeof masks / sizeof masks[0]))
        return masks[param];
    else
        return 0xffffffffUL; /* Or whatever else you want to do in this error case */
}

Es ist erwähnenswert, dass Sie, wenn Sie die if() Anweisung (weil wir befürchten, dass jemand sie mit param > 32 ), dann bringt Ihnen das nichts gegenüber der Alternative der anderen Antwort:

unsigned long mask(unsigned param)
{
    if (param < 32)
        return (1UL << param) - 1;
    else
        return -1;
}

Der einzige Unterschied besteht darin, dass die letztere Version einen Sonderfall hat param >= 32 während der erste Fall nur einen Sonderfall hat param > 32 .

Answer 5

Wie wäre es mit diesem (in Java):

int mask = -1;
mask = mask << param;
mask = ~mask;

Auf diese Weise können Sie Nachschlagetabellen und die feste Kodierung der Länge einer ganzen Zahl vermeiden.

Erläuterung: Eine vorzeichenbehaftete ganze Zahl mit dem Wert -1 wird binär als alle Einsen dargestellt. Schieben Sie die angegebene Anzahl von Malen nach links, um so viele 0en auf der rechten Seite hinzuzufügen. Dies führt zu einer Art "umgekehrter Maske". Negieren Sie dann das verschobene Ergebnis, um Ihre Maske zu erstellen.

Dies könnte verkürzt werden auf:

int mask = ~(-1<<param);

Ein Beispiel:

int param = 5;
int mask = -1;        // 11111111 (shortened for example)
mask = mask << param; // 11100000
mask = ~mask;         // 00011111