Recurse Center Day 8: Hamming Weight: I Am So Confused
I’m reimplementing my cryptopals
in Python, and today I worked a challenge that required me to
calculate the Hamming distance between two equal-length
strings. Hamming distance is a measure of difference - it indicates
how many corresponding characters in the input strings are
different. For example, the Hamming distance between
TART is 1. Well, that’s not entirely true. More often it’s more
relevant to determine the specific number of differing bits.
As you can see below, in this case, the strings differ by 3 bits.
Calculating Hamming Distance
Given two bytes, we can calculate their Hamming distance in two steps:
- XOR (exclusive or) the bytes
- Determine the Hamming weight of the XORed bytes
XOR the Bytes
Remember that Hamming distance is a measure of how many bits differ
between two equal-length strings. XOR is relevant because when
XORing two bytes, by the nature of the exclusive or operation, the
only time a
1 bit will appear in the resulting byte is when the two
input bits are different, and that’s exactly what we’re trying to
So for the above example:
01000001 ⨁ 01010100 = 00010101
Now all we need to do is count the number of occurrences of
the resulting bit string.
Enter Hamming Weight
Hamming weight is formally defined as the count of the
symbols in a string different than the zero-symbol of the given alphabet,
Hamming weight is especially useful for evaluating bit strings, which
are represented by an alphabet with two symbols,
1. So to
find the Hamming weight of a bit string is to simply count the number
1s in the string.
I Am So Confused
While I was able to implement a function for calculating the Hamming weight of a given byte , despite several attempts to understand how and why it works, I still don’t and I am very confused. I think the main issue is that I don’t entirely understand bitwise operations so I need to focus on addressing that before I delve into understanding Hamming weight implementations. If you know of any good resources for learning and practicing bitwise operations, will you tweet them at me please and thank you?