算法学习之位运算

本文主要是介绍算法学习之位运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、作用

在复杂问题中经常可以作为工具让代码更加优雅。

二、知识储备基础

“~”：取反符   0->1, 1->0

三、常见的两种操作

1.n的二进制表示中第k位数字是几？

(1)原理

先右移操作，再与操作。

（2）代码实现

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;int main(){int n = 10;for(int i = 3; i >= 0; -- i){printf("%d", n>>i&1);}return 0;
}

2.lowbit操作 （树状数组的基本操作）

（1）作用

  返回一个二进制数，这个数是x的最后一位1（及其后面的0）。

（2）举例

（3）具体实现

  在 c++中一个正整数对应的负数是原数（该正整数）的补码。补码是原码取反加1。

  所以，x&(-x) = x&(~x+1)

int lowbit(int x){return x & -x;
}

（4）原理解释

（5）应用   统计x中1的个数

  代码实现

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;int lowbit(int x){return x & -x;
}int main(){int x;scanf("%d", &x);int res = 0;while(x){x -= lowbit(x);++ res; }printf("%d ", res);return 0;
}

这篇关于算法学习之位运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---