计算Hamming Distance汉明距离速度对比

汉明距离 Hamming Distance
两个二进制数不同的位,的数量
比如:
bin 001000
bin 000100
————–
第三位和第四位不同,所以它们的汉明距离为2
参考[ref]:
https://www.cnblogs.com/grandyang/p/6201215.html
https://blog.csdn.net/chouisbo/article/details/54906909

 

第1种:查二维表法,事先建一张256*256的表hmd
第2种:Wegner (1960) 提出了一种计算汉明权重(即计算给定整数的二进制表示中1的个数)的算法,通过反复查找并消除最低的非零bit位来实现
第3种:移位
第4种:异或最末位,再移位

 

BYTE hmdistance1(BYTE a1, BYTE a2)
{
	return hmd[a1][a2];
}

BYTE hmdistance2(BYTE a1, BYTE a2)
{
	BYTE val = a1 ^ a2;
	int num1 = 0;
	while (val) {
		++num1;
		val &= val - 1;
	}
	return num1;
}


BYTE hmdistance3(BYTE a1, BYTE a2)
{
	BYTE val = a1 ^ a2;
	int num1 = 0;
	while (val) {
		if (val & 0x01)
			++num1;
		val >>= 1;
	}
	return num1;
}

BYTE hmdistance4(BYTE a1, BYTE a2)
{
	BYTE val1 = a1;
	BYTE val2 = a2;
	int num1 = 0;
	for(int i=0; i<8; i++)
	{
		if ((val1 & 0x1) ^ (val2 & 0x1))
			++num1;
		val1 >>= 1;
		val2 >>= 1;
	}
	return num1;
}

 

 

第1种:最快,废空间
第2种:节省空间的情况下最快
第3种、第4种:差不多,3稍快

移位操作测试

最近用到一个移位操作,需求:
有一个数,取值范围是(0~0x7FFF],不断做左移操作,直到大于0x8000

翻译成C代码如下:

void p1(u32* pArr, int count)
{
	u32 tmp = 0;
	int n = 0;
	int i = 0;

	for (i = 0; i < count; i++) {
		tmp = pArr[i];
		n = 0;
		do
		{
			tmp = (tmp << 1);
			n++;
		} while (tmp < 0x8000);
	}

}

那用下面的if来判断,然后直接左移n位,会不会快一点呢?

void p2(u32* pArr, int count)
{
	u32 tmp = 0;
	int n = 0;
	int i = 0;

	for (i = 0; i < count; i++) {
		n = 0;
		tmp = pArr[i];

		if (tmp & 0x4000)
			n = 1;
		else if (tmp & 0x2000)
			n = 2;
		else if (tmp & 0x1000)
			n = 3;
		else if (tmp & 0x800)
			n = 4;
		else if (tmp & 0x400)
			n = 5;
		else if (tmp & 0x200)
			n = 6;
		else if (tmp & 0x100)
			n = 7;
		else if (tmp & 0x80)
			n = 8;
		else if (tmp & 0x40)
			n = 9;
		else if (tmp & 0x20)
			n = 10;
		else if (tmp & 0x10)
			n = 11;
		else if (tmp & 0x8)
			n = 12;
		else if (tmp & 0x4)
			n = 13;
		else if (tmp & 0x2)
			n = 14;
		else if (tmp & 0x1)
			n = 15;

		tmp = tmp << n;
	}
}

 

实测:当count等于10^8时,p2会快大约1秒钟。下面是main函数

#include <windows.h>
#include <time.h>
#include <stdio.h>

#define u32 unsigned int
#define num 100000000

long long getTime()
{
	return GetTickCount();
}

int main()
{
	long long start;
	long long end;
	u32* arr = NULL;

	srand((unsigned)getTime());
	arr = (u32 *)malloc(sizeof(u32)*num);
	if (arr == NULL)
		return 1;
	
	for (u32 i = 0; i < num; i++)
	{
		arr[i] = ((rand() % 0x7) + 1)<<12;
	}
	printf("start:\r\n");
	start = getTime();
	p1(arr, num);
	end = getTime();

	printf("p1: %lld\r\n", (end - start));

	start = getTime();
	p2(arr, num);
	end = getTime();

	printf("p2: %lld\r\n", (end - start));
	free(arr);
	getchar();
    return 0;
}

 

 

java.lang.UnsatisfiedLinkError: no XXX in java.library.path

其中涉及的测试源码如下:

For those who didn’t install Java with default settings, a systematic way for solving JNI class path problem is:
1> include “System.out.println(System.getProperty(“Java.library.path”)); ” in your “static” block, right before loading the class.
2> run your program and not surprisingly you got the err again, but this time with java.library.path info for your system. (it’s important since this path name varies among systems).
3> cp your libxxx.so into the java.library.path

 

Java一般使用两个path:classpath 和 java.library.path

classpath是指向jar包的位置

java.library.path是非java类包的位置如(dll,so)

解决办法:

第一种方法,在代码里设置环境变量

第二种方法:执行时在vm arguments里添加-Djava.library.path= /usr/local/lib,例如java -Djava.library.path=.   xxx(xxx是某个类文件的名字,不包括后缀)

第三种方法:设置环境变量java.library.path

1:Linux下的系统变量LD_LIBRARY_PATH来添加java.library.path

2:Windows下设置哪个环境变量???????????????????

 

如果你上面看不懂的话就继续向下面看:
1、 在你载入jni类之前 放入“System.out.println( System.getProperty(“java.library.path”));
2、运行你的程序你将获得java.library.path指向的目录
3、拷贝你的libxxx.so到java.library.path指向的某个目录下面。
注意:
Linux下:一定要将Linux下的共享库(我暂且这么叫:)命名成libxxx.so的形式,”xxx”是你在System.loadLibrary(“xxx“)中用到的加载库名称。

Windows下:一定要将Windows下的共享库(我暂且这么叫:)命名成xxx.dll的形式(没有前边的lib三个字母),”xxx”是你在System.loadLibrary(“xxx“)中用到的加载库名称。

 

查了其他的资料:
也可以通过设置LINUX下的系统变量LD_LIBRARY_PATH来添加java.library.path,只要在启动~/.bashrc中添加如下代码然后重新登录shell,就可以将动态库放在当前目录下运行你的jni程序了。
export LD_LIBRARY_PATH=.:..:$LD_LIBRARY_PATH

另外也可以通过如下I’m new to JNI. I see there are several ways to set JVM to look for libraries dll, so, etc.

 

System.setProperty(“java.library.path”, “.”);
System.loadLibrary(“hello”);
That’s when UnsatisfiedLinkError

java.lang.UnsatisfiedLinkError: no hello in java.library.path
at java.lang.ClassLoader.loadLibrary(ClassLoader.java:1682)
at java.lang.Runtime.loadLibrary0(Runtime.java:822)
at java.lang.System.loadLibrary(System.java:992)
at HelloWorld.main(HelloWorld.java:17)