题目描述：求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
常见思路：等差数列（不能使用乘除，pass），迭代（不能使用循环，pass），递归（用位运算短路原则代替if条件判断）
短路原则： 对于A&&B与运算，当条件A为false则不再执行条件B判断，故仅当条件A成立才执行条件B判断。 A||B或运算同理，A如果为true则不执行条件B判断，仅当条件A不成立才执行条件B判断。
注意：由于条件语句不能写成赋值语句，可以使用 辅助变量ret 或者 (n += sumNums(n-1)) > 0 把赋值语句变成条件语句
class Solution { public: //int ret; int sumNums(int n) { //①if使递归终止 //if(n == 1) return 1; //不能使用赋值语句，故改为判断是否大于0语句 //②&&法 n != 1 && (n += sumNums(n-1)) > 0; //③||法 //n == 1 || (n += sumNums(n-1)) > 0; //ret += n; return n; } };剑指 Offer 15. 二进制中1的个数 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。 示例 1：
输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。 示例 2：
输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。 示例 3：
输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。
class Solution { public: int hammingWeight(uint32_t n) { //n和1 &运算 //最后一位若为0，则结果为0；最后一位若为1，则结果为1 int res = 0; while(n) { res += n & 1; //&号两边要打空格 //if(n & 1) res++; //&号两边要打空格 n >>= 1; //注意写了等号才是把n变成移动后的值 } return res; /*int cnt = 0; //n-1：为n最右边的1变成0，1的右边（全为0）变成1，1的左边保持不变 //n & (n-1) 最右边的1变成0 //n与n-1按位与，与完再与，每与一次都能消耗掉一个1，使n变为0的次数就是1的个数 while(n) { n &= n-1; cnt++; } return cnt;*/ } };剑指 Offer 65. 不用加减乘除做加法 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 示例:
输入: a = 1, b = 1 输出: 2
提示：
a, b 均可能是负数或 0 结果不会溢出 32 位整数
解： //00 无进位和：0 进位：0 //01 无进位和：1 进位：0 //01 无进位和：1 进位：0 //11 无进位和：0 进位：1
//a + b = 无进位和 + 进位和 //无进位和：a^b 异或 //进位和：a & b << 1
递归等式：a + b = a^b + （a & b） << 1 递归终止条件：进位和为0。此时a即为所求。 （数据为补码表示，cpu加减运算均为加运算，故负数运算同样适用，但需注意：C++不支持负数左移，需转换成无符号数类型再左移。）
class Solution { public: int add(int a, int b) { if(b == 0) return a; //当进位和为0（位数有限，左移最终一定会为0），终止加法 return add(a^b,(unsigned int)(a&b) << 1); //C++不支持负数左移 } };剑指 Offer 56 - I. 数组中数字出现的次数 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1] 示例 2：
输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
解： //相同的两个数字异或，值为0 //故若只有一个数字出现了一次，将数组成员全部异或，则结果为那一个数字
//1.将数组所有值异或一遍，得到目标两数a,b异或值c，且这两数异或值必不为0 //2.找到数值c为1的一个位，则a，b两数此位必不等，按照此位为0或为1将数组分为两个数组,则a，b落在了不同的数组中 //3.分别对两个数组进行异或，则得到目标数a,b.
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { if(nums.empty()) return {}; int c = 0; //目标a,b异或值 for(int i = 0;i < nums.size();++i) { c ^= nums[i]; } if(!c) return {}; //获得c第一个为1的位 int bitOne = 1; for(int i = 0;i < 31;++i) while((c & bitOne) == 0) //记得加括号,==运算符优先级高于&运算符 bitOne <<= 1; //按照指定位为0或为1把数组分为两组 int zero = 0,one = 0; for(int i = 0;i < nums.size();++i) { if((nums[i] & bitOne)) one ^= nums[i]; else zero ^= nums[i]; } return {zero,one}; } };注意：while((c & bitOne) == 0) //记得加括号,==运算符优先级高于&运算符
剑指 Offer 56 - II. 数组中数字出现的次数 II 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3] 输出：4 示例 2：
输入：nums = [9,1,7,9,7,9,7] 输出：1
限制：
1 <= nums.length <= 10000 1 <= nums[i] < 2^31
解： 思路 //相同的数,第i位均为1或均为0。 //设数组中第i位为0的数的个数为cnt0，第i位为0的数的个数为cnt1。 //若只出现一次的数第i位为1，则cnt1 = 3n + 1，cnt0 = 3n;第i位为0同理。
实现 1.遍历数组，统计第i位为1的数的个数，若该位为1，则res += 2^(i-1)，为0则+0。 2.总共统计32位
class Solution { public: int singleNumber(vector<int>& nums) { if(nums.empty()) return 0; int res; unsigned int bitMap = 1; //定义为无符号数，因为bitMap == 0x80000000 时，有符号数认为其是负数，C++中负数不能左移 for(int i = 0;i < 32;++i) //第i位 { int cnt = 0; for(int j = 0;j < nums.size();++j) //统计数组数字第i位为1的个数 if((nums[j] & bitMap)) ++cnt; if(cnt%3) res += bitMap; //返回值直接用bitMap计算即可 bitMap <<= 1; } return res; } };