一、不用加减乘除做加法

题目链接

题目描述:

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
数据范围：两个数都满足 -10 \le n \le 1000−10≤n≤1000
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(1)O(1)

示例：
示例1

输入：1,2
返回值：3

示例2

输入：0,0
返回值：0

分析思路：
题目不让用四则运算符号，所以我们需要用位运算来达到加法的目的。
位运算的本质是对二进制位操作，通过找规律可以发现：
位运算中两数进行^（异或运算）可以提供两数加和后二进制非进位信息，位运算中的两数进行&(与运算)的结果可以提供两数加和后的二进制进位信息

如图：

通过观察可以发现：如果在没有进位的情况下两个二进制序列^后就为结果sum，在加上进位信息就是有进位的情况。所以当进位信息不为0时，我们就可以先左移进位信息^后得到非进制信息，再&看进位信息是否为0，如此循环。

int Add(int num1, int num2 ) {
    // write code here
    int add = num2;
    int sum = num1;
    while(add != 0)
    {
        int tmp = add ^ sum;
        //进位信息
        add = (sum & add) << 1;
        sum = tmp;
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

二、二进制中1的个数

题目链接

题目描述：

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
数据范围：- 2^31 <= n <= -2^31-1−2^31<=n<=2^31−1
即范围为:-2147483648<= n <= 2147483647−2147483648<=n<=2147483647

示例一：

输入：10
返回值：2
说明：
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。

示例二：

输入：-1
返回值：32
说明：
负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1

思路分析：
因为因负数用补码表示，故不能用连除法。
我们可以让目标数字右移&数字1，如果结果为1，就说明最后一位是1，就可以看到有多少位1

int NumberOf1(int n ) {
    int count = 0;
    int i = 0;
    for(i = 0; i < 32; i++)
    {
        if((n >> i) & 1 == 1)
            count++;
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10

---

三、有限制求1+2+3+…+n

题目链接

题目描述：

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
数据范围： 0 < n \le 2000 进阶： 空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n)

示例一：

输入：5
返回值：15

示例二：

输入：1
返回值：1

思路分析：
不让用乘除法和条件判断语句就说明不能使用公式法和循环。
这很容易就能想到递归：
一般递归是这么实现：

int Sum_Solution(int n)
{
	if (n == 1)
	{
		return 1;
	}
	return n + Sum_Solution(n - 1);
}
1
2
3
4
5
6
7
8

但是这里还是会用到条件判断语句，那我们就可以巧用 && 的短路性质，如果&&的左边为假，右边就不会进行：

int Sum_Solution(int n ) {
    // write code here
    n && (n += Sum_Solution(n - 1));
    return n;
}
1
2
3
4
5

---

---