How to search list of numbers for a particular property

Question

I have a long list of numbers. There are no duplicates in the list and all numbers are representable with 2N bits.

For every pair of numbers, I can calculate whether a particular condition is true (whether the result of a bitwise XOR of the two numbers has exactly N bits set). If the condition is true, I say those two numbers are linked. I call the number of links a number has within a list its rank. I need to find one of the numbers in the list that has the highest rank.

I can do this in O(n²) by calculating each number's rank one by one.

Is it possible to do it faster?

Answer 1

How many bit sequences will meet the xor condition for any given number?

From the Central Limit Theorem, it is O(4^N/sqrt(N)). More to the point, if I give you the first 2N-10*sqrt(N) bits, odds are low that you can't conclude anything useful about whether it will meet your xor condition.

If 4^N < n, we can get a speedup by just going with a data structure of number to count. Rather than look at each number to find whether it has a particular bitsequence that meets the xor condition, we just count how many times number meeting the condition appears. But if n is too much smaller than that, most numbers won't have enough other numbers close enough to them to try to benefit out of analyzing them as a group.