《LeetCode零基础指南》第一讲题解！
《LeetCode零基础指南》链接： https://blog.csdn.net/whereisherofrom/category_11492771.html
目录
位运算及快速幂知识点总结
位运算常识
按位与& ： 二进制上同1为1，否则为0
按位异或^ ： 二进制上互异为1，否则为0。又叫不进位加法。
快速幂
原理：求幂时每一次都将幂分为两半，用当前的底数做平方运算。
比如5的二进制为101，求3^5就可以转化为3^(2^0) * a ^(2^2) 。
那么如何求解：我们从101的最右边开始算幂，第一位对应3的1次方，第二位对应3的2次方，第三位对应3的四次方，而我们只有第一位和第三位是1，第二位是0，对应求3^1 * 3^4。我们使用&按位与1取幂的最低位，再用>>左移1来去掉幂的二进制的最低位，每次求更高一位的幂时，底数变成自身的平方即可。
example：
3^5:
? ? ? 3 ???????? 求最低一位，底数为3
1 0 1? ? ? ? ? 5 & 1 得到 1， 即二进制最低位，3 * 1 = 3
当前得到：3
? ? ? 9? ? ? ? 求第二位，底数为3*3
? ?1? 0? ? ? ? 1 0 & 1 得到 0，当前二进制最低位为0，当前位为空
当前得到： 3
? ? ? 81
? ? ? ?1? ? ? ? 1 & 1 得到 1，也就是当前二进制最低位， 81 * 1 = 1
当前的到：81 * 3 = 253? ? 也就是最终答案
题目
两整数之和
?371. 两整数之和 - 力扣（LeetCode） (leetcode-cn.com)（前几题一样）
思路：前面提到了按位与和按位异或，按位异或用来实现无进位加法，而按位与可以实现进位的统计。
如何实现：两数的相加等于两数异或的值加上两数与的值左移1位，即a + b = (a ^ b) + (a & b) << 1
例子：4 + 5
? ? ? ? ? ? ? ? ? 1 0 0
? ? ? ? ? ? ? ? ? 1 0 1? ? ? ??
按位异或? ? 0 0 1
按位与? ? ?1 0 0 0? ? ? ? (1 0 0 左移一位得）
相加? ? ? ? ?1 0 0 1
通过上面的示例我们发现，按位异或可以实现无进位加法，按位与可以找出当前两数和的进位，而我们继续将得到的两个值使用异或和与，就可以得到新的异或值和与值，那么只需要异或到两数与的值为0时，就代表已经实现了相加，也就是没有进位了，即当前值就是两数的和
class Solution {
public:
int getSum(int a, int b) {
unsigned int carry;
while ( b != 0 ){
carry = (unsigned)(a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
};递归乘法
面试题 08.05. 递归乘法 - 力扣（LeetCode） (leetcode-cn.com)
思路：这道题可以使用快速幂的思想来做，即将两数的乘积换成一个数与另一个数的二进制的各个位相乘，不同的是，求幂使用底数的乘法，而求乘积则使用底数的加法。
example：
3 * 5
? ? ? 3? ? ? ??
1 0 1? ? ? ? 最低为1
当前得到：1 * 3 = 3
? ?6
1 0? ? ? ? ? 最低为0
当前得到：3 + 6 * 0 = 3
12
1
当前得到 3 + 12 = 15 即答案
class Solution {
public:
int multiply(int A, int B) {
return (B & 1 ? A : 0) + (B > 1 ? multiply(A + A, B >> 1) : 0);
}
};两数相除
29. 两数相除 - 力扣（LeetCode） (leetcode-cn.com)
不好意思，这道题暂时还没做，过几天补上。
x的n次幂
50. Pow(x, n) - 力扣（LeetCode） (leetcode-cn.com)
这道题就是使用之前提及的快速幂思想?
class Solution {
public:
double myPow(double x, int n) {
double ans = 1;
if( n < 0 ){
x = 1 / x;
}
while (n){
if(n & 1)
ans *= x;
x *= x;
n /= 2;
}
return ans;
}
};x的平方根
69. x 的平方根 - 力扣（LeetCode） (leetcode-cn.com)
思路:暴力求解，使用二分法和long long来防止超时和溢出。
class Solution {
public:
int mySqrt(int x) {
int left = 0, right = x, ans = -1;
while(left <= right){
int mid = left + (right - left) / 2;
if((long long) mid * mid <= x){ //long long 防止溢出
ans = mid;
left = mid + 1;
}
else right = mid - 1;
}
return ans;
}
};最大数值
面试题 16.07. 最大数值 - 力扣（LeetCode） (leetcode-cn.com)
思路：a，b中最大值为（a + b + |a - b|）/ 2，其中我们使用位运算符来解决绝对值问题
两个int相减使用int来保存可能会溢出，所以使用long保存两数相减（8字节64位），且右移时高位会补符号位，所以负数右移63位，二进制位是64个1，即得到了-1。使用diff保存两数的差，分别对正负两种情况分析，我们得到：(diff?^?(diff?>>?63))?-?(diff?>>?63)这个式子，正数时diff ^ 0 = diff，再减去0仍然是diff，负数时diff ^ -1就是将diff每一位反转，再加1得到原码，也就是他的正数。
class Solution {
public:
int maximum(int a, int b) {
long diff = (long)a - (long) b;
return ((long)a + (long)b + (diff ^ (diff >> 63)) - (diff >> 63)) >> 1;
}
};反转两次的数字
这道题比较简单，只需要判断他的尾数是不是0即可，注意讨论值为0的情况。
class Solution {
public:
bool isSameAfterReversals(int num) {
if( num == 0) return true;
if( num % 10 == 0) return false;
else return true;
}
};
?