Is this the most optimal way? C bitfields

Question

I made a function to set or clear a specific number of bits in a DWORD. My function works. I don't need help making it work. However, I am wondering if the method I've chosen to do it is the fastest possible way.

It's rather hard for me to explain how this works. There are two arrays containing DWORDs that are filled with bits on the left and right side of the DWORD (with all binary 1's). It makes a mask with all the bits filled except for the ones I want to set or clear, and then sets them with bitwise operators based on that mask. It seems rather complicated for such a simple task, but it seems like the fastest way I could come up with. It's much faster than setting them bit by bit.

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

How about:

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

It's pretty likely that simple bitwise operations will be faster than table lookup on any modern processor.

Note: Depending on the relationship between DWORD and long long on this platform, you may need special handling for the case where nBits == sizeof(DWORD)*8. Or if nBits==0 is not a possibility, you could just do DWORD mask = ((2ULL << (nBits - 1)) - 1) << pos;.

Update: It's been mentioned that the if could potentially be slow, which is true. Here's a replacement for it, but you'd need to measure to see if it's actually any faster in practice.

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

This is the way I'd do it. I'd break it into two functions, setbits() and clearbits(). Steps broken out for clarity, and I'm sure it can be far more optimized.

This version is dependent on 32-bit code as it stands. Also, in my world, bit 0 is the rightmost bit. Your mileage may vary.

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

I stumbled across this improved version whilst looking for something else today. Courtesy of Sean Anderson's Bit Twiddling Hacks at 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 ;

}

Much depends on your compiler, though.