Computing Hamming Distance Between Binary Vectors
You say in the comments that we might have $c \approx 15$ or so. There should be very efficient algorithms in this case, using locality sensitive hashing.

For example, here is a simple LSH.  Randomly choose a set of about 10,000 indices (out of the 1,000,000).  Hash each vector by computing some standard hash of the 10,000 bits in those positions (ignoring the other 990,000 bits entirely).  Store all the vectors in a hashtable using this hash.  Now look for all pairs of vectors that have the same hash.  This can be done by storing all the vectors in a hashtable using this hash and looking at all collisions within a single hash bucket, or by sorting the hashes and looking at adjacent pairs.

Suppose the pair of vectors $b_i,b_j$ are at distance $\le 15$.  Then with probability about 0.86, they will agree in the selected 10,000 positions and thus have the same hash.  In other words, about 86% of the pairs of vectors at distance $\le 15$ will be found in this way. 

Now you can repeat this multiple times to ensure you find all of the pairs, with high likelihood.  If you repeat this about 10 times with a different random set of indices each time, then only about $10^{-8}$ of the pairs that are close will be missed.  If you repeat it 100 times, each close pair has only a $10^{-85}$ probability to be missed.  That probability is so low it can be safely ignored: essentially, all close pairs will be found.

The running time is $O(n^2)$: $O(n)$ time to compute each hash, and then you do that $n$ times for $n$ different vectors.  In practice it might be even faster than that if you can take advantage of the fact that most of the bit positions are ignored during the hashing.