https://twitter.com/David3141593/status/1200184568650878979

fast_sideways_xor.py

import random
import time

def cursed(x):
	return format(x, "b").count("1") % 2

def woke(x):
	while x > 1:
		midpoint = x.bit_length()//2
		mask = (1<<midpoint)-1
		x = x >> midpoint ^ (x & mask)
	return x

def hybrid(x):
	while x.bit_length() > 512:
		midpoint = x.bit_length()//2
		mask = (1<<midpoint)-1
		x = x >> midpoint ^ (x & mask)
	return format(x, "b").count("1") % 2


def bench(bitlen, iters, func):
	inputs = [random.getrandbits(bitlen) for i in range(iters)]
	start = time.time()
	for test in inputs:
		result = func(test)
	return (time.time()-start)/iters

# sanity check
for i in range(1000):
	test = random.getrandbits(1000)
	assert(cursed(test) == woke(test) == hybrid(test))

# benchmark
for bitlen in [64, 512, 1000, 0x10000]:
	print("bitlen={}:".format(bitlen))
	print("cursed: t={}ns".format(int(bench(bitlen, 10000, cursed)*1e9)))
	print("woke:   t={}ns".format(int(bench(bitlen, 10000, woke)*1e9)))
	print("hybrid: t={}ns".format(int(bench(bitlen, 10000, hybrid)*1e9)))

"""
bitlen=64:
cursed: t=869ns
woke:   t=1959ns
hybrid: t=1037ns
bitlen=512:
cursed: t=3627ns
woke:   t=3211ns
hybrid: t=3763ns
bitlen=1000:
cursed: t=6620ns
woke:   t=3781ns
hybrid: t=4329ns
bitlen=65536:
cursed: t=380169ns
woke:   t=17289ns
hybrid: t=18015ns
"""