How to binary compare the contents of two directories on Linux (recursively)

Run the following in both directories (change the output filename for the second):
find . -print0 | LC_ALL=C sort -z | xargs -0r md5sum > ../dir1.md5 2>&1

Compare the two resulting text files with eg. diff.
If you're interested only in files (and don't care for potential empty directories), then add -type f to the arguments of find.