未经允许，不得转载
前言
我做出的调整：
本来想一个月内刷完《剑指offer》所有Java代码并写完解析以提供自己复习，但是发现自己求量不求质的思想着实龌龊。这本书的题目每一道都值得深思，今天看到别人写的代码如此精妙美丽，而自己的却像一坨屎。我痛定思痛，决定改成每日一题的模式，把本书所有的代码及解法吃透。由于前十题，写的代码稀巴烂，在我更新好最后一题后，会重新写前十题。
第十一题
难易度：⭐
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
例如：
输入数字 9 ,9 的二进制表示为1001，所以 1 的个数为 2，结果输出 2
- 不需要算法的思路：
在Java中提供了Integer.toBinaryString(n)的方法，将一个数字转换为二进制的数后再转换为字符串，我们只需要将字符串转换为char数组依次遍历并统计字符'1' 的个数即可，但很显然这样做并不是面试官期待的做法
代码如下：
public class Solution {
public int NumberOf1(int n) {
String str = Integer.toBinaryString(n);
char[] chars = str.toCharArray();
int res = 0;
for(int i = 0;i < chars.length; i++){
if(chars[i] == '1'){
res ++;
}
}
return res;
}
}
- 使用位运算
对数字1依次左移，直到左移至0为止。在左移的过程中同输入的数字n取&,我们只需要判断取&的结果是否等于0，如果为0，说明该位上的数字是0，如果不等于 0 说明该位的数字为 1。
举例：
9 这个数字的二进制为 1001
0001 & 1001 结果不为 0 res++
将 0001 左移一位
0010 & 1001 结果为 0
将 0010 左移一位
0100 & 1001 结果为 0
将 0100 左移一位
1000 & 1001 结果不为 0 res++
... ...
直到将最初的 1 移动至int的长度也就是32位 溢出为 0 为止
代码如下：
public class Solution {
public int NumberOf1(int n) {
int flag = 1;
int res = 0;
while (flag != 0) {
if ((flag & n) != 0) {
res++;
}
flag = flag << 1;
}
return res;
}
}
本解法需要将数字1进行一个类型长度的左移运算，有没有办法做到不移动那么长的距离就可以得到结果呢？
- 最优解
结论：
n & (n - 1) 的结果是将 n的二进制数最右边的那个 1 变为 0
举例：
1101 & 1100 的结果为 1100 实际上就是将 1101最右边的1变成了 0
1010 & 1001 的结果为 1000 实际上就是将1010最右边的 1变成了0
对于这样一个结论，不妨试着自己证明一下，这里就不再给证明了。
有了这样的一个结论，我们就可以这样写代码:
public class Solution {
public int NumberOf1(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
}
这样我们就可以遍历 n 的二进制数中 1 的个数这样一个长度，就可以得到结果。
第十二题
难易度：⭐
给定一个double类型的浮点数base和int类型的整数exponent。
求base的exponent次方，要求不使用函数库中的方法
本题的重点是对于各种case的考察
- 首先，如果base和exponent均为 0 ，我们需要抛出异常
- 当 base 为 0 时，exponent无论正负 结果均为 1
对于 exponent 来讲，有正数or负数两种情况：
- exponent为正，我们需要遍历exponent 让 base自乘即可获得结果
- exponent为负，我们需要对exponent取正后，在将得到的结果取倒数
理清各种case后，代码并不难：
public class Solution {
public double Power(double base, int exponent) {
if (base == 0 && exponent == 0) {
throw new RuntimeException("base 与 exponent 不能同时为 0 ");
}
// base 为 0 ；无论exponent为正or负 结果均为0
if (base == 0) {
return 0;
}
// exponent 为负数时，结果为 对exponent取反的倒数
if (exponent < 0) {
return 1 / PowerWithUnsignedExponent(base, (-exponent));
}else {
return PowerWithUnsignedExponent(base,exponent);
}
}
private double PowerWithUnsignedExponent(double base, int exponent) {
double res = 1d;
for (int i = 0; i < exponent; i++) {
res *= base;
}
return res;
}
}
但是本代码并不是最优解，对于上面的 PowerWithUnsignedExponent 方法 有更优秀的写法
试想如果 exponent 为 32，我们上面的 PowerWithUnsignedExponent中要循环31次乘法运算。如果换一个思路思考：
32 = 16 * 16
16 = 8 * 8
8 = 4 * 4
... ...
不难想到，对于PowerWithUnsignedExponent 可以使用递归的思路
我们有如下公式：
最优解代码如下：
public class Solution {
public double Power(double base, int exponent) {
if (base == 0 && exponent == 0) {
throw new RuntimeException("base 与 exponent 不能同时为 0 ");
}
// base 为 0 ；无论exponent为正or负 结果均为0
if (base == 0) {
return 0;
}
// exponent 为负数时，结果为 对exponent取反的倒数
if (exponent < 0) {
return 1 / PowerWithUnsignedExponent(base, (-exponent));
} else {
return PowerWithUnsignedExponent(base, exponent);
}
}
private double PowerWithUnsignedExponent(double base, int exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
double res = PowerWithUnsignedExponent(base, exponent >> 1);
res *= res;
if ((exponent & 1) != 0) { // 等同于 exponent/ 2 ! = 0
res *= base;
}
return res;
}
}
