How to find the index of the left-most 1 bit for x=2^k?

Question

Possible Duplicate:
Efficient bitwise operations for counting bits or find the right|left most ones

I wrote a search algorithm. In order to optimize it, I want to use a 32bit int to mark if number 0~31 could be used. That is, if I have a state State, I could easily fetch all possible number by using:

x = State & -State
State -= x

But actually, I need to know where is the 1 in x (notice that there is only 1 in x's binary form)? For example, if x = 0000 0100, I want to know that is the third.

I know I could do that by using a for loop, but it seems that it would cost much time.

I wonder that if there is a method using bitwise operation? And would static_cast<int>(log2(x)) costs much time?

Thanks for any help.

If you only have one bit set and are doing this to optimize, why not store the data in a 5 bit integer instead? — Joachim Isaksson, Sep 28 '12 at 09:12
Edit your title, please. It seems you ask if `x` is given. It may be confusing. — Leri, Sep 28 '12 at 09:13
I asked a similar question some time ago. I think the only way is to use compiler builtin, if you don't want to use a for loop. — Heisenbug, Sep 28 '12 at 09:14
@JoachimIsaksson Sorry, I couldn't understand what you said. My previous method was using a bool[32] to store it. — abcdabcd987, Sep 28 '12 at 09:15
@Heisenbug: sort of depends what you mean by "use a for loop". http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog has some methods with a loop that only counts to 5, so it's entirely practical to unroll that manually and say that you're not using a loop. I'm not sure exactly where the limit is that it's "cheating" to claim you've avoided a loop by unrolling. I think it depends on the size of the loop body and is less than 32, though. — Steve Jessop, Sep 28 '12 at 09:17
@abcdabcd987 What I'm saying is that if only one bit is set at a time, there are only 32 possible values. It's easier to just store that value in a byte than to calculate it from where the bit is set in an integer. — Joachim Isaksson, Sep 28 '12 at 09:20
@JoachimIsaksson Oh, I see. But I'm afraid that all bits will be used. Thanks anyway. — abcdabcd987, Sep 28 '12 at 09:22
@abcdabcd987: there still seems to be confusion. If, as you say in your question, there is only one 1 in the number, then you could just store the bit-number instead of the mask. Basically, now you are storing "1< — Christian Stieber, Sep 28 '12 at 09:28

score 3 · Accepted Answer · answered Sep 28 '12 at 09:28

3

Many CPUs have a native hardware instruction, something like CTZ ("count trailing zeros"). GCC exposes this through the built-in function __builtin_ctz; other compilers should have similar facilities.

answered Sep 28 '12 at 09:28

Kerrek SB

464,522
92
875
1,084

`__builtin_ffs` actually – abcdabcd987 Sep 28 '12 at 10:56
@abcdabcd987: oh, indeed -- they're very similar, aren't they? – Kerrek SB Sep 28 '12 at 12:05

score 3 · Answer 2 · answered Sep 28 '12 at 09:45

Nobody seems to have mentioned the obvious solution - to use a giant switch for all possible powers of two.

The below code implements this, plus binary search and division by two.

NOTE: these functions expect that the input will be a power of two; they may return nonsense if it is not.

#include <inttypes.h>
#include <stdio.h>

int get_exp_switch (uint64_t x)
{
    switch (x) {
        case (uint64_t)1 << 0: return 0;
        case (uint64_t)1 << 1: return 1;
        case (uint64_t)1 << 2: return 2;
        case (uint64_t)1 << 3: return 3;
        case (uint64_t)1 << 4: return 4;
        case (uint64_t)1 << 5: return 5;
        case (uint64_t)1 << 6: return 6;
        case (uint64_t)1 << 7: return 7;
        case (uint64_t)1 << 8: return 8;
        case (uint64_t)1 << 9: return 9;
        case (uint64_t)1 << 10: return 10;
        case (uint64_t)1 << 11: return 11;
        case (uint64_t)1 << 12: return 12;
        case (uint64_t)1 << 13: return 13;
        case (uint64_t)1 << 14: return 14;
        case (uint64_t)1 << 15: return 15;
        case (uint64_t)1 << 16: return 16;
        case (uint64_t)1 << 17: return 17;
        case (uint64_t)1 << 18: return 18;
        case (uint64_t)1 << 19: return 19;
        case (uint64_t)1 << 20: return 20;
        case (uint64_t)1 << 21: return 21;
        case (uint64_t)1 << 22: return 22;
        case (uint64_t)1 << 23: return 23;
        case (uint64_t)1 << 24: return 24;
        case (uint64_t)1 << 25: return 25;
        case (uint64_t)1 << 26: return 26;
        case (uint64_t)1 << 27: return 27;
        case (uint64_t)1 << 28: return 28;
        case (uint64_t)1 << 29: return 29;
        case (uint64_t)1 << 30: return 30;
        case (uint64_t)1 << 31: return 31;
        case (uint64_t)1 << 32: return 32;
        case (uint64_t)1 << 33: return 33;
        case (uint64_t)1 << 34: return 34;
        case (uint64_t)1 << 35: return 35;
        case (uint64_t)1 << 36: return 36;
        case (uint64_t)1 << 37: return 37;
        case (uint64_t)1 << 38: return 38;
        case (uint64_t)1 << 39: return 39;
        case (uint64_t)1 << 40: return 40;
        case (uint64_t)1 << 41: return 41;
        case (uint64_t)1 << 42: return 42;
        case (uint64_t)1 << 43: return 43;
        case (uint64_t)1 << 44: return 44;
        case (uint64_t)1 << 45: return 45;
        case (uint64_t)1 << 46: return 46;
        case (uint64_t)1 << 47: return 47;
        case (uint64_t)1 << 48: return 48;
        case (uint64_t)1 << 49: return 49;
        case (uint64_t)1 << 50: return 50;
        case (uint64_t)1 << 51: return 51;
        case (uint64_t)1 << 52: return 52;
        case (uint64_t)1 << 53: return 53;
        case (uint64_t)1 << 54: return 54;
        case (uint64_t)1 << 55: return 55;
        case (uint64_t)1 << 56: return 56;
        case (uint64_t)1 << 57: return 57;
        case (uint64_t)1 << 58: return 58;
        case (uint64_t)1 << 59: return 59;
        case (uint64_t)1 << 60: return 60;
        case (uint64_t)1 << 61: return 61;
        case (uint64_t)1 << 62: return 62;
        case (uint64_t)1 << 63: return 63;
        default: return 0; // not allowed
    }
}

int get_exp_simple (uint64_t x)
{
    int i = -1;
    do {
        i++;
        x /= 2;
    } while (x > 0);
    return i;
}

int get_exp_binsearch (uint64_t x)
{
    int left = 63;
    int right = 0;

    while (left > right) {
        int middle = (left + right) / 2;
        uint64_t middle_value = (uint64_t)1 << middle;
        if (x < middle_value) {
            left = middle - 1;
        }
        else if (x > middle_value) {
            right = middle + 1;
        }
        else {
            return middle;
        }
    }

    return left;
}

int main ()
{
    uint64_t sum = 0;

    for (int j = 0; j < 100000; j++) {
        for (int i = 0; i < 64; i++) {
            uint64_t x = (uint64_t)1 << i;
            int l = get_exp_switch(x);
            //int l = get_exp_simple(x);
            //int l = get_exp_binsearch(x);
            sum += l;
            //printf("%" PRIu64 ": %d\n", x, l);
        }
    }

    printf("%" PRIu64 "\n", sum);

    return 0;
}

Benchmark results on my (64-bit) system with clang -O2:

get_exp_switch: 0m0.103s
get_exp_simple: 0m0.196s
get_exp_binsearch: 0m0.158s

However, note that as you use larger integers (bignum), the binary search method will quickly begin to outperform the simple method, and the code size of the switch method may get unacceptably large.

wouldn't a simple shifting loop be more/at least as efficient? — Valmond, Sep 28 '12 at 11:57
Valmond: get_exp_simple() *is* a simple shifting loop, at least with any decent compiler with optimizations enabled. — Ambroz Bizjak, Sep 28 '12 at 12:02

score 1 · Answer 3 · answered Sep 28 '12 at 09:16

You can use the bit scaning tricks from here if you must go with bitwise operators, however, most compilers have intrisics for finding the first/last set bit, aka BitScanForward and BitScanReverse, these functions are very fast on modern processors and should be used (technically these are bitwise operations, that is, they operate on bits, they just don't have an operator form).

score 0 · Answer 4 · answered Sep 28 '12 at 09:50

You can do a log(n) search (pseudo c-code, havent tried it but should work, n equals the position):

STATE = 0010 0000
int bits=8;

int n=1;
while(bits>1)
{
    bits >>=1;//right shift 1
    int upper = STATE>>bits; //get the upper half
    if(upper)
    {
        n+=bits;
        STATE>>=bits;
    }
    //else the "1" is on the right side
}

You can also do a look-up in a pre created table, ie. do the loop above (as a 32bits table would probably take too much space space) but stop when (for example) bits==4 and do a look-up in a 16 bytes long look-up table (you would add that number to 'n').

How to find the index of the left-most 1 bit for x=2^k?

4 Answers4