Various step count function for Collatz 3n+1 problem

collatz.cpp

#include <stdint.h>
#include <windows.h>
#include <intrin.h>

uint64_t collatz_count_ref(uint64_t n) {
	uint64_t count = 0;
	while (n > 1) {
		n = (n % 2 == 1) ? 3 * n + 1 : n >> 1;
		count++;
	}
	return count;
}

inline uint64_t collatz_count_opt_x(
	uint64_t n, 
	void(*even_update)(uint64_t&, uint64_t&)
) {
	uint64_t count = 0;

	if (n > 1) {
		switch (n & 1) {
			case 1: do {
				// 奇数
				n = 3 * n + 1;
				count++;
			default:
				//偶数
				even_update(n, count);
			} while (n > 1);
		}
	}
	return count;
}

#define GEN(fname, divfunc) \
uint64_t fname(uint64_t n) { \
	return collatz_count_opt_x(n, divfunc);\
}
#define _ [](uint64_t& n, uint64_t& count)

GEN(collatz_count_opt_narrow, _{
	while (!(n & 1)) {
		n = n >> 1;
		count++;
	}
})

GEN(collatz_count_opt_bsf, _{
	unsigned long c; // counter of leading zero
	_BitScanForward64(&c, n);
	n = n >> c;
	count += c;
})

GEN(collatz_count_opt_tzcnt, _{
	DWORD64 c = _tzcnt_u64(n);
	n = n >> c;
	count += c;
})

GEN(collatz_count_opt_popcnt, _{
	DWORD64 c = __popcnt64((n & (0 - n)) - 1);
	n = n >> c;
	count += c;
})

#undef _
#undef GEN