二進制中1的個數以及時間比較

public class Algorithm {

	public static void main(String[] args) {
		long t1 = System.currentTimeMillis();
		for (int i = -10000000; i < 10000000; i++) {
			countOne(i);
		}
		long t2 = System.currentTimeMillis();
		long p1 = t2 - t1;

		long t3 = System.currentTimeMillis();
		for (int i = -10000000; i < 10000000; i++) {
			countOne2(i);
		}
		long t4 = System.currentTimeMillis();
		long p2 = t4 - t3;
		System.out.println(p1 + "----" + p2);
	}

	/**
	 * 位運算求1的個數
	 * 
	 * @param x
	 * @return
	 */
	public static int countOne(int x) {
		x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
		x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
		x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
		x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);// (1)
		x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);// (2)
		// x = (x * 0x01010101) >> 24;(3)
		return x;
	}

	/**
	 * 1的個數
	 * 
	 * @param x
	 * @return
	 */
	public static int countOne2(int x) {
		int cnt = 0;
		while (x != 0) {
			x &= (x - 1);
			cnt++;
		}
		return cnt;
	}
}

位運算的時間有波動，非位運算的耗時基本上在250-270左右。位運算的速度確實快。

其中(1)和(2)的效果與(3)相同