webentwicklung-frage-antwort-db.com.de

Bitmaske in C

Was ist der beste Weg, um eine Bitmaske in C mit m gesetzten Bits zu erstellen, denen k nicht gesetzte Bits und n nicht gesetzte Bits vorausgehen:

00..0 11..1 00..0
  k     m     n

Zum Beispiel würde k = 1, m = 4, n = 3 die Bitmaske ergeben:

01111000
21
grigy

~ (~ 0 << m) << n

41
Darius Bacon

Sie fragen also nach m gesetzten Bits, denen k Rücksetzbits und n Rücksetzbits vorangestellt sind? Wir können k ignorieren, da es weitgehend durch die Wahl des Integer-Typs eingeschränkt wird.

mask = ((1 << m) - 1) << n;
29

Ich mag beide Lösungen. Hier ist ein anderer Weg, der mir einfällt (wahrscheinlich nicht besser).

((~((unsigned int)0) << k) >> (k + n)) << n

BEARBEITEN: In meiner vorherigen Version gab es einen Fehler (ohne die nicht signierte int-Besetzung). Das Problem war, dass ~0 >> n vorne 1s und nicht 0s hinzufügt.

Und ja, dieser Ansatz hat einen großen Nachteil. Es wird davon ausgegangen, dass Sie die Anzahl der Bits des Standard-Integer-Typs kennen. Mit anderen Worten, es wird davon ausgegangen, dass Sie k wirklich kennen, während die anderen Lösungen von k unabhängig sind. Dadurch ist meine Version weniger portabel oder zumindest schwerer zu portieren. (Es werden auch 3 Shifts und Addition sowie ein bitweiser Negationsoperator verwendet, also zwei zusätzliche Operationen.)

Also sollten Sie besser eines der anderen Beispiele verwenden.

Hier ist eine kleine Test-App von Jonathan Leffler, um die Ausgabe der verschiedenen Lösungen zu vergleichen und zu verifizieren:

#include <stdio.h>
#include <limits.h>

enum { ULONG_BITS = (sizeof(unsigned long) * CHAR_BIT) };

static unsigned long set_mask_1(int k, int m, int n)
{
    return ~(~0 << m) << n;
}

static unsigned long set_mask_2(int k, int m, int n)
{
    return ((1 << m) - 1) << n;
}

static unsigned long set_mask_3(int k, int m, int n)
{
    return ((~((unsigned long)0) << k) >> (k + n)) << n;
}

static int test_cases[][2] =
{
    { 1, 0 },
    { 1, 1 },
    { 1, 2 },
    { 1, 3 },
    { 2, 1 },
    { 2, 2 },
    { 2, 3 },
    { 3, 4 },
    { 3, 5 },
};

int main(void)
{
    size_t i;
    for (i = 0; i < 9; i++)
    {
        int m = test_cases[i][0];
        int n = test_cases[i][1];
        int k = ULONG_BITS - (m + n);
        printf("%d/%d/%d = 0x%08lX = 0x%08lX = 0x%08lX\n", k, m, n,
               set_mask_1(k, m, n),
               set_mask_2(k, m, n),
               set_mask_3(k, m, n));
    }
    return 0;
}
5
quinmars

(Nur) für diejenigen, die an einer etwas effizienteren Lösung für x86-Systeme mit BMI2-Unterstützung interessiert sind (Intel Haswell oder neuer, AMD Excavator oder neuer):

mask = _bzhi_u32(-1,m)<<n;

Der Befehl bzhi setzt die High-Bits beginnend mit der angegebenen Bitposition auf Null. Der _bzhi_u32 wird zu dieser Anweisung kompiliert. Testcode:

#include <stdio.h>
#include <x86intrin.h>
/*  gcc -O3 -Wall -m64 -march=haswell bitmsk_mn.c   */

unsigned int bitmsk(unsigned int m, unsigned int n)
{
    return _bzhi_u32(-1,m)<<n;
}

int main() {
    int k = bitmsk(7,13);
    printf("k= %08X\n",k);
    return 0;
}

Ausgabe:

$./a.out
k= 000FE000

Das Codefragment _bzhi_u32(-1,m)<<n besteht aus drei Anweisungen

movl    $-1, %edx
bzhi    %edi, %edx, %edi
shlx    %esi, %edi, %eax

Welches ist eine Anweisung weniger als die Codes von @Jonathan Leffler und @Darius Bacon . Auf Intel Haswell-Prozessoren oder neueren Prozessoren haben sowohl bzhi als auch shlx eine Latenzzeit von 1 Zyklus und einen Durchsatz von 2 pro Zyklus. Bei AMD Ryzen haben diese beiden Befehle sogar einen Durchsatz von 4 pro Zyklus.

0
wim

Obwohl die Top-Antworten einfach und effektiv sind, wird das MSB nicht für den Fall festgelegt, dass n=0 und m=31:

~(~0 << 31) << 0 = 0111 1111 1111 1111 1111 1111 1111 1111‬

((1 << 31)-1) << 0 = 0111 1111 1111 1111 1111 1111 1111 1111‬

Mein Vorschlag für ein 32-Bit-Wort ohne Vorzeichen (das hässlich ist und einen Zweig hat) sieht folgendermaßen aus:

unsigned int create_mask(unsigned int n,unsigned int m) {
  // 0 <= start_bit, end_bit <= 31
  return (m - n == 31 ? 0xFFFFFFFF : ((1 << (m-n)+1)-1) << n);
}

Dies erhält tatsächlich die Bits im Bereich [m,n] (geschlossenes Intervall), so dass create_mask(0,0) eine Maske für das erste Bit (Bit 0) und create_mask(4,6) eine Maske für die Bits 4 bis 6 zurückgibt, d. H. ... 00111 0000.

0
Nubcake