Algorytm generowania maski bitowej

Question

Wystąpiłem w obliczu tego unikalnego problemu generowania maski bitowej w oparciu o parametr wejściowy. Na przykład,

jeśli parametr = 2, to maska ​​jest 0x3 (11b) jeśli parametr = 5, a maska ​​będzie 0x1F (1 1111b)

to, że zastosowana przy użyciu o-pętlę C, coś

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

    nMask |= (1 << i); 
} 

chciałbym wiedzieć, czy istnieje lepszy algorytm ~~~

Answer 1

jedno zauważyć o bitmasks jak to jest, że są one zawsze jeden mniej niż potęgi dwójki.

Wyrażenie "1 < < n" to łatwy sposób na uzyskanie n-tej potęgi dwóch.

Nie chcesz, aby zero dawało maskę bitową "00000001", chcesz, aby zapewniało zero. Więc musisz odjąć jedną.

mask = (1 << param) - 1; 

Edit:

Jeśli chcesz przypadek szczególny dla param> 32:

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

Metoda ta powinna działać na 16, 32 lub 64-bitowe liczby całkowite, ale może muszą wyraźnie wpisać "1".

Answer 2

Dla zainteresowanych, jest to alternatywa lookup-table omówione w komentarzach do drugiej odpowiedzi - z tą różnicą, że działa poprawnie na param z 32. Jest wystarczająco łatwo rozszerzyć do wersji 64 bit unsigned long long, jeśli ciebie potrzebują tego i nie powinny znacząco różnić się szybkością (jeśli jest wywoływana w ciasnej wewnętrznej pętli, statyczny stół pozostanie przynajmniej w pamięci podręcznej L2, a jeśli jest to , a nie wywołany w ciasnej wewnętrznej pętli, to wygrywa różnica wydajności nie ważne).

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 */ 
} 

Warto zwrócić uwagę, że jeśli trzeba oświadczenie if() (bo obawiają się, że ktoś może nazwać go param > 32), to nie wygra nic nad alternatywą od drugiej odpowiedzi:

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

Jedyna różnica polega na tym, że druga wersja ma specjalny przypadek param >= 32, podczas gdy pierwszy ma specjalny przypadek param > 32.

Answer 3

Alternatywnie można użyć prawej zmiany, aby uniknąć problemu wspomnianego w rozwiązaniu (1 << param) - 1.

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

przy założeniu, że param <= 32, oczywiście.

Answer 4

Wydajne, Oddział-Free Portable i Generic (ale brzydki) Realizacja

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

Usage (Producing kompilacji Stałe)

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

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

Przykład

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

Wyjście

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 

Wyjaśnienie

Przede wszystkim, jak już omówione w innych odpowiedzi, >> jest używany zamiast << w celu uniknięcia problemu, gdy liczba przesunięcie jest równe do liczby bitów typu przechowywania wartości. (Dzięki Julien's answer above dla idei)

Dla ułatwienia dyskusji, niech „instancji” makro z unsigned int jak __TYPE__ i zobaczyć, co się dzieje (przy założeniu 32-bit na razie):

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

Skupmy na:

((sizeof(unsigned int) * CHAR_BIT) 

pierwsza. sizeof(unsigned int) jest znany podczas kompilacji. Jest równa 4 zgodnie z naszym założeniem. CHAR_BIT reprezentuje liczbę bitów na char, a.k.a. na bajt. Jest również znany podczas kompilacji. Jest równy 8 na większości maszyn na Ziemi. Ponieważ to wyrażenie jest znane podczas kompilacji, kompilator prawdopodobnie wykonałby mnożenie w czasie kompilacji i potraktowałby go jako stałą, która w tym przypadku równa się 32. ruch

Przejdźmy do:

((unsigned int) -1) 

Jest równa 0xFFFFFFFF. Przesyłanie -1 do dowolnego typu bez znaku powoduje utworzenie wartości "all-1s" w tym typie. Ta część jest także stałą czasową kompilacji.

Do tej pory, wyrażenie:

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

jest w rzeczywistości taki sam jak:

0xffffffffUL >> (32 - param) 

która jest taka sama jak odpowiedź Juliena powyżej. Jednym z problemów z jego odpowiedzią jest to, że jeśli param jest równe 0, tworząc wyrażenie 0xffffffffUL >> 32, wynikiem wyrażenia będzie 0xffffffffUL, zamiast oczekiwanego 0!(Dlatego właśnie nazwać moją parametr jako __ONE_COUNT__ podkreślić swój zamiar)

Aby rozwiązać ten problem, możemy po prostu dodać szczególny przypadek dla __ONE_COUNT równa 0 użyciu if-else lub ?:, tak:

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

Ale bezgałęziowy kod jest chłodniejszy, prawda ?! Przejdźmy do następnej części:

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

Zacznijmy od najgłębszego wyrażenia do najbardziej zewnętrznego. ((__ONE_COUNT__) != 0) produkuje 0, gdy parametr to 0, lub 1 w przeciwnym razie. (-((__ONE_COUNT__) != 0)) produkuje 0, gdy parametr to 0, lub -1 w przeciwnym razie. W przypadku ((unsigned int) (-((__ONE_COUNT__) != 0))), sztuczka typu rzutowego ((unsigned int) -1) została już wyjaśniona powyżej. Czy zauważyłeś teraz sztuczkę? Wyrażenie:

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

równa się "all-0s" jeśli __ONE_COUNT__ wynosi zero, a "all-1s" inaczej. Działa jako maska ​​bitowa dla wartości obliczonej w pierwszym kroku. Tak więc, jeśli __ONE_COUNT__ jest niezerowa, maska ​​jako brak efektu i jest taka sama jak odpowiedź Juliena. Jeśli __ONE_COUNT__ jest 0, zamaskowuje wszystkie fragmenty odpowiedzi Juliena, tworząc stałe zero. Wizualizację, oglądać to:

__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 5

Jak na ten temat (w Javie):

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

W ten sposób można uniknąć tablic przeglądowych i ciężko kodowania długości całkowitej.

Objaśnienie: Liczba całkowita ze znakiem o wartości -1 jest reprezentowana w postaci binarnej jako wszystkie. Shift opuścił określoną liczbę razy, aby dodać wiele zer po prawej stronie. Spowoduje to "sortowanie odwrotne". Następnie zaneguj przesunięty wynik, aby utworzyć maskę.

ten może być skrócony do:

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

Przykład:

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