ビット演算のアルゴリズム問題での使用(C++)

一、算術演算子とビット演算子
演算子:+、-、*、/、%
ビット演算子:&ビットと、|ビットまたは、^ビット別または、~ビット別逆、<<左シフト右側補0、>>右シフト左側補記号ビット、>>右シフト左側補0
注意:シフト演算には必ず値を付けます.すなわち、aを2ビット左にシフトするのはa<<2であるべきではない.それは
a = a<<2;またはa<=2;
.
二、ブロンフィルター
http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html
http://segmentfault.com/a/1190000002729689
http://www.cnblogs.com/kissdodog/archive/2013/04/18/3027812.html
Webページブラックリストシステム
スパムフィルタリングシステム
爬虫類のウェブサイト判断重複システム
ある程度のミスを許す
空間に対する要求が厳しい
三、ビット演算練習問題
1、余分なストレージスペースを使用せずに2つの整数を交換する
解法1:class  Swap { public :      vector< int > getSwap(vector< int > num) {          num[ 0 ] = num[ 1 ]-num[ 0 ];          num[ 1 ] = num[ 1 ]-num[ 0 ];          num[ 0 ] = num[ 0 ]+num[ 1 ];          return  num;      } };
解法2:
class 
Swap {
public
:
    vector<
int
> getSwap(vector<
int
> num) {
        num[
0
] ^= num[
1
];
        num[
1
] ^= num[
0
];
        num[
0
] ^= num[
1
];
       
return
num;
    }
};
2、比較文を使用せずに2つの数のサイズを比較する
解法:比較文を用いずに大きさを判断するには,まず1,0とa,bの2つの数の線形の組み合わせで大きさを判断することを考える.次に,戻りaにどのような状況があるかを解析し,この状況を1つの変数で記録し,戻りbの場合を別の変数で記録する.状況分析は以下の表(+は非負を表す):
a
b
a-b
戻り値
+
+
+
a
-
-
+
a
+
+
-
b
-
-
-
b
+
-
+(オーバーフロー-)
a
-
+
-(オーバーフロー+)
b
1 aを返すには、a、bが同号であり、a-bが負ではない場合と、a、bが負ではない場合と、a、bが負ではない場合と、a、bが負ではない場合と、a、bが負ではない場合と、a、bは異号であり、aは負ではない.
②戻りbにも2つの場合がある:a、bは同号でa-bは負である;a、bは異号であり、aは負である.
このようにしてa-bの記号を直接判断しないことができます.オーバーフローする可能性があるからです.class Compare { public :             int getSign( int num) {          return ((num >>  31 )& 1 )^ 1 ;      }             int getMax( int a,  int b) {          int as = getSign(a);          int bs = getSign(b);          int cs = getSign(a-b);                     int dif = as^bs;          int same = dif^ 1 ;          int reta = same*cs+dif*as;          int retb = reta^ 1 ;          return reta*a+retb*b;      } };
3、1つの配列の中でただ1つの数が奇数回現れて、その残りの数はすべて偶数回現れて、この奇数回現れた数を探し出します
要求:O(N)O(1)
解法:すべての数をビット別または演算し、偶数回のビット別または後は0、奇数回のビット別または後は変わらない.class OddAppearance { public :      int findOdd(vector< int > A,  int n) {          int res = A[ 0 ];          for ( int i =  1 ;i < n;i++) {              res ^= A[i];          }          return res;      } };
4、1つの配列の中で2つの数が奇数回現れて、その残りの数はすべて偶数回現れて、この2つの奇数回現れた数を探し出します
解法:
①第1回目に全てのデータを異種化し、奇数回出現した2つの数の異種化または結果を得る
xor;
2 xorの中で1のビットで、2つの数の中できっと異なっていて、1つの数はこのビットで1の別の数が0で、xorの中で1のビットを見つけます(k位と仮定します);
3配列をもう一度巡り,k位1の数を異にし,最後に得られた結果は探すべき数の1つであり,xorとこの数を異にするともう1つの探す数が得られる.
class
 OddAppearance {
public
:
    vector<
int
> findOdds(vector<
int
> arr, 
int
 n) {
        
int
 xor = 
0
;
        vector<
int
> result;
        for (
int
 i = 
0
;i < n;i++) {
            xor ^= arr[i];
        }
        
int temp = xor &(~xor + 1
);//この演算はxorの中で右から1番目が1のビットを見つけることができて、xorを逆にして1番目の1の右の1ビットを1に変えることができて、プラスします
//1最初の1の右側を1桁上げることで、最初の1の位置を1にすることができますが、他の位置は変更されていません.
//xor按位与可保留第一个1.
        
int
 res1 = 
0
;
        for (
int
 j = 
0
;j < n;j++) {
            if ((arr[j]&temp) != 
0
){//ビットと、ビットまたは、ビット別または、ビット別に判断する文は、ビット演算にカッコを付けなければなりません
                res1 ^=arr[j];
            }
        }
        
int
 res2 = xor ^res1;
        result.push_back(min(res1,res2));
        result.push_back(max(res1,res2));
        
return
 result;
    }
};