二进制数字中1的个数

Posted on by — No Comments ↓ 
#include "stdafx.h"
#include <nmmintrin.h>

/*
 *通过移位计算1的个数
 *每一位都要判断和处理
 */
int BitCount(unsigned int n)
{
	unsigned int c = 0;
	while (n >0)
	{
		if ((n & 1) == 1)++c;
		n >>= 1;
	}
	return c;
}

/*
 *通过减法及位运算，保证每次至少消除一个1
 *只处理1的位，0的位不处理
 */
int BitCountWithMinus(unsigned int n)
{
	unsigned int c = 0;
	for (c = 0; n; ++c)
	{
		n &= (n - 1);
	}
	return c;
}

/*
*将32位数字，截为4个8位数
*通过查表，得到每个8位数中1的个数，然后求和
*/
int BitCountLUT8(unsigned int n)
{
	unsigned char BitsSetTable256[256] = { 0 };

	for (int i = 0; i <256; i++)
	{
		BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
	}

	unsigned int c = 0;

	unsigned char* p = (unsigned char*)&n;

	c = BitsSetTable256[p[0]] +
		BitsSetTable256[p[1]] +
		BitsSetTable256[p[2]] +
		BitsSetTable256[p[3]];

	return c;
}

/*
*将32位数字，截为4个8位数
*通过查表，得到每个8位数中1的个数，然后求和
*LUT表已经计算好
*/
int BitCountLUT8Static(unsigned int n)
{
	unsigned int table[256] =
	{
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
	};

	return table[n & 0xff] +
		table[(n >> 8) & 0xff] +
		table[(n >> 16) & 0xff] +
		table[(n >> 24) & 0xff];
}

/*
*将32位数字，截为8个4位数
*通过查表，得到每个4位数中1的个数，然后求和
*LUT表已经计算好
*/
int BitCountLUT4Static(unsigned int n)
{
	unsigned int table[16] =
	{
		0, 1, 1, 2,
		1, 2, 2, 3,
		1, 2, 2, 3,
		2, 3, 3, 4
	};

	unsigned int count = 0;
	while (n)
	{
		count += table[n & 0xf];
		n >>= 4;
	}
	return count;
}

/*
*将32位数字，相邻的2位求和，然后相邻的4位求和
*然后相邻的8位、16位、32位求和
*/
int BitCountParallel(unsigned int n)
{
	n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
	n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
	n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
	n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
	n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);

	return n;
}

