A quick way to determine the right of the majority of the nth bit set in 64-bit

Question

I am trying to determine the correct bit of the nth bit

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

if the comparison needs to be done 64 times. Is there a faster way?

Answer 1

Works for 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

There is a little trick:

value & -value

This uses a binary integer representation of negative numbers.

Edit: This does not quite give the exact result as indicated in the question. The rest can be done using a small lookup table.

Answer 3

GCC, __builtin_ctz __builtin_ffs. (http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005fffs-2894)

MSVC, _BitScanForward. . MSVC GCC?.

POSIX ffs. (http://linux.die.net/man/3/ffs)

Answer 4

:

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 5

KennyTM , . , :

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

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

.. 6 ( , log (N) , N ).

Answer 6

b = n & (-n)      // finds the bit
b -= 1;           // this gives 1 to the right
b--;              // this gets us just the trailing 1 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.

This, of course, is in C.

Answer 7

Here's another method that takes advantage of a short circuit with logical AND operations and conditional commands or an instruction pipeline.

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.

The advantage of this method is that there are no branches, and the command pipeline is not broken. It is very fast on processors that execute conditional execution of instructions.