È questo il modo migliore? Campi di bit C

Question

Ho creato una funzione per impostare o cancellare un numero specifico di bit in un DWORD. La mia funzione funziona. Non ho bisogno di aiuto per farlo funzionare. Tuttavia, mi chiedo se il metodo che ho scelto di farlo sia il modo più veloce possibile.

È piuttosto difficile per me spiegare come funziona. Esistono due array contenenti DWORD riempiti con bit sul lato sinistro e destro di DWORD (con tutti gli 1 binari). Crea una maschera con tutti i bit riempiti tranne quelli che voglio impostare o cancellare, quindi li imposta con operatori bit a bit basati su quella maschera. Sembra piuttosto complicato per un compito così semplice, ma sembra il modo più veloce con cui possa arrivare. È molto più veloce che impostarli a poco a poco.

static DWORD __dwFilledBitsRight[] = { 
     0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF 
    }; 

static DWORD __dwFilledBitsLeft[] = { 
     0x0, 0x80000000, 0xC0000000, 0xE0000000, 0xF0000000, 0xF8000000, 0xFC000000, 0xFE000000, 0xFF000000, 0xFF800000, 0xFFC00000, 0xFFE00000, 0xFFF00000, 0xFFF80000, 0xFFFC0000, 0xFFFE0000, 0xFFFF0000, 0xFFFF8000, 0xFFFFC000, 0xFFFFE000, 0xFFFFF000, 0xFFFFF800, 0xFFFFFC00, 0xFFFFFE00, 0xFFFFFF00, 0xFFFFFF80, 0xFFFFFFC0, 0xFFFFFFE0, 
     0xFFFFFFF0, 0xFFFFFFF8, 0xFFFFFFFC, 0xFFFFFFFE, 0xFFFFFFFF 
    }; 

    // nStartBitFromLeft must be between 1 and 32... 
    // 1 is the bit farthest to the left (actual bit 31) 
    // 32 is the bit farthest to the right (actual bit 0) 
    inline void __FillDWORDBits(DWORD *p, int nStartBitFromLeft, int nBits, BOOL bSet) 
    { 
     DWORD dwLeftMask = __dwFilledBitsLeft[nStartBitFromLeft - 1]; // Mask for data on the left of the bits we want 
     DWORD dwRightMask = __dwFilledBitsRight[33 - (nStartBitFromLeft + nBits)]; // Mask for data on the right of the bits we want 
     DWORD dwBitMask = ~(dwLeftMask | dwRightMask); // Mask for the bits we want 
     DWORD dwOriginal = *p; 
     if(bSet) *p = (dwOriginal & dwLeftMask) | (dwOriginal & dwRightMask) | (0xFFFFFFFF & dwBitMask); 
     else *p = (dwOriginal & dwLeftMask) | (dwOriginal & dwRightMask) | 0; 

    } 

Answer 1

ne dite:

// Create mask of correct length, and shift to the correct position 
DWORD mask = ((1ULL << nBits) - 1) << pos; 
// Apply mask (or its inverse) 
if (bSet) 
{ 
    *p |= mask; 
} 
else 
{ 
    *p &= ~mask; 
} 

E 'piuttosto probabile che semplici operazioni bit per bit sarà più veloce di tabella di ricerca su qualsiasi processore moderno.

Nota: A seconda del rapporto tra DWORD e long long su questa piattaforma, potrebbe essere necessario un trattamento speciale per il caso in cui nBits == sizeof(DWORD)*8. Oppure se nBits==0 non è una possibilità, puoi semplicemente fare DWORD mask = ((2ULL << (nBits - 1)) - 1) << pos;.

Aggiornamento: È stato detto che il if potrebbe potenzialmente essere lento, il che è vero. Ecco un rimpiazzo, ma è necessario misurare per vedere se è effettivamente più veloce nella pratica.

// A bit hacky, but the aim is to get 0x00000000 or 0xFFFFFFFF 
// (relies on two's-complement representation) 
DWORD blanket = bSet - 1; 
// Use the blanket to override one or other masking operation 
*p |= (blanket | mask); 
*p &= ~(blanket & mask); 

Answer 2

Questo è il modo in cui lo farei. Lo suddividerei in due funzioni, setbits() e clearbits(). Passi scomposti per chiarezza, e sono sicuro che può essere molto più ottimizzato.

Questa versione dipende dal codice a 32 bit così com'è. Inoltre, nel mio mondo, il bit 0 è il bit più a destra. Il tuo chilometraggio può variare.

setbits(DWORD *p , int offset , int len) 
{ 
    // offset must be 0-31, len must be 0-31, len+offset must be 0-32 
    int right_shift = (!len ? 0 : 32 - (len+offset)) ; 
    int left_shift = offset ; 
    DWORD right_mask = 0xFFFFFFFF >> right_shift ; 
    DWORD left_mask = 0xFFFFFFFF << left_shift ; 
    DWORD mask  = left_mask & right_mask  ; 

    *p |= mask ; 

    return ; 
} 

clearbits(DWORD *p , int offset , int len) 
{ 
    // offset must be 0-31, len must be 0-31, len+offset must be 0-32 
    int right_shift = (!len ? 0 : 32 - (len+offset)) ; 
    int left_shift = offset ; 
    DWORD right_mask = 0xFFFFFFFF >> right_shift ; 
    DWORD left_mask = 0xFFFFFFFF << left_shift ; 
    DWORD mask  = ~(left_mask & right_mask) ; 

    *p &= mask ; 

    return ; 
} 

Mi sono imbattuto in questa versione migliorata mentre cercavo qualcos'altro oggi. Per gentile concessione di Sean Anderson Bit Twiddling Hacks alla Stanford University:

// uncomment #define to get the super scalar CPU version. 
// #define SUPER_SCALAR_CPU 
void setbits(unsigned int *p , int offset , int len , int flag) 
{ 
    unsigned int mask = ((1 << len) - 1) << offset ; 

#if !defined(SUPER_SCALAR_CPU) 
    *p ^= (- flag^*p) & mask ; 
#else 
    // supposed to be some 16% faster on a Intel Core 2 Duo than the non-super-scalar version above 
    *p = (*p & ~ mask) | (- flag & mask) ; 
#endif 

    return ; 

} 

Molto dipende dal vostro compilatore, però.