本文共 3436 字，大约阅读时间需要 11 分钟。

微信搜索：编程笔记本

微信搜索：编程笔记本 微信搜索：编程笔记本

今天要给大家分享的是位运算的几种妙用。

位运算大多时候都很晦涩难解，大家若是对某种用途的原理不理解，请私信告诉我，我将给予详细解答。

目录

1. 位运算符

&：按位与

|：按位或 ^：异或 ~：取反 <<：左移（右边补零） >>：右移（左边补符号位）

微信搜索：编程笔记本

微信搜索：编程笔记本 微信搜索：编程笔记本

2. 交换两个变量的值

常规操作：

void swap(int& a, int& b){
       int tmp = a;    a = b;    b = tmp;}

位运算：

void swap(int& a, int& b){
       a ^= b;    b ^= a;    a ^= b;}

3. 判断奇偶

常规操作：

if (n % 2 == 0) {
       cout << "Even" << endl;} else {
       cout << "Old" << endl;}

位运算：

if ((n & 1) == 0) {
       cout << "Even" << endl;} else {
       cout << "Old" << endl;}

微信搜索：编程笔记本

微信搜索：编程笔记本 微信搜索：编程笔记本

4. 求平均值

常规操作：

int average(int a, int b){
       return (a + b) / 2;}

位运算：

int average(int a, int b){
       return (a & b) + ((a ^ b) >> 1);}

5. 计算某数的二进制表示中的 1 的个数

位运算：

int countOne(int num){
       int cnt = 0;    for (int i = 0; i < 8 * sizeof(num); ++i) {
           cnt += num & 1;        num >>= 1;    }    return cnt;}

6. 乘（除）以 2^m

常规操作：

int calculate(int num, int m){
       return num * pow(2, m); // return num / pow(2, m);}

位运算：

int calculate(int num, int m){
       return num << m; // return num >> m;}

微信搜索：编程笔记本

微信搜索：编程笔记本 微信搜索：编程笔记本

7. 将某数的二进制表示中最右边 1 置零

常规操作：

void setBitZero(int& num){
       int mask = 1;    for (int i = 0; i < 8 * sizeof(num); ++i) {
           if ((num & mask) != 1) {
               num ^= mask;            break;        }    }}

位运算：

void setBitZero(int& num){
       num = num & (num - 1);}

8. 计算绝对值

常规操作：

int abs(int num){
       return num >= 0 ? num : -num;}

位运算：

int abs(int num){
       int tmp;    tmp = num >> (8 * sizeof(num) - 1);        return (num ^ tmp) - tmp; // return (num + tmp) ^ tmp;}

9. 判断某正数是不是 2 的整数次幂

常规操作：

bool isPower2(int num){
       int cmp = 1;    while (cmp < num) {
           cmp *= 2;    }    return cmp == num;}

位运算：

bool isPower2(int num){
       return (num != 0 && (num & (num - 1) == 0));}

微信搜索：编程笔记本

微信搜索：编程笔记本 微信搜索：编程笔记本

10. 找出数据列表中只出现一次的数（其他数都出现了两次）

常规操作：

int showOnece(vector
   
     nums){
       int res;    map
    
      m;    for (auto num : nums) {
           ++m[num];    }    for (auto num : nums) {
           if (m[num] == 1) {
               res = num;            break;        }    }    return res;}
    
   

位运算：

int showOnece(vector
   
     nums){
       int res = 0;    for (auto num : nums) {
           res ^= num;    }    return res;}
   

11. 小试牛刀：LeetCode_268 缺失数字

题目描述：

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 ... n 中没有出现在序列中的那个数。

示例：

• 输入: [3, 0, 1]

  输出: 2

• 输入: [9, 6, 4, 2, 3, 5, 7, 0, 1]

  输出: 8

参考代码：

int missingNumber(vector
   
    & nums) {
       int len = nums.size();    int res = len;    for (int i = 0; i < len; ++i) {
           res ^= i ^ nums[i];    }    return res;}
   

12. 小试牛刀：LeetCode_17.10 主要元素

题目描述：

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回 -1 。

示例：

• 输入：[1,2,5,9,5,9,5,5,5]

  输出：5

• 输入：[3,2]

  输出：-1

参考代码：

int majorityElement(vector
   
    & nums) {
       int res= 0;    int len = nums.size();    for (int i = 0; i < 8 * sizeof(int); ++i){
           int mask = 1 << i;        int countOne = 0;        for (int j = 0; j < len ; ++j){
               if ((nums[j] & mask) != 0) {
                   ++countOne;            }        }        if (countOne > len / 2) {
               res ^= mask;        }    }    int countRes = 0;    for (int i = 0; i < len ; i++) {
           if (nums[i] == res) {
               ++countRes;        }    }    if (countRes <= len / 2) {
           res = -1;    }    return res;}
   

微信搜索：编程笔记本

微信搜索：编程笔记本 微信搜索：编程笔记本

转载地址：http://nhkgn.baihongyu.com/