Fast way to determine right most nth bit set in a 64 bit

Question

I try to determine the right most nth bit set

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 comparison needs to be done 64 times. Is there any faster way?

Answer 1

There's a little trick for this:

value & -value

This uses the twos' complement integer representation of negative numbers.

Edit: This doesn't quite give the exact result as given in the question. The rest can be done with a small lookup table.

Answer 2

If you're using GCC, use the __builtin_ctz or __builtin_ffs function. (http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005fffs-2894)

If you're using MSVC, use the _BitScanForward function. See http://stackoverflow.com/questions/355967/how-to-use-msvc-intrinsics-to-get-the-equivalent-of-this-gcc-code.

In POSIX there's also a ffs function. (http://linux.die.net/man/3/ffs)

Answer 3

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 4

KennyTM's suggestions are good if your compiler supports them. Otherwise, you can speed it up using a binary search, something like:

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

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

and so on. This will do 6 comparisons (in general, log(N) comparisons, versus N for a linear search).

Answer 5

You could use a loop:

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;

This takes up less code space than the if statement proposal, with similar functionality.

Answer 6

Here's another method that takes advantage of short-circuit with logical AND operations and conditional instruction execution or the 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 to this method is that there are no branches and the instruction pipeline is not disturbed. This is very fast on processors that perform conditional execution of instructions.