- 输入一个整数，输出该数二进制表示中1的个数。附加题：判断一个数是否是2的幂。
- 一个整数数组里除了两个数字以外，其他数字都出现两次。请找出只出现一次的数字，要求时间复杂度O(n)，空间复杂度O(1)。
- 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/即加减乘除四则运算符号。
1、思路：
常规方法：逐位和1做与运算，看是否为1。如果右移位，当符号位为1时，会陷入死循环（高位补1）。所以选择左移位，当标志位为0时说明所有位都移动完成。
巧妙方法：当n-1时，与n相比，最右边的1变为0，再右侧的0变为1。所以n&(n-1)不为0，则计数加1，有几个1就有几次循环。
判断2的幂：用二进制表示该数，如果是2的幂，则只有高位出现1，其他位都是0。
1 int NumberOf1_Solution1(int n) 2 { 3 int count = 0; 4 unsigned int flag = 1; 5 while(flag) 6 { 7 if(n & flag) 8 count ++; 9 10 flag = flag << 1;11 }12 13 return count;14 }15 16 int NumberOf1_Solution2(int n)17 {18 int count = 0;19 20 while (n)21 {22 ++ count;23 n = (n - 1) & n;24 }25 26 return count;27 }
2、思路：
空间复杂度O(1)说明不能用hash。真经：异或自己得0，异或0得自己。首先，所有数组中的数字都异或一遍，出现两次的相互抵消，最后的结果是两个只出现1次的数字异或的结果。其次，最右边出现1的位说明两个数在该位上不同，则以该位为0或为1分隔成两个数组。最后，在新的两个数组上都异或一遍，得两个数字。
1 void FindNumsAppearOnce(int data[], int length, int* num1, int* num2) 2 { 3 if (data == NULL || length < 2) 4 return; 5 6 int resultExclusiveOR = 0; 7 for (int i = 0; i < length; ++ i) 8 resultExclusiveOR ^= data[i]; 9 10 unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); 11 12 *num1 = *num2 = 0;13 for (int j = 0; j < length; ++ j)14 {15 if(IsBit1(data[j], indexOf1))16 *num1 ^= data[j];17 else18 *num2 ^= data[j];19 }20 }21 22 // 找到num从右边数起第一个是1的位23 unsigned int FindFirstBitIs1(int num)24 {25 int indexBit = 0;26 while (((num & 1) == 0) && (indexBit < 8 * sizeof(int)))27 {28 num = num >> 1;29 ++ indexBit;30 }31 32 return indexBit;33 }34 35 // 判断数字num的第indexBit位是不是136 bool IsBit1(int num, unsigned int indexBit)37 {38 num = num >> indexBit;39 return (num & 1);40 }
3、思路：
只能用位运算。模拟加法过程，先各个位上相加不考虑进位，再考虑进位，最后把进位加上。而0+0=0，1+1=0，0+1=1，1+0=1，即异或的结果。只有1+1=0才会产生进位，那么1&1=1，将1左移表示进位。
1 int Add(int num1, int num2) 2 { 3 int sum, carry; 4 do 5 { 6 sum = num1 ^ num2; 7 carry = (num1 & num2) << 1; 8 9 num1 = sum;10 num2 = carry;11 }12 while(num2 != 0);13 14 return num1;15 }