-
1、求素数
/**
* 对正整数n，如果用2到根号n之间的所有整数去除，均无法整除，则n为质数。
* 质数大于等于2 不能被它本身和1以外的数整除
* @param val
* @return
*/
private static boolean testPrime(int val){
if (val<=3 && val>0) {
return true;
}
for (int i = 2; i <= Math.sqrt(val); i++) {
if (val%i==0) {
return false;
}
}
return true;
}
-
2、查找整数对应二进制中1的个数
1、为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n - 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。
private static int BitCount2(int n) {
int c = 0;
for (c = 0; c<n; ++c) {
n &= (n - 1); // 清除最低位的1
}
return c;
}
2、普通移位算法
int BitCount(int n) {
int c = 0; // 计数器
while (n > 0) {
if ((n & 1) == 1) // 当前位是1
++c; // 计数器加1
n >>= 1; // 移位
}
return c;
}
