Calculate hamming distance of bloom filters in c?

Question

I need to compare two equal sized bloom filters BF1 and BF2 for their similarity using hamming distance which expresses the distance between the two sets as Bloom Distance

B(BF1,BF2)=one(BF1 & BF2)/SIZEOF(BF1)
Where the one() function counts number of set bits in the ANDed bloom filter.

I adopted this formula from Path similarity evaluation using Bloom filters section 3(page 4. Similarity metrics).

I have implemented the following c code to do it but it definitely is not working.

#include <stdlib.h>
#include <stdio.h>
const int BF_LEN= 1024;

char *BF1;//=malloc(BF_LEN*sizeof(char));
char *BF2;//=malloc(BF_LEN*sizeof(char));
char *buf;//=malloc(BF_LEN*sizeof(char));
char *buf_ptr=NULL;
int set_bits_count=0;
float similarity=0.0;

u_int32_t NumberOfSetBits(u_int32_t i)
{
    return (((((i - ((i >> 1) & 0x55555555)) & 0x33333333) + (((i - ((i >> 1) & 0x55555555)) >> 2) & 0x33333333) + (((i - ((i >> 1) & 0x55555555)) & 0x33333333) + (((i - ((i >> 1) & 0x55555555)) >> 2) & 0x33333333) >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

void main()
{
    BF1=malloc(BF_LEN*sizeof(char));
    BF2=malloc(BF_LEN*sizeof(char));
    buf=malloc(BF_LEN*sizeof(char));
 //Edit2:initialize them to 0
for(int j=0;j<BF_LEN;j++)    
        {
            BF1[j]='\0';
            BF2[j]='\0';
            buf[j]='\0';
        }
    BF1="BF1 is filled with some characters";
    BF2="BF2 is filled with some characters and more";

    for(int j=0; j<BF_LEN; j++)
    {
        buf[j]=BF1[j]&BF2[j];
    }

    buf_ptr=buf;

    for(int m=0; m<BF_LEN; m++) //This is for the **one()** function
        set_bits_count+=NumberOfSetBits(*buf_ptr++);

    similarity=1-set_bits_count/(float)BF_LEN;
    printf("%.2f",similarity);
//Edit1: Following Comments
    free(BF1);
    free(BF2);
    free(buf);
}

NumberOfSetBits() Adopted from Set bit counter

Answer 1

Please have a try with this code. Hamming distance is the population count with XOR:

 void hamming()
 {
    static const unsigned int BF_LEN = 1024;

    char BF1[BF_LEN];
    char BF2[BF_LEN];

    unsigned int set_bits_count = 0;
    float similarity = 0.0f;

    memset(BF1,'\0',BF_LEN);
    memset(BF2,'\0',BF_LEN);
    strcpy(BF1, "BF1 is filled with some characters");
    strcpy(BF2, "BF2 is filled with some characters and more");

    for(unsigned int j = 0; j < BF_LEN; j += sizeof(T_Uint32))
    {
        set_bits_count += hammingDistance(*(T_Uint32*)&BF1[j], *(T_Uint32*)&BF2[j]);
    }


    similarity = 1.0f - set_bits_count/(float)BF_LEN;
    printf("%.2f", similarity);
}

//Reference: P. Wegner, Comm. ACM, Vol. 3, Issue 5, 1960. 
T_Uint getNrOfBitsSet(T_Uint32 bits)
{     
  T_Uint bitsSet = 0;

  while (bits)
  {
    bits &= bits - 1; // clears the least significant bit set
    ++bitsSet;
  }
  return bitsSet;
}

T_Uint hammingDistance(T_Uint32 a, T_Uint32 b)
{
    return getNrOfBitsSet(a^b);
}