Hacker News new | ask | show | jobs
by hendzen 5148 days ago
Yes, the munching square picture is the same because the hamming distance of two binary numbers is their XOR.

As to why it looks similar to the visualization in the article, your hamming distance picture is essentially the multiplication table for a galois ring GF(2^n), where n is width of the bits of the binary numbers you were using.

Note that I say galois ring, not field; assuming that an n (for n even) bit unsigned binary number overflows as such: 0x00..01 + 0xFF..FF = 0x00..00, then your chart is the multiplication table of the ring formed by taking Z_2 modulo the ideal generated by the polynomial <x^n-1 + x^n-2 + ... + x^3 + x^2 + x + 1>, which is a ring since this polynomial is reducible (it has a root of 1).

2 comments

A quibble of terminology: fields are rings too, so what you want to say is that it's not a field (or that it's 'only a ring') because the polynomial is reducible, rather than that it's a ring because the polynomial is reducible. It's a ring because it satisfies all the necessary properties--whether the polynomial is reducible or not has no bearing at all on whether the object under discussion is a ring.
For binary strings a and b the Hamming distance is equal to the number of ones ( population count) in a XOR b.

Population count of x is not the same as x, so... how are the images the same?