Могу ли я сделать это без итерации?
blockquote>Это действительно возможно.
Как я наиболее эффективно определяю позицию набора бит?
blockquote>Вы можете попробовать этот алгоритм. Он разбивает символ пополам, чтобы найти верхний бит, каждый раз переходя на нижнюю половину:
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
s, четыре дляuint32
s. ..). и это может быть быстрее, чем ваш цикл.
Основываясь на идее Антона Коваленко (хешированный поиск) и комментария на 6502 (деление медленное), я также предлагаю эту реализацию (8-бит => 3 (g0)
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]; }