Быстрый способ определить самый правый п-й бит установлен в 64 бит

Question

Я стараюсь, чтобы определить самый правый п-й бит установлен

if (value & (1 << 0)) { return 0; } 
if (value & (1 << 1)) { return 1; } 
if (value & (1 << 2)) { return 2; } 
... 
if (value & (1 << 63)) { return 63; } 

, если нужно сделать 64 раз в сравнении. Есть ли более быстрый способ?

Answer 1

работы для Visual C++ 6

int toErrorCodeBit(__int64 value) { 
    const int low_double_word = value; 
    int result = 0; 

    __asm 
    { 
     bsf eax, low_double_word 
     jz low_double_value_0 
     mov result, eax 
    } 
    return result; 

low_double_value_0:  
    const int upper_double_word = value >> 32; 

    __asm 
    { 
     bsf eax, upper_double_word 
     mov result, eax 
    } 
    result += 32; 
    return result; 
} 

Answer 2

Там есть маленькая хитрость для этого:

value & -value 

Это использует комплемент целое представление двоек отрицательных чисел.

Редактировать: Это не совсем дает точный результат, как указано в вопросе. Остальное можно сделать с помощью небольшой таблицы поиска.

Answer 3

Если вы используете GCC, используйте функцию или __builtin_ffs. (http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005fffs-2894)

Если вы используете MSVC, используйте функцию _BitScanForward. См. How to use MSVC intrinsics to get the equivalent of this GCC code?.

В POSIX есть также функция ffs. (http://linux.die.net/man/3/ffs)

Answer 4

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

int result = 0; 
if (!(value & 0xffffffff)) { 
    result += 32; 
    value >>= 32; 
} 

if (!(value & 0xffff)) { 
    result += 16; 
    value >>= 16; 
} 

и так далее. Это будет делать 6 сравнений (в общем, log (N) сравнения, против N для линейного поиска).

Answer 5

Вы можете использовать цикл:

unsigned int value; 
unsigned int temp_value; 
const unsigned int BITS_IN_INT = sizeof(int)/CHAR_BIT; 
unsigned int index = 0; 

// Make a copy of the value, to alter. 
temp_value = value; 
for (index = 0; index < BITS_IN_INT; ++index) 
{ 
    if (temp_value & 1) 
    { 
     break; 
    } 
    temp_value >>= 1; 
} 
return index; 

Это занимает меньше места, чем код предложения в if заявление, с аналогичной функциональностью.

Answer 6

Вот еще один метод, который использует короткое замыкание с логическими операциями И и выполнением условных команд или конвейером команд.

unsigned int value; 

unsigned int temp_value = value; 
bool bit_found = false; 
unsigned int index = 0; 

bit_found = !bit_found && ((temp_value & (1 << index++)); // bit 0 
bit_found = !bit_found && ((temp_value & (1 << index++)); // bit 1 
bit_found = !bit_found && ((temp_value & (1 << index++)); // bit 2 
bit_found = !bit_found && ((temp_value & (1 << index++)); // bit 3 
//... 
bit_found = !bit_found && ((temp_value & (1 << index++)); // bit 64 
return index - 1; // The -1 may not be necessary depending on the starting bit number. 

Преимущество этого метода в том, что нет ветвей, и конвейер команд не нарушен. Это происходит очень быстро на процессорах, которые выполняют условное выполнение инструкций.

Answer 7

 
b = n & (-n)  // finds the bit 
b -= 1;   // this gives 1's to the right 
b--;    // this gets us just the trailing 1's that need counting 
b = (b & 0x5555555555555555) + ((b>>1) & 0x5555555555555555); // 2 bit sums of 1 bit numbers 
b = (b & 0x3333333333333333) + ((b>>2) & 0x3333333333333333); // 4 bit sums of 2 bit numbers 
b = (b & 0x0f0f0f0f0f0f0f0f) + ((b>>4) & 0x0f0f0f0f0f0f0f0f); // 8 bit sums of 4 bit numbers 
b = (b & 0x00ff00ff00ff00ff) + ((b>>8) & 0x00ff00ff00ff00ff); // 16 bit sums of 8 bit numbers 
b = (b & 0x0000ffff0000ffff) + ((b>>16) & 0x0000ffff0000ffff); // 32 bit sums of 16 bit numbers 
b = (b & 0x00000000ffffffff) + ((b>>32) & 0x00000000ffffffff); // sum of 32 bit numbers 
b &= 63; // otherwise I think an input of 0 would produce 64 for a result. 

Это, конечно, C.