欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

每天两题04

程序员文章站 2022-04-15 08:08:46
本来昨晚就准备看两个题的,结果下班回来躺了一下就睡着了,今天继续,嘿嘿(^.^) 题目一:二进制中1的个数 题目描述:输入一个整数,输出该数二进制表示中 1 的个数。 思路:第一眼看到这个题目的我想法是首先将这个数转成二进制字符串,然后通过遍历这个字符串中的每一个元素是不是等于1,然后用个int类型 ......

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

题目一:二进制中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
    }