位運算的應用：
程式中的所有數在計算機記憶體中都是以二進制的形式儲存的。所謂位運算，就是直接對整數在記憶體中的二進制位進行操作，一般解題時都用一個十進制整數來代表某個集合。
基本的位運算操作：
&(按位與)、|(按位或)、^(按位異或)、~ (按位取反)。
其中，按位取反運算符是單目運算符，其餘均為雙目運算符。
位運算符的優先級從高到低，依次為~、&、^、|，
其中~的結合方向自右至左，且優先級高于算術運算符，其餘運算符的結合方向都是自左至右，且優先級低于關系運算符。
下面總結一下一些高效且實用的位運算技巧:
1、 枚舉n個元素的所有子集：
這個就比較常用了，枚舉出所有的二進制子集，總共2^n個集合
for (int i = 0; i< 1<<n; i++){
for (int j = 0; j < n; j++)
if (i & (1<<j))printf("%d ", j);
}
随便舉一個例子：
hdu 4462- Scaringthe Birds
題意：有一個n*n的網格，有k個格子交點處可以放置稻草人，稻草人可以保護離它曼哈頓距離不超過d的範圍内的點，求最少放幾個稻草人可以保護所有的點。
分析：稻草人最多10個，即使不使用dlx，直接暴力效率也足夠高，枚舉所有的放置的情況，總共2^10-1種情況，注意題目有兩個坑點（也不算是坑點吧，隻是我被坑了而已），一個就是注意到距離是manhattan distance，而不是哈密爾頓距離，不要看漏了，還有一個就是可以放置稻草人的點是不要保護的，是以隻要看是否覆寫了其他n*n-k個點即可…….
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
int vis[55][55], r[15], x[15], y[15];
int n, k;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct po{
int x, y;
po(int x = 0, int y = 0):x(x), y(y){}
};
vector<po> G[15];
void dfs(int x, int y, int xx, int yy, int r, int c)
{
vis[x][y] = 1;
for (int i = 0; i < 4; i++){
int nx = x + dir[i][0], ny = y + dir[i][1];
if (nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny]) continue;
int d = abs(nx-xx) + abs(ny-yy);
if (d <= r){
G[c].push_back(po(nx, ny));
dfs(nx, ny, xx, yy, r, c);
}
}
}
int main()
{
while (scanf("%d", &n), n){
scanf("%d", &k);
for (int i = 1; i <= k; i++) G[i].clear();
for (int i = 1; i <= k; i++) scanf("%d %d", &x[i], &y[i]);
for (int i = 1; i <= k; i++) scanf("%d", &r[i]);
for (int i = 1; i <= k; i++){
memset(vis, 0, sizeof(vis));
dfs(x[i], y[i], x[i], y[i], r[i], i);
}
int a = (1<<k), ans = INF;
if (k == n*n) { puts("0");continue;}
for (int i = 1; i < a; i++){
memset(vis, 0, sizeof(vis));
int cnt = k, c = 0;
for (int j = 1; j <= k; j++) vis[x[j]][y[j]] = 1;
for (int j = 1; j <= k; j++){
if (i & (1 << (j-1))){
c++;
for (int l = 0; l < G[j].size(); l++){
int f = G[j][l].x, s = G[j][l].y;
if (!vis[f][s]){
vis[f][s] = 1;
cnt++;
}
}
}
}
if (cnt == n*n) ans = min(ans, c);
}
if (ans == INF) ans = -1;
printf("%d\n", ans);
}
return 0;
}
2、高效枚舉某個集合所有的子集。
就像是統計一個數的二進制位有多少個1一樣：
int cnt = 0;
scanf("%d",&n);
for(; n; n &=(n-1), cnt++);
這樣處理很快，循環次數為這個數當中二進制位為1的個數，n &= (n-1)的意思是清除n的二進制位當中最左邊的1.
那麼枚舉某個集合Sup的子集的方法：
//如果不考慮空集的話，那麼循環到0就可以結束了。
for (int sub = sup;sub; sub = (sub-1) & sup){
//對子集sub的處理
}
考慮空集的話，使用dowhile 友善點
int t = sup;
do{
//對子集的處理
t = (t-1) & sup;
}while (t != sup);
例題：
Uva1354-MobileComputing
題意：給出一個房間的寬度r和s個挂墜的重量wi，設計一個盡量寬（但寬度不能超過房間寬度r）的天平，挂着所有挂墜，天平由長度為1的木棍組成，每一端要麼挂一個挂墜，要麼挂另一個天平。
分析：懸挂吊墜的方式有很多種，挂墜最多6個，暴力枚舉即可。一個合法的挂的方式可以看作是一顆二叉樹，那麼我們隻需要枚舉所有可能的二叉樹？怎麼枚舉呢？正如紫書上面所說的：自頂向下構造，每次枚舉左子樹用到哪些子集，那麼這棵樹當中的挂墜就确定了，然後右子樹就是剩下的挂墜。是以我們遞歸構造所有可能的二叉樹，對于每一個子樹的根節點，統計目前懸挂方式的左右臂長度，最後對于根節點，在所有可能的長度中選出不超過r的最長的寬度即可。
是以問題的一個關鍵是進行子樹挂墜集合的枚舉，然後程式實作過程中可以進行記憶化搜尋，對于已經處理過的子集，直接傳回即可。整體架構感覺類似于數位dp的實作，那裡是枚舉數位然後統計，而這裡是枚舉子集然後統計。剩下的都是些細節問題了，注意計算左右臂長度時要考慮全面，這題的一個條件是保證天平的寬度不會恰好在r-1e5到r+1e5之間，是以我們可以忽略精度問題，直接進行浮點數的比較。
感覺做過這題之後體會到了位運算的友善與實用。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include <vector>
#define INF 0x3f3f3f3f
#define LL long long
#define EPS 1e-6
using namespace std;
const int N = 1<<6;
struct node{
double ll, rl;
node(double l = 0, double r = 0): ll(l), rl(r){}
};
vector<node> scale[N];
int vis[N], w[6], sw[N];
int n;
double r;
int bitcount(int S)
{
int cnt = 0;
for (; S; S &= (S-1), cnt++);
return cnt;
}
void dfs(int S)
{
if (vis[S]) return ;
vis[S] = 1;
if (bitcount(S) == 1){
scale[S].push_back(node(0, 0));
return ;
}
for (int l = S & (S-1), r; l; l = (l-1) & S){
r = S^l;
dfs(l); dfs(r);
for (int i = 0; i < scale[l].size(); i++){
for (int j = 0; j < scale[r].size(); j++){
double llen = max(scale[l][i].ll + sw[r]*1.0/sw[S], scale[r][j].ll - sw[l]*1.0/sw[S]);
double rlen = max(scale[r][j].rl + sw[l]*1.0/sw[S], scale[l][i].rl - sw[r]*1.0/sw[S]);
scale[S].push_back(node(llen, rlen));
}
}
}
}
double solve()
{
int S = (1<<n)-1;
double ans = -1;
dfs(S);
for (int i = 0; i < scale[S].size(); i++){
double t = scale[S][i].ll + scale[S][i].rl;
if (t <= r && t > ans) ans = t;
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while (t--){
scanf("%lf %d", &r, &n);
for (int i = 0; i < n; i++) scanf("%d", w+i);
for (int i = 1; i < 1<<n; i++){
vis[i] = sw[i] = 0;
scale[i].clear();
for (int j = 0; j < n; j++)
if (i & (1<<j)) sw[i] += w[j];
}
printf("%.9f\n", solve());
}
return 0;
}
3、枚舉大小為k的所有子集。
核心代碼：
int t =(1<<k) - 1;
while (t <1<<n){
//對子集的處理
int x = t & -t, y = t + x;
t = ((t & ~y) / x >> 1) |ｙ;
}
例題：
Hdu5914- Triangle
題意：給定n，有n根長度分别為1、2…..n的木棍，問最少去掉幾根可以使得剩下的木棍不能組成三角形。
分析：不用斐波那契數的話，考慮到n<=20,可以直接暴力，按去掉木棍根數從小到大開始枚舉，直到不能組成三角形為止。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int a[25] = {0, 0, 0, 0, 1, 1, 2};
int judge(int x, int n)
{
int b[30];
int k = 0, tag = 1;
for (int i = 1; i <= n; i++)
if (!(x & (1 << (i-1)))) b[k++] = i;
for (int j = k-1; j >= 2 && tag; j--)
if (b[j] < b[j-1]+b[j-2]) tag = 0;
return tag;
}
int main()
{
for (int i = 7; i <= 20; i++){
int flag = 1;
for (int k = a[i-1]; flag ; k++){
int co = (1<<k)-1;
while (co < 1 << i){
int x = co & -co, y = co + x;
co = ((co & ~y) / x >> 1) | y;
if (judge(co, i)) {flag = 0; a[i] = k; break;}
}
}
}
int t, ca = 0, n;
scanf("%d", &t);
while (t--){
scanf("%d", &n);
printf("Case #%d: %d\n", ++ca, a[n]);
}
return 0;
}
4、枚舉不相鄰元素的集合。
for (int i = 1; i< (1<<n); i++){
if ((i >> 1) & i) continue;
//對子集的處理
}
刷的題太少了，暫時沒有遇到用過這個的題….
5、 枚舉第k位一定為1的所有子集。
可以從第k位為1的最小整數開始循環，直到取遍所有的子集。
//從滿足條件的最小的整數m開始,枚舉所有第k位一定為1的所有子集：
for (int t = m; t< (1 << n); t = (t+1) | m){
//對子集的處理
}
6、 當然還有很多有用的位運算，在此借用Matrix67大牛的總結：
下面列舉了一些常見的二進制位的變換操作。
功能 | 示例 | 位運算
去掉最後一位 | (101101->10110) | x>> 1
在最後加一個0 | (101101->1011010) | x<< 1
在最後加一個1 | (101101->1011011) | x<< 1+1
把最後一位變成1 | (101100->101101) | x| 1
把最後一位變成0 | (101101->101100) | x| 1-1
最後一位取反 | (101101->101100) | x^ 1
把右數第k位變成1 |(101001->101101,k=3) | x | (1<< (k-1))
把右數第k位變成0 |(101101->101001,k=3) | x & ~(1 << (k-1))
右數第k位取反 |(101001->101101,k=3) | x ^ (1<< (k-1))
取末k位 |(1101101->1101,k=5) | x &((1 << k)-1)
取右數第k位 |(1101101->1,k=4) | x >>(k-1) & 1
把末k位變成1 |(101001->101111,k=4) | x | ((1<< k)-1)
末k位取反 |(101001->100110,k=4) | x ^ ((1<< k)-1)
把右邊連續的1變成0 |(100101111->100100000) | x &(x+1)
把右起第一個0變成1 |(100101111->100111111) | x | (x+1)
把右邊連續的0變成1 |(11011000->11011111) | x | (x-1)
取右邊連續的1 | (100101111->1111) |(x ^ (x+1)) >> 1
去掉右起第一個1的左邊 | (100101000->1000) | x & (x ^ (x-1))
最後一個在樹狀數組中會用到。
7、 關于位運算的一點總結：
很久之前借了學校圖書館的一本叫做算法心得的書，看過之後感覺作者簡直神奇，不愧是大師，裡面是各種優化程式的奇淫技巧，不過那時什麼都不懂，看了覺得沒用，現在懂了一點了，然而之前看過的都忘了，裡面關于位運算的内容特别多，值得一看。
下面就是一些常見的技巧，效率都比普通運算要高很多
/*1、交換兩個整數的值：
int a, b;
a = a ^ b;
b = a ^ b;
a = a ^ b;
與下面的等價,不過利用的是^的重要性質，效率當然比算術運算高
a = a + b;
b = a - b;
a = a - b;
2、與2的x次方的運算
int a;
a <<= x;//乘2^x
a >= x;//除2^x
a & (1 << x) - 1 //取a%(2^x)的餘數
a & 1//判斷奇偶性，為0則a為偶數,否則為奇數
a & (a-1)//判斷a是否為2的幂或者0，結果為0代表是，否則代表不是
3、其他常用技巧
int a, b;
a = ~a + 1//取相反數
a = (a ^ (a >> 31)) - (a >> 31) //取絕對值
(a & b) + ((a ^ b) >> 1) //取平均值
a ^ b//判斷a、b符号是否相同，如果結果>0則相同，否則不同
*/
(1)、位運算優先級較低，如果結合其他的運算符，那麼最好在使用時加上括号，當然如果很清楚優先級就另當别論了。
(2)、位運算雖說高效，但是很多枚舉子集的技巧資料量大點就無法使用了，是以還是得慎用，根據題目的資料範圍而定吧。
(3)、使用位運算注意細節的處理，比如說枚舉子集時的起點，終點等等。
(4)、使用位運算關鍵是了解每一個運算的特點，靈活運用它們的性質，并且找到問題與位之間的聯系，其實上面的幾個枚舉集合的技巧都是根據位之間的聯系然後運用相應的運算符得出的，一些位運算符也有一些非常重要的特點，比如說異或運算具有交換律，結合律，自反性等等。
(5)、位運算應用很廣，展現在很多算法和資料結構上，比如說狀态壓縮，樹狀數組等等，在狀态壓縮中的使用通常是最常見的，很多算法都設計到狀态之間的轉移，比如說搜尋，dp等等。有時候很難表示目前的這個狀态，但是通過二進制位便可以解決了，是以位運算還是很友善和實用的，比如說一些在棋盤，網格中要表示某一行/列的狀态時的問題。
在資料結構中的應用最常見的是樹狀數組，借用論文上面的話：樹狀數組的思想核心在于運用了十進制數與二進制數之間的聯系，通過數的二進制形式來決定儲存資訊，把複雜的問題簡單化,方法簡單巧妙。
樹狀數組的優勢在于代碼長度短，不易出錯，思想巧妙，算法複雜度低，維護簡單，易推廣到二維甚至三維等等。對于資料結構要求操作不複雜的題目，是上佳的選擇。
而且線段樹也涉及到了簡單的右移位運算，或運算等等。
![10 個你有可能不知道的Android Studio技巧[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)