Это самый оптимальный способ?Си битовые поля - PullRequest
Новая
       32

Это самый оптимальный способ?Си битовые поля

6 голосов
/ 26 января 2011

Я сделал функцию для установки или очистки определенного числа битов в DWORD. Моя функция работает. Мне не нужна помощь, чтобы это сработало. Однако мне интересно, является ли выбранный мною метод наиболее быстрым?

Мне довольно сложно объяснить, как это работает. Есть два массива, содержащие DWORD, которые заполнены битами слева и справа от DWORD (со всеми двоичными единицами). Он создает маску со всеми заполненными битами, кроме тех, которые я хочу установить или очистить, а затем устанавливает их с помощью побитовых операторов на основе этой маски. Это кажется довольно сложным для такой простой задачи, но, похоже, самый быстрый способ, которым я мог придумать. Это намного быстрее, чем устанавливать их постепенно. 

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;

    }

Ответы [ 2 ]

12 голосов
/ 26 января 2011

Как насчет: 

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

Вполне вероятно, что простые побитовые операции будут быстрее, чем поиск таблиц на любом современном процессоре.

Примечание: В зависимости от отношений между DWORD и long long на этой платформе вам может потребоваться специальная обработка для случая, когда nBits == sizeof(DWORD)*8. Или, если nBits==0 не представляется возможным, вы можете просто сделать DWORD mask = ((2ULL << (nBits - 1)) - 1) << pos;.

Обновление: Было упомянуто, что if потенциально может быть медленным, что верно. Вот замена для этого, но вам нужно измерить, чтобы увидеть, действительно ли это быстрее на практике. 

// 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);
4 голосов
/ 26 января 2011

Я бы так и сделал. Я бы разбил его на две функции: setbits () и clearbits (). Для ясности выложены шаги, и я уверен, что это может быть гораздо более оптимизировано.

Эта версия зависит от 32-битного кода в его нынешнем виде. Кроме того, в моем мире бит 0 - самый правый бит. Ваш пробег может отличаться. 

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

Я наткнулся на эту улучшенную версию, пока искал что-то еще сегодня. Предоставлено Шоном Андерсоном Bit Twiddling Hacks в Стэнфордском университете: 

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

}

Однако многое зависит от вашего компилятора.

...