Skip to content

Instantly share code, notes, and snippets.

@joriki
Created January 26, 2020 23:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save joriki/51c19e37c22e2d3eb7d6d120b441fbb8 to your computer and use it in GitHub Desktop.
Save joriki/51c19e37c22e2d3eb7d6d120b441fbb8 to your computer and use it in GitHub Desktop.
Compute the minimum Hamming distance among three bit strings; see https://math.stackexchange.com/questions/3523712.
import java.util.Random;
public class Question3523712 {
final static long ntrials = 10000028000;
final static Random random = new Random();
public static void main (String [] args) {
long sum = 0;
for (long k = 0;k < ntrials;k++) {
long a = random.nextLong();
long b = random.nextLong();
long c = random.nextLong();
sum += Math.min(Math.min(hamming(a, b),hamming(b, c)),hamming(c, a));
}
System.out.println(sum / (double) ntrials);
}
static int hamming(long a,long b) {
int hamming = 0;
for (int i = 0;i < 64;i++) {
if ((a & 1) != (b & 1))
hamming++;
a >>= 1;
b >>= 1;
}
return hamming;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment