Maska bitowa w C


Jaki jest najlepszy sposób na wykreślenie maski bitowej w języku C z ustawieniem
m
bitów poprzedzonych przez
k
, a następnie ustawieniem
n
:
00..0 11..1 00..0
k m n

Na przykład k = 1, m = 4, n = 3 spowoduje powstanie maski bitowej:
01111000

Zaproszony:
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

~ (~ 0 <& < m) & < & < H.
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

Więc pytasz o m ustawionych bitów, poprzedzone prefiksem k bitów resetowania, a następnie n bitów resetowania? Możemy zignorować k, ponieważ będzie ono w dużym stopniu ograniczone przez wybór typu liczby całkowitej.
mask = ((1 << m) - 1) << n;
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

Lubię oba rozwiązania. Oto inny sposób, który przychodzi mi do głowy (prawdopodobnie nie lepszy).
((~((unsigned int)0) << k) >> (k + n)) << n
EDIT:
Wystąpił błąd w mojej poprzedniej wersji (nie miała ona rzutowania typu unsigned int). Problem polegał na tym, że
~ 0 & > & > n
dodaje 1 z przodu, a nie 0.
I tak, to podejście ma jedną wielką wadę: zakłada, że ​​znasz liczbę bitów standardowego typu liczby całkowitej, czyli innymi słowy, zakłada, że ​​znasz k, podczas gdy inne rozwiązania nie zależą od k. To sprawia, że ​​moja wersja jest mniej przenośna lub przynajmniej trudniejsza do przeniesienia. (Wykorzystuje również 3 przesunięcia, dodawanie i operator negacji bitowej, które są dwiema dodatkowymi operacjami).

Dlatego lepiej użyj jednego z innych przykładów.

Oto mała aplikacja testowa wykonana przez Jonathana Lefflera w celu porównania i przetestowania wyników różnych rozwiązań:
#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 = 0xlX = 0xlX = 0xlX\n", k, m, n,
set_mask_1(k, m, n),
set_mask_2(k, m, n),
set_mask_3(k, m, n));
}
return 0;
}
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

(Tylko) dla zainteresowanych nieco lepszym rozwiązaniem w systemach x86 z obsługą BMI2 (Intel Haswell lub nowszy, AMD Excavator lub nowszy):
mask = _bzhi_u32(-1,m)<<n;

Instrukcja
bzhi
usuwa najbardziej znaczące bity z określonej pozycji bitu.
Funkcja wewnętrzna
_bzhi_u32
jest kompilowana do tej instrukcji. Kod testowy:
#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= X\n",k);
return 0;
}

Wyjście:
$./a.out
k= 000FE000

Fragment kodu
_bzhi_u32 (-1, m) & < & < n
składa się z trzech instrukcji
movl $-1, %edx
bzhi %edi, %edx, %edi
shlx %esi, %edi, %eax

To o jedną instrukcję mniej niż kody @ Jonathan

Leffler
https://stackoverflow.com/a/316494/2439725
i

@Darius Bacon
https://stackoverflow.com/a/316493/2439725
.
W procesorach Intel Haswell lub nowszych zarówno
bzhi
, jak i
shlx
mają 1 cykl latencji i
przepustowość 2 na cykl. Na AMD Ryzen te dwie instrukcje mają nawet przepustowość 4 na cykl.
Anonimowy użytkownik

Anonimowy użytkownik

Potwierdzenie od:

Chociaż najlepsze odpowiedzi są proste i wydajne, nie instalują MSB w przypadku, gdy
n = 0
i
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‬
Moja sugestia dotycząca 32-bitowego słowa bez znaku (które jest brzydkie i ma gałąź) wygląda następująco:
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);
}

To faktycznie zwraca bity z zakresu
[m, n]
(przedział zamknięty), więc
create_mask (0,0)
zwróci maskę dla pierwszego BITU (bit 0) , podczas gdy
create_mask (4,6)
zwróci maskę dla bitów od 4 do 6, tj.
... 00111 0000
.

Aby odpowiedzieć na pytania, Zaloguj się lub Zarejestruj się