每日算法题：Day 6
作者：TeddyZhang，公众号：算法工程师之路
Day 6, C/C++知识点走起~
1
编程题
【剑指Offer】二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路： 我们大家都知道整数在计算机中是以二进制的形式来存储的，因此对于正数或者负数都是0或1的数字组成的。且由于int型为32位，因此我们可以逐一的对每一位进行判断，只需要n & (1<<i)就可以判断第i位是否为1了！
class Solution {
public:
int NumberOf1(int n) {
int count = ;
for(int i = ;i >=; --i){
if(n & ( << i)){
++count;
}
}
return count;
}
};
当然也可以使用STL中的bitset(位图)来直接统计，花里胡哨的写法，只需要一句话！
6};【剑指Offer】数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路： 首先我们来说一个O(n)的方法，这个题目主要考虑到幂指数为负的情况需要对结果求倒数。
class Solution {
public:
double Power(double base, int exponent) {
double res = ;
if(exponent == )
return ;
if(base == )
return ;
for(int i = ;i < abs(exponent); ++i){
res *= base;
}
if(exponent < ){
res = / res;
}
return res;
}
};
显然，上面的算法一定不会合面试官的胃口的，因此我们可以使用一个快幂算法来进行求解！其实际编程不复杂，但是效率很高的！
假设3^64需要64个乘法运算，但如果这样计算的话：
3^1 = 3 (也就是base) 3^2 = (3^1) * (3^1) 3^4 = (3^2) * (3^2) … 3^64 = (3^32) * (3*32)
这个样子的话，就只算6次乘法，效率提升了很多了!因此我们就可以进行如下编程。
class Solution {
public:
double Power(double base, int exponent) {
if(exponent == ){
return ;
}
if(base == ){
return ;
}
double tmp = base;
double res = ;
int e = abs(exponent);
while(e > ){
if(e & ){ //e & 1相当于e % 2
res *= tmp;
}
e >>= ; // e >> 1相当于e / 2
tmp *= tmp;
}
return (exponent > ) ? res : / res;
}
};2
概念题
【C/C++】引用传递和值传递的区别
值传递： 编译系统会在调用该函数的地方，把实参复制一份传给函数的形参。因此如果对形参进行修改，其实质是修改实参的副本，而实参本身不发生变化！但这样由于副本拷贝需要系统资源，效率会很低。
引用传递： 编译系统会在调用该函数的地方，直接将实参的内存地址（指针）传给形参。因此形参和实参共同拥有同一块内存，因此在函数中对参数进行修改，实参也会跟着修改。并且引用传递时规定引用不为空，因此需要在使用时对指针进行判断。
C++中参数一般使用引用传递（比如类或者结构体）！
【C/C++】sizeof和strlen的区别有哪些
- sizeof是运算符，并不是函数，结果在编译时得到而非运行中获得；strlen是字符处理的库函数
- sizeof参数可以是任何数据的类型或者数据（sizeof参数不退化）；strlen的参数只能是字符指针且结尾是'\0'的字符串。
- 因为sizeof值在编译时确定，所以不能用来得到动态分配（运行时分配）存储空间的大小。
【C/C++】指针和引用有什么区别呢？
- 指针是一个变量，实质为某一个变量的地址，指向某一个内存区域，可以进行改变！而引用相当于为某一个变量起别名罢了，指向的均为同一块区域，不可以修改！
int a=; int *p=&a;
int a=; int &b=a; //b相当于a的别名
- 可以有const指针，但是没有const引用
- 引用不能为空，必须在定义的时候进行初始化,而指针可以为空，nullptr, 也可以先声明再初始化
- 指针可以有多级，但是引用只能是一级（int **p；合法 而 int &&a是不合法的）
- 可以有const指针，但是没有const引用；
- "sizeof引用"得到的是所指向的变量的大小，而"sizeof指针"得到的是指针本身的大小。