test/other/bitOps.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include "../util.h"
#include <other/bitOps.cpp>

void test_subsets() {
	int queries = 0;
	for (int i = 0; i < 1000'000; i++) {
		int mask = 0;
		int limBits = Random::integer<int>(1, 15);
		for (int j = 0; j < limBits; j++) {
			mask |= 1 << Random::integer<int>(0, 31);
		}

		int expeced = 1 << __builtin_popcount(mask);
		int last = -1;
		int seen = 1;
		subsets(mask, [&](int active){
			if (active <= 0) cerr << "error active: " << active << FAIL;
			if (last >= 0 && active >= last) cerr << "error active: " << active  << ", last: " << last << FAIL;
			last = active;
			seen++;
		});
		if (expeced != seen) cerr << "got: " << seen << ", expeced: " << expeced << FAIL;
		queries++;
	}
	cerr << "tested subsets queries: " << queries << endl;
}

ll naive(ll x) {
	vector<ll> bits;
	for (ll i = 0; i < 63; i++) {
		bits.push_back(x & 1);
		x >>= 1;
	}
	ranges::next_permutation(bits | views::reverse);
	x = 0;
	for (ll i = 0, j = 1; i < 63; i++, j <<= 1) {
		if (bits[i] != 0) x |= j;
	}
	return x;
}

void test_nextPerm() {
	int queries = 0;
	for (int i = 0; i < 1000'000; i++) {
		ll x = 4;//Random::integer<ll>(1, LL::INF);
		ll got = nextPerm(x);
		ll expeced = naive(x);
		if (got != expeced) cerr << x << ": got: " << got << ", expeced: " << expeced << FAIL;
		queries++;
	}
	cerr << "tested nextPerm queries: " << queries << endl;
}

int main() {
	test_subsets();
	test_nextPerm();
}