每天两题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 }