刷题《剑指Offer》day06

题目来源：力扣《剑指Offer》第二版
完成时间：2022/07/27

• • 15. 二进制中1的个数
  • • 我的题解
  • 16. 数值的整数次方
  • • 我的题解
    • 其他题解

主要思路就是不断地右移，和1做与运算。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n) {
            if(n & 1){
                count++;
            }
            n = n >> 1;
        }
        return count;
    }
};

这道题有个巨坑的地方，就是给定的n可能会超范围，要用一个long接收一下，我一开始没找到思路，用的书上原码过的。大致思想和斐波那契数列有点像，比如13次方可以拆解成6+6+1，6又拆解为3+3，以此类推。

class Solution {
public:
    double myPow(double x, int n) {
        long m = n;//巨坑
        if(n >= 0) return count(x,m);
        else return count(1 / x, -m);
    }

    double count(double x, long n) {
        if(n == 0) return 1;
        if(n == 1) return x;

        double result = myPow(x,n >> 1);
        result *= result;
        if(n % 2 == 1){
            result *= x;
        }
        return result;
    }
};

这个就比较取巧，和上一题类似，用二进制的思路，不断右移。比如13就是1101，即1+0+4+8，碰到1就可以进行运算。

double myPow(double x, int n) {
	double res = 1;
	long y = n;
	if (n < 0) {
		y = -y;
		x = 1 / x;
	}
	while (y > 0) {
		if (y % 2 == 1) {//判断最后一位是否为1
			res = res * x;
		}
		x = x * x;
		y = y >> 1;//右移
	}
	return res;
}