位运算的妙用

September 27, 2017
算法

对于一些特定问题，巧妙运用位运算能使解法异常简洁和高效，同时，适当运用位运算也能对程序进行优化。

运用的时候，可能涉及多种位运算。

计算机中位运算分为以下六种：

  1. 与 &
  2. 或 |
  3. 非 ～
  4. 异或 ^
  5. 左移 «
  6. 右移 »

异或 #

异或具有以下性质（可能还有，下同）：

  1. a^b = b^a
  2. a^a = 0
  3. a^0 = a

实例 #

[leetcode 136 single number]


Given an 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?


**题目大意：**每个元素都出现两次，但有一个只出现一次，找出出现一次的元素。


这题如果用标记数组做 时间复杂度，空间复杂度都是 O(n) 。但如果利用异或的前两个性质，则可以将空间复杂度压缩到O(1)。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int result = nums[0];
        for(int i=1;i<nums.size();i++)
            result = result ^ nums[i];
        return result;
    }
};

与或 #

与运算可以快速取得一个变量某个 bit位 的数值。

如： 0010 & 1110 = 0010 0010 & 1101 = 0000

如果 0010 & b = 0010 则表明 b 的第二位是1，不等则为0。


与运算可以快速将某bit为快速置为0，而或运算可以快速将某bit位置为1。

与运算的其他用法

  • n & (n-1) 可以把n的最低位置0

左移右移 #

左移相当于乘2，右移相当于除2，并且它们的速度比乘除要快。

所以当程序中出现大量✖️2，或➗2运算时，可以用左移和右移进行优化。

例子 #

LeetCode Bit Manipulation