美文网首页
简单小算法

简单小算法

作者: 左上偏右 | 来源:发表于2016-12-26 13:49 被阅读10次
    • 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;
        }
    

    相关文章

      网友评论

          本文标题:简单小算法

          本文链接:https://www.haomeiwen.com/subject/zjsjvttx.html