[LeetCode]巧用位运算

引言

在编程过程中，位运算是常用的运算之一，直接对二进制位操作使得位运算比一般的操作指令更加高效。巧用位运算，可以解决一些其他运算符号难以解决或者用其他方法解决起来更加复杂的问题。

01

二进制数字中“1”的个数

int get_1_Count(int n)
{
  int count = 0;
  while (n)
  {
    n = n&(n-1);
    count++;
  }
  return count;
}

复制

02

两个数作加法

不使用 “+” 运算符的条件下对两个输入参数做加法运算，位运算也可以做到！那就是异或！

• a^b：按位相加后没有进位的和；
• a&b：可得可以产生进位的地方；
• (a&b)<<1：得到进位后的值。

int get_sum_by_bitAdd(int a, int b)
{
  int aTemp = 0, bTemp = 0;
  while (b != 0) {
    aTemp = a ^ b;
    bTemp = (a & b) << 1;
    a = aTemp;
    b = bTemp;
  }
  return a;
}

复制

03

两个数作减法

首先需要知道位运算的一个运算规律：~n=-(n+1)，比如：~3=-4

两个数作减法，如a-b可以转换成加法a+(-b)，由上面的运算规律可知-b=~(b-1)，因此a-b=a+(-b)=a+[~(b-1)]，利用上一节的位运算实现两数相加即可。

int sub_by_bit(int a, int b)
{
  int _b = ~(b - 1);
  return get_sum_by_bitAdd(a, _b);
}

复制

04

交换两个数

在不创建临时变量的条件下交换两个数，同样是异或！

• 第一次异或：找出两个变量里bit位不同的位，保存为a；
• 第二次异或：取反b里与a不同的bit位，将b变成了原来的a；
• 第三次异或：取反a里与b不同的bit位，将a变成了原来的b.

void swap_by_bitXor(int a, int b)
{
  printf("%d  %d \n", a, b);
  a = a^b;
  b = a^b;
  a = a^b;
  printf("%d  %d \n", a, b);
}

复制

05

找出数组里只出现一次的1个数（其余数字均出现两次）

LeetCode第136题： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

// 基本方法：
// 1. a^b^c = a^c^b
// 2.   a^a = 0
// 3.   a^0 = a
 
int find_Once_by_bitXor(int[] arr, int Length) {
    int result = 0;
    for (int i = 0; i < Length; i++) {
        result ^= arr[i];
    }
 
    return result;
}

复制

与之类似，LeetCode第389题：给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。示例：

输入：s = "abcd" t = "abcde" 输出：e 解释：'e' 是那个被添加的字母。

解题思路与上面一致，异或，最终结果即为添加的值：

char findTheDifference(string s, string t) {
        char ch = 0;
        
        for(int i=0;i<s.size();i++){
            ch^=s[i];
        }
        for(int i=0;i<t.size();i++){
            ch^=t[i];
        }   
        return ch;
    }

复制

06

找出数组里只出现一次的1个数（其余数字均出现3次）

LeetCode第137题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素

在这个问题中，所有的bit的出现次数只会有两种情况，3*n，3*n + 1,这里的 n 是任意整数，假设你遍历数组，其实会有一个中间态就是 3*n + 2 存在，对于除这个数以外的其他数，过程大概是 3*n + 1 -> 3*n + 2 -> 3*n，我们只要记录的就是 3*n + 1 和 3*n + 2的情况，因为 3*n 其实是一个初始状态（n=0）,记不记录和我们最后要返回的答案无关，而记录 3*n + 2 是为了恢复一些 bit 从 3*n + 2 到 3*n.

int singleNumber(int[] nums, int Length) {
    int one = 0, two = 0;
    for (int i = 0; i < Length; ++i) {
        // 找出当前的 3n + 1
        one = (nums[i] ^ one) & (~two);
        // 找出当前的 3n + 2
        two = (nums[i] ^ two) & (~one);
    }
 
    return one;
}

复制

关于上述代码可以做个简单的测试，由于是要找出数组中只出现一次的那个数，所以与数字的顺序无关，不放Jungle举个最简单的例子nums[4] = {3,3,3,1} ,过程如下图：