/*
*第一行，计算每三位的1的个数（其实11*3是33位，但最高一位可以假设为0，所以没问题）
*第二行，实际上是先计算了相邻6位中1的个数（不会产生进位，结果最多占到3位），并将前三位置为0
*然后通过取模，相当于将每6位数字做了加法
*/
int BitCountMagic(unsigned int n)
{
	unsigned int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
	return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

unsigned int n = 127;
unsigned int bitCount = _mm_popcnt_u32(n);


/*
*将8位数字，转换为MY_UNSIGHED_CHAR结构体，然后求和
*/
struct MY_UNSIGHED_CHAR
{
	unsigned a : 1;
	unsigned b : 1;
	unsigned c : 1;
	unsigned d : 1;
	unsigned e : 1;
	unsigned f : 1;
	unsigned g : 1;
	unsigned h : 1;
};

long BitCountStuct(unsigned char b)
{
	struct MY_UNSIGHED_CHAR *by = (struct MY_UNSIGHED_CHAR*)&b;
	return (by->a + by->b + by->c + by->d + by->e + by->f + by->g + by->h);
}

int _tmain(int argc, _TCHAR* argv[])
{
	printf("There are %d 1 in 133\n", BitCount(133));
	printf("There are %d 1 in 133\n", BitCountWithMinus(133));
	printf("There are %d 1 in 133\n", BitCountLUT8(133));
	printf("There are %d 1 in 133\n", BitCountLUT8Static(133));
	printf("There are %d 1 in 133\n", BitCountLUT4Static(133));
	printf("There are %d 1 in 133\n", BitCountParallel(133));
	printf("There are %d 1 in 133\n", BitCountMagic(133));
	printf("There are %d 1 in 133\n", BitCountStuct(133));
	return 0;
}

用位运算实现加减乘除

Posted on by — No Comments ↓ 
        //加法
	public static int add(int a, int b)  
	{  
	    int ans;  
	    while(b!=0)  
	    {
	        ans = a^b;
	        b = ((a&b)<<1);
	        a = ans;  
	    }  
	    return a;  
	}  
	
	//减法
	public static int sub(int a, int b)
	{  
	    return add(a, -b);  
	}
	
	//正数乘法
	private static int posMultiply(int a,int b)  
	{  
	    int ans = 0;  
	    while(b>0)  
	    {  
	        if((b&0x1)==1)ans = add(ans, a);  
	        a = (a<<1);  
	        b = (b>>1);  
	    }  
	    return ans;  
	}  
	  
	//乘法
	public static int multiply(int a,int b)  
	{  
	    if(a==0||b==0)return 0;  
	    if(a>0 && b>0)  
	        return posMultiply(a, b);  
	    if(a<0)  
	    {  
	        if(b<0)  
	        {  
	            return posMultiply(-a, -b);  
	        } 
	        else
	        {
	        	return -posMultiply(-a, b ); 
	        }
	    }
	    else
	    {
	    	return -posMultiply(a, -b);
	    }
	}  
	  
	//正数除法
	private static int posDiv(int x,int y)  
	{  
	    int ans=0;  
	    for(int i=31;i>=0;i--)  
	    {
	        if((x>>i)>=y)  
	        {  
	            ans+=(1<<i);  
	            x-=(y<<i);  
	        }  
	    }  
	    return ans;  
	}  
	  
	//除法
	public static int div( int a, int b )  
	{
		assert(b!=0);
	    if(a==0)return 0;

	    if(a>0)  
	    {  
	        if(b>0)
	        {
	            return posDiv(a,b); 
	        }
	        else
	        {
	        	return -posDiv( a,-b);  
	        }
	    }  
	    else
	    {
	    	if(b>0)
	    	{
		        return -posDiv(a, b);  
	    	}
	    	else
	    	{
	    		return -posDiv(-a, -b);  
	    	}
	    }
	    
	}   
	
	//求负数
	public static int negtive(int a)
	{  
	    return add(~a, 1);  
	}
	  
	//比较正数大小
	private static boolean isbigerPos( int a, int b )   
	{
	    int c = 1;  
	    b = (a^b);  
	    if(b==0)return false;
	    
	    while(b>0)  
	    {  
	    	b>>=1;
	        c <<= 1;  
	    }  
	    return (c&a)==0;  
	}   
	  
	//比较大小   
	public static boolean isbiger( int a, int b )   
	{
	    if(a<0)  
	    {  
	        if(b<0)  
	        {  
	            return isbigerPos( negtive(b), negtive(a) );  
	        }
	        else
	        {
	        	return false;  
	        }
	    }
	    else
	    {
		    if(b<0)
		    {
		        return true;  
		    }
		    else
		    {
		    	return isbigerPos(a, b);  
		    }
	    }

	}

	public static int divideby3(int x)  
	{  
	    int sum = 0;  
	    while(x > 3)  
	    {  
	        sum = add(x>>2 , sum);  
	        x = add(x>>2 , x&3);  
	    } 
	    if(x == 3) 
	    {
	        sum = add(sum , 1);
	    }
	    return sum;  
	}  
	
	public static void main(String[] args)
	{
		System.out.println(add(13,19));
		System.out.println(sub(13,19));
		System.out.println(multiply(13,19));
		System.out.println(div(10,5));
		System.out.println(negtive(13));
		System.out.println(isbiger(10,5));
		System.out.println(isbiger(10,11));
		
		System.out.println(divideby3(15));
		System.out.println(divideby3(14));
		System.out.println(divideby3(13));
		System.out.println(divideby3(12));
		System.out.println(divideby3(11));
	}

几种常见求解平方根的方法

Posted on by — No Comments ↓ 
        //精度
	private final static double accuracy= 1e-6;

	/**
	 * 暴力求解
	 */
	public static double bruteSqrt(double x)
	{
		assert(x>=0);
		double ans=0.0;
		while (Math.abs(x - ans * ans) > accuracy)ans += accuracy;
		return ans;
	}

	/**
	 * 牛顿法求解
	 */
	public static double newtonSqrt(double x)
	{
		assert(x>=0);
		double avg = x;
		double last_avg = Double.MAX_VALUE;

		while (Math.abs(avg - last_avg) > accuracy)
		{
			last_avg = avg;
			avg = (avg + x / avg) / 2;
		}
		return avg;
	}

	/**
	 * 二分法求解
	 */
	public static double binarySqrt(double x)
	{
		assert(x>=0);

		double low = 0;
		double high = x;
		double mid = Double.MAX_VALUE;
		double last_mid = Double.MIN_VALUE;

		while (Math.abs(mid - last_mid) > accuracy)
		{
			last_mid = mid;
			mid = (low + high)/2;
			if (mid*mid>x)high = mid;
			if (mid*mid<x)low = mid;
		}
		return mid;

	}

	private final static int[] LUT =
	{ 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84,
			86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115,
			116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132, 133, 134, 135, 136,
			137, 138, 139, 140, 141, 142, 143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155,
			155, 156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168, 169, 170, 170, 171,
			172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186,
			187, 187, 188, 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200,
			201, 201, 202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213,
			214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223, 224, 224, 225, 225,
			226, 226, 227, 227, 228, 229, 229, 230, 230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237,
			237, 238, 238, 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247, 247, 248,
			248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255 };

	/**
	 * 查表法求解
	 */
	public static int intLutSqrt(int x)
	{
		int xn;

		if (x >= 0x10000)
		{
			if (x >= 0x1000000)
			{
				if (x >= 0x10000000)
				{
					if (x >= 0x40000000)
					{
						xn = LUT[x >> 24] << 8;
					}
					else
					{
						xn = LUT[x >> 22] << 7;
					}
				}
				else
				{
					if (x >= 0x4000000)
					{
						xn = LUT[x >> 20] << 6;
					}
					else
					{
						xn = LUT[x >> 18] << 5;
					}
				}

				xn = (xn + 1 + (x / xn)) >> 1;
				xn = (xn + 1 + (x / xn)) >> 1;
				return ((xn * xn) > x) ? --xn : xn;
			}
			else
			{
				if (x >= 0x100000)
				{
					if (x >= 0x400000)
					{
						xn = LUT[x >> 16] << 4;
					}
					else
					{
						xn = LUT[x >> 14] << 3;
					}
				}
				else
				{
					if (x >= 0x40000)
					{
						xn = LUT[x >> 12] << 2;
					}
					else
					{
						xn = LUT[x >> 10] << 1;
					}
				}

				xn = (xn + 1 + (x / xn)) >> 1;

				return ((xn * xn) > x) ? --xn : xn;
			}
		}
		else
		{
			if (x >= 0x100)
			{
				if (x >= 0x1000)
				{
					if (x >= 0x4000)
					{
						xn = (LUT[x >> 8]) + 1;
					}
					else
					{
						xn = (LUT[x >> 6] >> 1) + 1;
					}
				}
				else
				{
					if (x >= 0x400)
					{
						xn = (LUT[x >> 4] >> 2) + 1;
					}
					else
					{
						xn = (LUT[x >> 2] >> 3) + 1;
					}
				}

				return ((xn * xn) > x) ? --xn : xn;
			}
			else
			{
				if (x >= 0)
				{
					return LUT[x] >> 4;
				}
			}
		}

		return -1;
	}

	/**
	 * Quake III中快速求解平方根倒数的方法
	 */
	public static float fastInvSqrt(float x)  
	{  
	     float xhalf = 0.5f*x;  
	     int f2i = Float.floatToRawIntBits(x);
	     f2i = 0x5f375a86-(f2i>>1);
	     x = Float.intBitsToFloat(f2i);
	     x = x*(1.5f-xhalf*x*x);
	     x = x*(1.5f-xhalf*x*x);
	     return x;  
	}
	
	/**
	 * Quake III中快速求解平方根方法
	 */
	public static float fastSqrt(float x) {  
	    float y=x;
	    float xhalf = 0.5f*x;
	    int f2i = Float.floatToRawIntBits(x);  
	    f2i = 0x5f3759df-(f2i>>1);  
	    x = Float.intBitsToFloat(f2i);  
	    x  = x * (1.5f-(xhalf*x*x));  
	    x  = x * (1.5f-(xhalf*x*x));  
	    return y*x;  
	}

	public static void main(String[] args)
	{
		System.out.println(bruteSqrt(3));
		System.out.println(newtonSqrt(3));
		System.out.println(binarySqrt(3));
		System.out.println(intLutSqrt(64));
		System.out.println(1/fastInvSqrt(3));
		System.out.println(fastSqrt(3));
	}

指定WebBrowser控件的IE版本

Posted on by — No Comments ↓

1、假设你的程序用到了WebBrowser，程序名为XXX.exe，希望发布时指定WebBrowser的IE版本

2、在注册表指定的位置，新建名为XXX.exe的DWORD值，并按Browser Emulation的值，设置正确的IE版本即可。

HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\Main\FeatureControl\FEATURE_BROWSER_EMULATION
或
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Internet Explorer\MAIN\FeatureControl\FEATURE_BROWSER_EMULATION

3、如果是在VS调试时，需要指定其版本，则要设置VS的程序名，而不是被调试程序的程序名

4、Browser Emulation

Value Description
11001 (0x2AF9) Internet Explorer 11. Webpages are displayed in IE11 edge mode, regardless of the declared !DOCTYPE directive. Failing to declare a !DOCTYPE directive causes the page to load in Quirks.
11000 (0x2AF8) IE11. Webpages containing standards-based !DOCTYPE directives are displayed in IE11 edge mode. Default value for IE11.
10001 (0x2711) Internet Explorer 10. Webpages are displayed in IE10 Standards mode, regardless of the !DOCTYPE directive.
10000 (0x02710) Internet Explorer 10. Webpages containing standards-based !DOCTYPE directives are displayed in IE10 Standards mode. Default value for Internet Explorer 10.
9999 (0x270F) Windows Internet Explorer 9. Webpages are displayed in IE9 Standards mode, regardless of the declared !DOCTYPE directive. Failing to declare a !DOCTYPE directive causes the page to load in Quirks.
9000 (0x2328) Internet Explorer 9. Webpages containing standards-based !DOCTYPE directives are displayed in IE9 mode. Default value for Internet Explorer 9.
Important In Internet Explorer 10, Webpages containing standards-based !DOCTYPE directives are displayed in IE10 Standards mode.
8888 (0x22B8) Webpages are displayed in IE8 Standards mode, regardless of the declared !DOCTYPE directive. Failing to declare a !DOCTYPE directive causes the page to load in Quirks.
8000 (0x1F40) Webpages containing standards-based !DOCTYPE directives are displayed in IE8 mode. Default value for Internet Explorer 8.
Important In Internet Explorer 10, Webpages containing standards-based !DOCTYPE directives are displayed in IE10 Standards mode.
7000 (0x1B58) Webpages containing standards-based !DOCTYPE directives are displayed in IE7 Standards mode. Default value for applications hosting the WebBrowser Control.

参考：
MSDN

修复GPT分区表

Posted on by — No Comments ↓

说起gpt来，就一把鼻涕一把泪的，因为工作原因，需要在windows进行开发，
没办法在mac book pro里安了个win7，后来为了方便，在mac下安了ntfs的读写驱动，
悲剧发生了，某天开机进入mac，很久没反应，强制重启后，windows分区已经挂掉了。

于是重装，用win7的光盘进行的分区，后来用第三方分区工具调整了下，ntfs不负众望，又挂了
好吧～～，又重装了一次

一波三折，终于稳定了。
但mac下，却认不到ntfs分区，一直认为是mac下ntfs驱动的问题，尝试过一些解决方案，都不行。
今天发现，mac下分区大小和win7下分区大小不一样，mac下的分区大小，仍是我在win7下调整前的状态
懂了，明显是gpt分区表错了啊。

网上找了一堆工具，还差点用gpt把hybrid MBR给覆盖了，晕。
最后，用gdisk终于搞定了，修改gpt的神器啊。
http://sourceforge.net/projects/gptfdisk/files/gptfdisk/0.8.5/
http://www.rodsbooks.com/gdisk/walkthrough.html

sudo进入gdisk后，选用/dev/disk0，然后用v命令进行校验，
gdisk发警告，mbr里有两个分区在gpt中不存在，
进入expert模式，用p和o命令打印gpt和mbr分区信息，发现真的对不上，
把分区表记录好，gpt备份好。

然后将gpt中错误的两个分区删掉，再根据mbr里的数据，重新建立两个分区，
再用v命令校验，没有问题，
保持修改，重启，终于搞定了。

注意：
我的情况是，在mac分区表错误，而win7下分区表正确，这说明是gpt错了，而hybrid MBR是对的。
而如果是相反的情况，就要根据gpt重新编辑mbr，这样的工具很多，貌似在mac，win，linux共存的时候发生的几率会比较高。
对硬盘分区表的修改，是很危险的工作，一定要备份数据，备份分区表，将风险尽量降低。

Oracle、SQL Server、MySQL的语句变化总结

Posted on by — No Comments ↓
调整内容 Oracle SQL Server MySQL
数据类型：字符 VARCHAR2 NVARCHAR
数据类型：数字 NUMBER tinyint,smallint,int,bigint
数据类型：时间 TIMESTAMP DATATIME
列自增 sqeuence.nextval identity(1,1) identity(1,1)
约束主键 CONSTRAINT 表名 PRIMARY KEY (列名) USING INDE PRIMARY KEY
约束唯一 CONSTRAINT 表名 UNIQUE (列名) USING INDEX UNIQUE INDEX
注释 commnet sp_addextendedproperty
函数时间 sysdate getdate()
查询分页 rownum top limit
查询跨库 库名.表名 库名.dbo.表名 limit
执行存储过程 call exec

Oracle Job 101

Posted on by — No Comments ↓

1、新建一个存储过程

create or replace procedure p_insert_into_t1
as
begin
     insert into t1
     (select * from t where STATUS=1);
end;

2、新建一个作业

variable job_abc number;
begin
      sys.dbms_job.submit(:job_abc,
                         'p_insert_into_t1;',
                          sysdate,
                         'sysdate+1/1440');
       commit;
end;

其中，
参数1表示作业名字，参数2表示执行的存储过程，
参数3表示开始执行的时间，参数4表示执行的时间间隔

commit表示立即开始执行

执行成功后，返回job的ID

3、查询作业

select job,
       log_user,
       to_char(last_date,'yyyy-mm-dd hh24:mi:ss') last_date,
       to_char(next_date,'yyyy-mm-dd hh24:mi:ss') next_date,
       interval,
       what
from user_jobs

4、执行作业

execute dbms_job.run(job_id);

5、删除作业

execute dbms_job.remove(job_id);

6、暂停和继续作业

execute dbms_job.broken(job_id,true);
execute dbms_job.broken(job_id,false);

Java HTTP Premature EOF

Posted on by — No Comments ↓

这几天在调试HTTP通讯的时候，偶尔会发生下面的异常：
java.io.IOException: Premature EOF

主要原因是：
client在读取server返回的文件时，本来已经读完，但client又去读了一次
此时，就会抛出上面的异常

另外，公司搬家后，测试Java取回文件的效率，会出现两种诡异的延时：
1、打开输入流的时候，奇慢无比，要3～4s
2、在从输入流中读取时，不时会有200ms的奇怪延时
在不同的客户端机器上，从同一个服务端取回，会有不同的表现
貌似和客户端操作系统种类和JDK版本都有关，总之很诡异了。

唉～～，时间紧迫，只好找了其他方法解决

有人说是HTTP头设置问题，有人说是IPV6问题，试过后，问题依旧啊。