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

Aus dem Kopf. Sorry, ich bin auf dem Handy. Ich nehme an, ein 64-Bit-Typ für Klarheit, aber dies kann leicht verallgemeinert werden.

(((uint64_t) (bits < 64)) << (bits & 63)) - 1u

Es ist die typische (1 << bits) - 1 aber verzweigungslos, ohne undefiniertes Verhalten, mit dem & 63 auf einigen Plattformen wegoptimierbar und mit korrekten Ergebnissen für den gesamten Wertebereich.

Der linke (linke) Verschiebungsoperand wird zu 0, wenn die Verschiebung größer oder gleich der Typenbreite ist.

Der rechte (linke) Schiebeoperand ist maskiert, um undefiniertes Verhalten zu vermeiden; der Wert wird nie größer als 63. Dies dient nur dazu, Compiler und Sprachanwälte glücklich zu machen, da keine Plattform Einsen hinzufügen wird, wenn der linke Operand bereits Null ist (für Werte größer als 63). Ein guter Compiler sollte die & 63 Maskierung auf Plattformen, auf denen dies bereits das Verhalten des zugrunde liegenden Befehls ist (z. B. x86).

Wie wir gesehen haben, erhalten Werte, die größer als 63 sind, durch die Verschiebung das Ergebnis 0, aber es gibt eine Subtraktion um eins, so dass alle Bits durch einen vorzeichenlosen Integer-Unterlauf gesetzt werden, was bei vorzeichenlosen Typen kein undefiniertes Verhalten ist.

Answer 2

Wenn Sie sich Sorgen über einen Überlauf in einer C-ähnlichen Sprache mit (1 << param) - 1 (wenn param 32 oder 64 bei der maximalen Größe Typ die Maske wird 0 seit bitshift schiebt über die Grenzen des Typs), eine Lösung, die ich gerade gedacht:

const uint32_t mask = ( 1ul << ( maxBits - 1ul ) ) | ( ( 1ul << ( maxBits - 1ul ) ) - 1ul );

Oder ein anderes Beispiel

const uint64_t mask = ( 1ull << ( maxBits - 1ull ) ) | ( ( 1ull << ( maxBits - 1ull ) ) - 1ull );

Hier ist eine schablonenhafte Version, denken Sie daran, dass Sie diese mit einem unsignierten Typ R verwenden sollten:

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

// bits cannot be 0
template <typename R>
static constexpr R bitmask1( const R bits )
{
    const R one = 1;
    assert( bits >= one );
    assert( bits <= sizeof( R ) * CHAR_BIT );
    const R bitShift = one << ( bits - one );
    return bitShift | ( bitShift - one );
}

Nehmen wir an, die maximale Anzahl von Bits ist 8 bei einem Byte, dann hätten wir mit der ersten überlaufenden Funktion 1 << 8 == 256 , was bei der Umwandlung in ein Byte zu 0 wird. Mit meiner Funktion haben wir 1 << 7 == 128 , die ein Byte enthalten kann, wird also 1<<7 | 1<<7 - 1 .

Ich habe die Funktion nicht kompiliert, daher kann sie Tippfehler enthalten.

---

Und zum Spaß gibt es hier Julien Royer ist ausgearbeitet:

// bits can be 0
template <typename R>
static constexpr R bitmask2( const R bits )
{
    const R zero = 0;
    const R mask = ~zero;
    const R maxBits = sizeof( R ) * CHAR_BIT;
    assert( bits <= maxBits );
    return mask >> ( maxBits - bits );
}

Answer 3

Für eine 32-Bit-Maske können Sie dies verwenden (verwenden Sie uint64_t für eine 64-Bit-Maske):

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

int
main()
{
    size_t n = 8;
    assert(n <= 32);
    uint32_t mask = ~(uint32_t)0 >> (32 - n);

    printf("mask = %08" PRIX32 "\n", mask);
}

Ich weiß, es ist eine Antwort auf einen sehr alten Beitrag. Aber für den Fall, dass ein Mensch dies liest: Ich würde mich über jede Rückmeldung freuen.

Answer 4

Nur zum Vergleich (Google), ich habe das Folgende benutzt, um eine Übersicht zu erhalten 1 Maske für für integrale Typen.
In C++ könnte man einfach verwenden:

std::numeric_limits<uint_16t>::max() // 65535