Skip to content

Instantly share code, notes, and snippets.

@andr1972
Last active August 31, 2022 17:44
Show Gist options
  • Save andr1972/b9e048797c5479b29e40707807f2d392 to your computer and use it in GitHub Desktop.
Save andr1972/b9e048797c5479b29e40707807f2d392 to your computer and use it in GitHub Desktop.
Find first set bit from position and to position
/* 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;
}
@andr1972
Copy link
Author

better -1 as not_found

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment