def median(numbers, rangebits):
	assert max(numbers) < 1 << rangebits, numbers
	assert len(numbers) % 2 == 1
	value = 0
	lower = 0
	higher = 0
	for bit in xrange(rangebits):
		mask = ((1 << bit) - 1) << (rangebits - bit)
		bitcounts = [0, 0]
		for num in numbers:
			if (num & mask) == value:
				bitcounts[(num >> (rangebits - bit - 1)) & 1] += 1
		lowcount = lower + bitcounts[0]
		highcount = higher + bitcounts[1]
		if lowcount < highcount:
			value |= 1 << (rangebits - bit - 1)
			lower = lowcount
		elif lowcount > highcount:
			higher = highcount
		else:
			assert False
		#print hex(value), hex(mask), bitcounts, lower, higher
	return value

if __name__ == '__main__':
	from random import randrange, shuffle
	for i in xrange(1000):
		r = randrange(100, 10000) * 2 + 1
		print 'case %d, range %d' % (i, r)
		a = range(r)
		shuffle(a)
		b = 0
		while 1 << b < r:
			b += 1
		assert median(a, b) == r / 2