Определите, какой единственный бит в байте установлен

У меня есть byte который я использую для битфлагов. Я знаю, что один и только один бит в byte установлен в любое время.

Пример: unsigned char b = 0x20; //(00100000) 6th most bit set unsigned char b = 0x20; //(00100000) 6th most bit set

В настоящее время я использую следующий цикл, чтобы определить, какой бит установлен:

 int getSetBitLocation(unsigned char b) { int i=0; while( !((b >> i++) & 0x01) ) { ; } return i; } 

Как я наиболее эффективно определяю позицию установленного бита? Могу ли я сделать это без итераций?

Могу ли я сделать это без итераций?

Это действительно возможно.

Как я наиболее эффективно определяю позицию установленного бита?

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

 int getTopSetBit(unsigned char b) { int res = 0; if(b>15){ b = b >> 4; res = res + 4; } if(b>3){ b = b >> 2; res = res + 2; } //thanks @JasonD return res + (b>>1); } 

Он использует два сравнения (три для uint16 с, четыре для uint32 s …). и это может быть быстрее, чем ваш цикл. Это определенно не короче.


Основываясь на идее Антона Коваленко (хешированный поиск) и комментария на 6502 (деление медленное), я также предлагаю эту реализацию (8-битный => 3-битный хеш с использованием дебрюинской последовательности)

 int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2}; int getBitPosition(unsigned char b) { // return lookup[(b | (b>>1) | (b>>2) | (b>>4)) & 0x7]; return lookup[((b * 0x1D) >> 4) & 0x7]; } 

или (более крупное LUT, но использует только три слова вместо четырех)

 int[] lookup = {0xFF, 0, 1, 4, 2, 0xFF, 5, 0xFF, 7, 3, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF}; int getBitPosition(unsigned char b) { return lookup[(b | (b>>3) | (b>>4)) & 0xF]; } 

Таблица поиска достаточно проста, и вы можете уменьшить ее размер, если набор значений разрежен. Попробуем с 11 элементами вместо 128:

 unsigned char expt2mod11_bits[11]={0xFF,0,1,0xFF,2,4,0xFF,7,3,6,5}; unsigned char pos = expt2mod11_bits[b%11]; assert(pos < 8); assert(1< 

Конечно, это не обязательно более эффективно, особенно для 8 бит, но тот же трюк можно использовать для больших размеров, где полная таблица поиска будет ужасно большой. Посмотрим:

 unsigned int w; .... unsigned char expt2mod19_bits[19]={0xFF,0,1,13,2,0xFF,14,6,3,8,0xFF,12,15,5,7,11,4,10,9}; unsigned char pos = expt2mod19_bits[w%19]; assert(pos < 16); assert(1< 

Это довольно распространенная проблема для шахматных программ, которые используют 64 бита для представления позиций (то есть один 64-разрядный номер для хранения всех белых пешек, другой для всех черных и т. Д.).

При таком представлении иногда требуется найти индекс 0 … 63 первого или последнего бита набора и существует несколько возможных подходов:

  1. Просто сделайте цикл, как вы это делали
  2. Используя дихотомический поиск (т. Е. Если x & 0x00000000ffffffffULL равно нулю, нет необходимости проверять низкие 32 бита)
  3. Используя специальную инструкцию, если она доступна на процессоре (например, bsf и bsr на x86)
  4. Использование поисковых таблиц (конечно, не для всего 64-битного значения, а для 8 или 16 бит)

Что быстрее, тем не менее, действительно зависит от вашего оборудования и от реальных случаев использования. Только для 8-битных процессоров и для современного процессора я считаю, что лучше всего найти таблицу поиска с 256 записями …

Но вы действительно уверены, что это узкое место в вашем алгоритме?

 unsigned getSetBitLocation(unsigned char b) { unsigned pos=0; pos = (b & 0xf0) ? 4 : 0; b |= b >>4; pos += (b & 0xc) ? 2 : 0; b |= b >>2; pos += (b & 0x2) ? 1 : 0; return pos; } 

Было бы трудно сделать это без прыжков. Может быть, с последовательностями Брюина?

Самое простое – создать таблицу поиска. Самый простой из них будет скудным (имеет 256 элементов), но он технически избегает итерации.

Этот комментарий здесь технически избегает итерации, но кто мы шутим, он все равно выполняет одинаковое количество проверок: как написать базу данных (2) в c / c ++

Закрытая форма будет log2 () , a la, log2() + 1 Но я не уверен, насколько это эффективно – возможно, у процессора есть инструкция для принятия логарифмов базы 2?

Основываясь на вычислении log2 в Find, найдите базу данных 2 N-разрядного целого числа в операциях O (lg (N)) :

 int getSetBitLocation(unsigned char c) { // c is in {1, 2, 4, 8, 16, 32, 64, 128}, returned values are {0, 1, ..., 7} return (((c & 0xAA) != 0) | (((c & 0xCC) != 0) << 1) | (((c & 0xF0) != 0) << 2)); } 

если вы определите

 const char bytes[]={1,2,4,8,16,32,64,128} 

и использовать

 struct byte{ char data; int pos; } void assign(struct byte b,int i){ b.data=bytes[i]; b.pos=i } 

вам не нужно определять позицию установленного бита

Таблица поиска быстро и просто, когда CHAR_BIT == 8, но в некоторых системах CHAR_BIT == 16 или 32, и таблица поиска становится безумно громоздкой. Если вы рассматриваете таблицу поиска, я бы предложил ее обернуть; вместо этого сделайте его «функцией таблицы поиска», чтобы вы могли поменять логику, когда вам нужно оптимизировать.

Использование divide и conquer при выполнении двоичного поиска в отсортированном массиве включает сравнения на основе log2 CHAR_BIT . Этот код более сложный, включая инициализацию массива unsigned char для использования в качестве справочной таблицы для начала. После того как вы инициализировали такой массив, вы можете использовать bsearch для его поиска, например:

 #include  #include  void uchar_bit_init(unsigned char *table) { for (size_t x = 0; x < CHAR_BIT; x++) { table[x] = 1U << x; } } int uchar_compare(void const *x, void const *y) { char const *X = x, *Y = y; return (*X > *Y) - (*X < *Y); } size_t uchar_bit_lookup(unsigned char *table, unsigned char value) { unsigned char *position = bsearch(lookup, c, sizeof lookup, 1, char_compare); return position ? position - table + 1 : 0; } int main(void) { unsigned char lookup[CHAR_BIT]; uchar_bit_init(lookup); for (;;) { int c = getchar(); if (c == EOF) { break; } printf("Bit for %c found at %zu\n", c, uchar_bit_lookup(lookup, c)); } } 

PS Это звучит как микро-оптимизация. Получите свое решение (абстрагирование операций, требуемых для этих функций), а затем подумайте об оптимизации на основе профилирования. Убедитесь, что профилирование нацелено на систему, в которой ваше решение будет работать, если вы собираетесь сосредоточиться на микрооптимизации, поскольку эффективность микрооптимизации сильно различается, поскольку аппаратное обеспечение отличается даже немного ... Обычно лучше купить более быстрый ПК;)