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)相同
