Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0-1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arithmetic 0-1 matrix multiplication to computing all-pairs distances in a Hamming space. On the other hand, we present a fast randomized algorithm for approximate all-pairs distances in a Hamming space. By combining it with our reduction, we obtain also a fast randomized algorithm for approximate 0-1 matrix multiplication. Next, we present an output-sensitive randomized algorithm for a minimum spanning tree of a set of points in a generalized Hamming space, the lower is the cost of the minimum spanning tree the faster is our algorithm. Finally, we provide ((2+\epsilon))- approximation algorithms for the (\ell)-center clustering and minimum-diameter (\ell)-clustering problems in a Hamming space (\{0,1\}^d) that are substantially faster than the known (2)-approximation ones when both (\ell) and (d) are super-logarithmic.