每天两题04

2019-09-23 09:09:02来源：博客园阅读 ()

每天两题04

　　本来昨晚就准备看两个题的，结果下班回来躺了一下就睡着了，今天继续，嘿嘿(^.^)

题目一：二进制中1的个数

　　题目描述：输入一个整数，输出该数二进制表示中 1 的个数。

　　思路：第一眼看到这个题目的我想法是首先将这个数转成二进制字符串，然后通过遍历这个字符串中的每一个元素是不是等于1，然后用个int类型的数值去计算，代码如下：

public static int oneNum(int n) {
        String string = Integer.toBinaryString(n);
        int count = 0;
        for (int i = 0; i < string.length(); i++) {
            if (string.charAt(i) == '1') {
                count++;
            }
        }
        System.out.println("数字对应的二进制为："+string);
        return count;
    }

    public static void main(String[] args) {
        System.out.println("二进制中1的个位为："+oneNum(24));
    }

//运行结果：
//数字对应的二进制为：11000
//二进制中1的个位为：2

　　后来找了看了一下别人的解法，很奇特的思路，直接运用位运算来就可以了，比如输入的是6，对应的二进制为110，我们将6和（6-1）做“按位与”运算，就可以将110中后面的1去掉，此时得到的是100，然后将这个数和当前数减一，也就是000做位运算，就可以又去掉一个1了，此时得到的结果就是000

　　综上所述，假如有一个数n，我们只需要无限的计算n = n&（n-1），每计算一次计数的变量就加一，直到n等于0，此时就得到了1的个数，代码如下，这个的效率高很多

public static int oneNum2(int n){
        int count = 0;
        while (n!=0) {
            n &= (n-1);
            count ++;
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println("二进制中1的个位为："+oneNum2(24));//2
    }

题目二：数值的整数次方

　　题目描述：给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent，求 base 的 exponent 次方。

　　思路：最直接的想法，根据整数 exponent循环，每循环一次就乘以base，代码如下（不考虑exponent为负数的情况，其实考虑的话也很容易，那结果就是1/result）：

public static double pow(double base, int exponent) {
        double result = base;
        for (int i = 1; i < exponent; i++) {
            result *= base;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(pow(1.2, 2));//1.44
    }

　　很明显，这样的效率不是很好，这里可以用递归做，举个例子，如果是2x2x2x2x2x2,这里有6个2相乘，为什么我们要从前一个一个乘呢？先算前面两个2相乘的结果为4，然后再6/2==3次方就好了，由于6是偶数，所以继续下一次递归；然后我们计算前面两个4相乘结果为16，然后再3/2==1次方，由于3是奇数，要再乘以4。。。代码如下：

public static double pow2(double base, int exponent) {
        //这个是递归的出口
        if (exponent==1) {
            return base;
        }
        
        double result = pow2(base*base,exponent/2);
        //在递归中每一次都要对传入的exponent进行判断是不是奇数，是的话就多乘以一个base，比如有传入的是2.0和10，第一次递归就是4.0和5，注意：
        //这里会进行第二次递归传入的是16.0和5/2=2,所以在第二次递归调用完毕之后回来会多乘以一个4.0
        if (exponent%2 == 1) {
            result *= base;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(pow2(3.0, 3));//27.0
    }