Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation
The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption).  The practical running time may be different.  Asymptotics ignores constant factors, but constant factors can be important in practice.

The way to tell how much faster it is in practice is to implement it and do some experiments, i.e., benchmark it on realistic workloads.  Asymptotic analysis probably won't be very helpful in this case for predicting how much faster it will be.  No one is likely to be able to give you a prediction for what the results of those experiments will be; you'll just have to try it and see.