Find first set bit from position and to position

findbit.cpp

/* Is useful for searching empty slot */
#include <cstring>
#include <cstdio>
#include <cassert>
#include <chrono>
#include <cstdlib>
#include <exception>

using namespace std;

class stopwatch
{
public:
    chrono::time_point<chrono::high_resolution_clock> a, b;
    void start() { a = chrono::high_resolution_clock::now(); }
    void stop() { b = chrono::high_resolution_clock::now(); }
    double duration()
    {
        chrono::duration<double> elapsed_seconds = b - a;
        return elapsed_seconds.count();
    }
};

typedef uint64_t bitType;
const static int bitsInWord = sizeof(bitType) * 8;

static int ffs_first(bitType x) {
    return ffsll(x)-1;
}

int ffs_from(bitType x, int from) {
    assert(from>=0 && from <bitsInWord);
    bitType mask = bitType(-1) << from;
    return ffsll(x & mask)-1;
}

int ffs_to(bitType x, int to) {
    assert(to >= 0 && to < bitsInWord);
    bitType mask = ((bitType)1<< to) - 1;
    return ffsll(x & mask)-1;
}


int ffs_from_iter(bitType x, int from) {
    for (int i=from; i<bitsInWord; i++) {
        if (x & ((bitType)1<<i)) return i;
    }
    return -1;
}

int ffs_to_iter(bitType x, int to) {
    for (int i=0; i<to; i++) {
        if (x & ((bitType)1<<i)) return i;
    }
    return -1;
}

void test_from() {
    for (int i=0; i<bitsInWord; i++)
        for (int j=0; j<bitsInWord; j++) {
            int r1 =ffs_from((bitType)1<<i, j);
            int r2 = ffs_from_iter((bitType)1<<i, j);
            if (r1!=r2) throw std::exception();
        }
}


void test_to() {
    for (int i=0; i<bitsInWord; i++)
        for (int j=0; j<bitsInWord; j++) {
            int r1 =ffs_to((bitType)1<<i, j);
            int r2 = ffs_to_iter((bitType)1<<i, j);
            if (r1!=r2) throw std::exception();
        }
}

int bench() {
    int sum = 0;//against too aggresive optimalization with elimination whole expression
    const int loopCnt = 10;
    stopwatch st;
    double mindur = 1e80;
    for (int ll=0; ll<loopCnt; ll++)
    {
        st.start();
        for (int k = 0; k < 1000; k++)
            for (int i = 0; i < bitsInWord; i++)
                for (int j = 0; j < bitsInWord; j++) {
                    sum += ffs_from_iter((bitType)1<< i, j);
                }
        st.stop();
        double dur = st.duration();
        if (dur<mindur)
            mindur=dur;
    }
    printf("iter %f ns\n", mindur * 1e6 /bitsInWord/bitsInWord);

    mindur = 1e80;
    for (int ll=0; ll<loopCnt; ll++)
    {
        st.start();
        for (int k = 0; k < 1000; k++)
            for (int i = 0; i < bitsInWord; i++)
                for (int j = 0; j < bitsInWord; j++) {
                    sum += ffs_from((bitType)1<< i, j);
                }
        st.stop();
        double dur = st.duration();
        if (dur<mindur)
            mindur=dur;
    }
    printf("ffs %f ns\n", mindur * 1e6 /bitsInWord/bitsInWord);

    mindur = 1e80;
    for (int ll=0; ll<loopCnt; ll++)
    {
        st.start();
        for (int k = 0; k < 1000; k++)
            for (int i = 0; i < bitsInWord; i++)
                    sum += ffs_first((bitType)1<< i);
        st.stop();
        double dur = st.duration();
        if (dur<mindur)
            mindur=dur;
    }
    printf("ffs_first %f ns\n", mindur * 1e6 /bitsInWord);
    return sum;
}

int main() {
    test_from();
    test_to();
    bench();
    return 0;
}

removed if (!x) return 32

64 bit, faster

simplified ffs_first

better -1 as not_found