一、位運算常用的兩種操作：
(1) 求n的第k位數字：n >> k & 1
(2) 回傳n的最后一位1：lowbit(n) =n & -n
二、求n的第k位數字：n >> k & 1
n =15 (1111)2 : 先把第k位移到最后一位 n >> k, 看個位是幾 x & 1, n >> k & 1
具體實作：
#include<iostream>
using namespace std;
int main()
{
int n=10;
for(int k=3; k>=0; K--) cout << (n >>i & 1) << endl;
return 0;
}
三、lowbit是樹狀陣列的基本操作
1. lowbit(x)的作用: 回傳x的最后一位 1：
(1) x = 1010 lowbit(x) = 10
(2) x = 101000 lowbit(x) = 1000
2. lowbit(x) 的實作程序：
x & -x = x & (~x + 1)
-x = ~x + 1
x = 1010 ....10000
~x = 0101 ....01111
~x + 1 = 0101 ....10000
x & (~x + 1) = 0000 ....10000
3. lowbit(x)的應用：求二進制中 1 的個數
具體實作：
#include <iostream>
using namespace std;
int lowbit(int x)
{
return x & -x;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
int res = 0;
while(x) x -= lowbit(x), res++;//每次減去x的最后一位1
cout << res <<endl;
}
return 0;
}
查看更多
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51520.html
標籤：其他
上一篇：論文翻譯：《PRIMES is in P》——素性測驗的確定性多項式時間演算法研究
下一篇：重溫——遞推遞回與搜索