# Demo entry 6362463

c++

Submitted by anonymous on May 09, 2017 at 04:26
Language: C++. Code size: 2.7 kB.

```/*
*  =>实现自己的hamming distance计算代码
*  =>面向图像特征描述子的计算要求
*    1. feature长度128,256，..千万
*    2. 实现在海量数据中快速匹配（笨的暴力匹配）
*/

#include <stdio.h>
#include <stdlib.h>

// 使用SSE
#include <nmmintrin.h>

#define USE_SSE4 1

//定义特征描述子的长度，
#define FEATURE_LENGTH  128

typedef unsigned long long  uint64;
typedef unsigned int        uint32;

//c 实现的简单的hamming distance 计算,原理
int hamming_dis(unsigned x, unsigned y)
{
int dist;
unsigned val;

dist = 0;
val = x ^ y;  // X OR Y hammming Dis 是异或计算的值中“1”的个数

while(val != 0) //统计val的二进制表示中“1”的个数
{
dist++;
val &= val - 1;
}
return dist;
}

//https://tekpool.wordpress.com/2006/09/25/bit-count-parallel-counting-mit-hakmem/
//实现二进制数据并行统计
int BitCount(unsigned int u)
{
unsigned int uCount;

uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;
}

// 计算uint64 长度的hamming distance
uint64 _m_hamming_distance_uint64(uint64 x, uint64 y)
{
uint64 dist;
uint64 val;

dist = 0;
val  =  x ^ y;

while(val != 0)
{
dist++;
val &= val - 1;
}
return dist;
}

//计算空间长度更长的hamming distance,
int _m_hamming_dis(const unsigned char* x, const unsigned char *y)
{
#ifdef USE_SSE4
uint64 dist;

uint64  *xx = (uint64 *)x;
uint64  *yy = (uint64 *)y;
dist = 0;

//此处可以尝试添加并行处理！
for(unsigned i = 0; i <FEATURE_LENGTH /( sizeof(uint64) * 8 ); ++i)
{
//dist += _m_hamming_distance_uint64(xx[i],yy[i]);
//printf("xx, yy, dist = %d, %d, %d\n",dist,xx[i],yy[i]);
dist += _mm_popcnt_u64(xx[i] ^ yy[i]);
}
return (int)dist;
#else
int dist;

uint64  *xx = (uint64 *)x;
uint64  *yy = (uint64 *)y;
dist = 0;

//此处可以尝试添加并行处理！
for(unsigned i = 0; i <FEATURE_LENGTH /( sizeof(uint64) * 8 ); ++i)
{
//dist += _m_hamming_distance_uint64(xx[i],yy[i]);
// 或者
dist += BigCount(xx[i] ^ yy[i])
}
return dist;
#endif
}

// 测试函数
int main()
{

//printf("ham_dis = %d",hamming_dis(4,8));

unsigned  *a = (unsigned *)malloc(256); //256  bit
unsigned  *b = (unsigned *)malloc(256); //256

for(unsigned i = 0; i < 256 /(sizeof(unsigned)*8); ++i)
{
a[i] = i + 1;
b[i] = i + 2;
printf("a,b = %d,%d\n",a[i],b[i]);
}

uint64 *aa = (uint64 *)a;
uint64 *bb = (uint64 *)b;

for(unsigned i = 0; i < 256/(sizeof(uint64)*8); ++i)
{
printf("aa,bb = %d, %d\n",aa[i],bb[i]);
}

//测试计算长数据hamming dis结果正确
printf("ham_dis = %d\n",_m_hamming_dis((const unsigned char *)a,(const unsigned char *)b));

system("pause");
return 0;
}
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.