Bitmaske in C

Question

Wie konstruiert man am besten eine Bitmaske in C mit m gesetzte Bits, denen ein k nicht gesetzte Bits, gefolgt von n ungesetzte Bits:

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

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

01111000

Answer 1

Das können Sie tun:

~(~0 << m) << n

Answer 2

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

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

Answer 3

Mir gefallen beide Lösungen. Hier ist eine andere Möglichkeit, die mir in den Sinn kommt (wahrscheinlich nicht besser).

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

EDIT: Es gab einen Fehler in meiner vorherigen Version (sie war ohne den unsigned int cast). Das Problem war, dass ~0 >> n fügt vorne 1en und nicht 0en hinzu.

Und ja, dieser Ansatz hat einen großen Nachteil: er setzt voraus, dass man die Anzahl der Bits des Standard-Integer-Typs kennt, oder anders ausgedrückt, er setzt voraus, dass man k wirklich kennt, während die anderen Lösungen unabhängig von k sind. Das macht meine Version weniger portabel oder zumindest schwieriger zu portieren. (Außerdem verwendet sie 3 Verschiebungen, Addition und einen bitweisen Negationsoperator, also zwei zusätzliche Operationen).

Es wäre also besser, eines der anderen Beispiele zu verwenden.

Hier ist eine kleine Testanwendung, die von Jonathan Leffler erstellt wurde, um die Ausgabe der verschiedenen Lösungen zu vergleichen und zu überprüfen:

#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;
}

Answer 4

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

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

En bzhi Anweisung setzt die High-Bits ab der angegebenen Bitposition auf Null. Der Befehl _bzhi_u32 Intrinsic kompiliert zu dieser Anweisung. 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;
}

O

$./a.out
k= 000FE000

Das Codefragment _bzhi_u32(-1,m)<<n kompiliert zu drei Anweisungen

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

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

Answer 5

Die oberen Antworten sind zwar einfach und effektiv, setzen aber nicht das MSB für den Fall, dass n=0 y 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 sieht folgendermaßen aus:

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

Dadurch werden die Bits im Bereich [m,n] (geschlossenes Intervall), also create_mask(0,0) gibt eine Maske für das erste Bit (Bit 0) zurück und create_mask(4,6) gibt eine Maske für die Bits 4 bis 6 zurück, d. h. ... 00111 0000 .