位运算(Bit Manipulation)在算法中的应用

最近刷LettCode，遇到几个没思路的算法题，都是关于位运算的

# 136 Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

找出成对数数组中的那个单身狗（成天吃狗粮干什么）

• O(n^2)思路

先将数组进行排序，然后每次比较相邻的两个数且前进2个，出现不相等则输出第一个数；

• O(nlogn)思路

改进排序算法，采用快排

• 最终解决思路O(n)

迭代一次数组通过位运算，最后得出结果即数组中的单身数。

原理：

0 xor any = any；1 xor any = ~any；any xor any = any

异或运算的feature使得再出现两个相同的数时，异或结果会变成0，而其中不成双的数最后相当于与0异或得以留存下来

代码：

 1 class Solution {
 2 public:
 3     int singleNumber(vector<int>& nums) {
 4         int ans=0;
 5         for(int e : nums){
 6             ans ^= e;
 7         }
 8         return ans;
 9     }
10 };

# 371 Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = -2, b = 3
Output: 1

不使用+，-运算符进行两数的相加，这题第一时间还真没思路

原理：

• 两数在二进制下相加，不考虑进位的情况下，如果某位上分别是1，0则该位结果为1；若都是1则结果是0；都是0也是0；这情况和异或一致，这样我们将两数异或就得到了未进位下的两数和。

• 而发生进位则是两数对应位上都是1的情况，这时候我们通过按位与操作，得到需要进位的位置，然后进行左移就是每个位需要加上的进位。
• 将未进位的数之和 同 发生的进位相加（注意这里又相当于两数相加），就得到了结果。
• 同时上一步的又会产生新的进位，我们需循环到进位为零的情况

注意：C++中的负数的左移操作最后会变为最小的负整数而不是0，所以需要对进位数进行截取  => carry = caryy & 0x7FFFFFFF (整型长32位)

代码：

 1 class Solution {
 2 public:
 3     int getSum(int a, int b) {
 4         int carry;
 5         while(b){
 6             carry = a & b & 0x7FFFFFFF;
 7             a = a ^ b;
 8             b = carry << 1;
 9         }
10         return a;
11     }
12 };