Optimize Cython code with np.ndarray contained
As a general rule for optimizing with cython, try to avoid python function calls if possible, i.e. replace pythonic sum with numpy sum or explicit for loop, replace bit number table with numpy array, and try to declare types for all variables. 

You can also precalculate most of the variables used in distance calculation and use a separate array to hold minimum distances for each block. I quickly put something together and got the code below. 

Just wondering, what is the rationale for normalizing the distance with the number of set bits?

import cython
import numpy as np
cimport numpy as np

cdef bitCount(unsigned char value):
    cdef count = 0
    while(value):
        value &amp;= value - 1
        count += 1
    return(count)


def compare(np.ndarray[np.uint8_t, ndim=1, mode='c'] a, 
            np.ndarray[np.uint8_t, ndim=1, mode='c'] b):

    cdef int nblocksA = int(a.size/256)
    cdef int nblocksB = int(b.size/256)
    cdef int i, j, k

    cdef double partial_hamming_distance

    # Prepare a bit number table for fast query
    cdef np.ndarray[np.uint8_t, ndim=1] bits = np.zeros(256, dtype=np.uint8)
    for i in range(256):
        bits[i] = bitCount(i) 

    cdef np.ndarray[np.float_t, ndim=1] min_distances = np.ones(nblocksB,
                                                                dtype=np.float)
    min_distances *= 1000000

    cdef np.ndarray[np.float_t, ndim=1] set_bitsA = np.zeros(nblocksA, dtype=np.float)
    for i in range(nblocksA):
        for k in range(256):
            set_bitsA[i] += bits[a[k + 256 * i]]

    cdef np.ndarray[np.float_t, ndim=1] set_bitsB = np.zeros(nblocksB, dtype=np.float)
    for i in range(nblocksB):
        for k in range(256):
            set_bitsB[i] += bits[b[k + 256 * i]]

    for i in range(nblocksB):
        for j in range(nblocksA):
            partial_hamming_distance = 0

            for k in range(256):
                partial_hamming_distance += (bits[b[i*256+k] ^ a[j*256+k]] 
                                          / (set_bitsB[i] + set_bitsA[j]))

            if partial_hamming_distance &lt; min_distances[i]:
                min_distances[i] = partial_hamming_distance

    return np.sum(min_distances)