ビット演算——恐ろしく強い

前言
周知のように、ビット演算は私たちがコンピュータを学ぶ上で必ず学ぶもので、前人はバイナリ、ビット演算で私たちに操作の簡単なコンピュータをくれたが、私たちはビット演算に触れることは少ない.今日はアルゴリズムでのビット演算の運用を紹介します.
ビットえんざんきそ

&

押位と

対応する2つのバイナリビットがいずれも1である場合、そのビットの結果値は1であり、そうでない場合、0

である.

|

ビットまたは

の2つの対応するバイナリビットのうち1つが1である限り、そのビットの結果値は1

である.

^

按位異または

演算に参加する2つのバイナリビット値が同じであれば0、そうでなければ1

である.

~

取反

~は、1つのバイナリ数をビットで反転するための1元演算子で、0が1になり、1

になります.

<<

左に

移動

は、1つの数の各バイナリビットをすべてNビット左にシフトするために使用され、右補0

>>

右シフト

は、1つの数の各バイナリビットをNビット右端にシフト、右端にシフト低位は切り捨てられ、符号なし数に対しては高位補0

となる.

奇技淫巧
1.テクニック1:xの最下位を消す1

x & (x-1)
x = 1100
x-1 = 1011
x & (x-1) = 1000

1.1.整数nが2のべき乗であるか否かをO(1)時間で検出する.

構想解析:Nが2のべき乗であれば,Nは2つの条件を満たす.1.N>0 2.Nのバイナリ表現には1ビットNのバイナリ表現が1つしかないので,N&(N−1)を用いて一意の1つを消去する.Nが2のべき乗であれば,N&(N−1)の結果は0となり,判断できる.

1.2.2を適用して、32ビットの整数のバイナリ表現の中でどれだけ1つあるかを計算する.

構想解析:x&(x-1)からxの最後の知見を消去する.ループはx&(x-1)を用いて最後の1位を消去し,合計何回消去したかを計算する.

1.3.整数AをBに変換するには、ビット数を変更する必要があります

構想解析この応用は上の応用の開拓である.整数AをBに変換することを考え、AとBがi(0<=i<32)番目のビットで等しい場合、このBITビットを変更する必要はなく、i番目のビットで等しくない場合、このBITビットを変更する必要がある.だから問題はAとBがどれだけBITビットが異なるかに転化する.連想位置演算には,同じ0,異なる1の異或操作があるため,問題はA異或Bを計算した後のこの数のうち1の個数に変化した.

2.テクニック2バイナリによるサブセット列挙
アプリケーション異なる整数を含む集合を指定し、そのすべてのサブセットを返します.
サンプル
S=[1,2,3]の場合,[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2]]の解がある.
構想
1つの正の整数バイナリで表されるi番目のビットが1であるか0であるかを用いて,集合を表すi番目の数を取るか取らないかを考える.したがって,0から2 n−1までの合計2 n個の整数は,集合の2^nサブセットにちょうど対応する.

S = {1,2,3}
N bit Combination
0 000 {}
1 001 {1}
2 010 {2}
3 011 {1,2}
4 100 {3}
5 101 {1,3}
6 110 {2,3}
7 111 {1,2,3}

解題コード
あとで補足します.
テクニック3.a^b^b=a
3.1.1つの配列を適用すると,1つの数だけ1回出現し,残りは3回出現し,1回出現するものを探し出す.
に質問
Given [1,2,2,1,3,4,3], return 4
問題を解く構想.
1つの数がちょうど1つしか現れず、残りは2回も現れたことがあるので、すべての数を異にすれば、唯一の数を得ることができます.
C言語解題コード

#include
int main()
{
    int a[7]={1,2,2,1,3,4,3};
    int ans=0;
    for(int i=0;i<7;i++){
        ans^=a[i];
    }
    printf("%d
",ans);
}

3.2.二配列を適用すると,1つの数だけ1回出現し,残りは3回出現し,1回出現するものを探し出す.
に質問
Given [1,1,2,3,3,3,2,2,4,1] return 4
問題を解く構想.
数は3回出現するので、すなわち、2ビット毎に1回しか出現しない数がその2ビットで1であれば、この2ビットの全数字における出現回数は3では割り切れない.モード3演算には3つの状態しかない:00,01,10であるため、現在のビット%3を2つのビットで表すことができ、各ビットについて、Two,Oneに現在のビットの状態を表し、Bは入力数字の対応するビットを表し、Two+とOne+は出力状態を表す.

0 0 0 0 0
 0 0 1 0 1
 0 1 0 0 1
 0 1 1 1 0
 1 0 0 1 0
 1 0 1 0 0
 One+ = (One ^ B) & (~Two)
 Two+ = (~One+) & (Two ^ B)

C言語解題コード

#include

void findNum(int *a,int n)
{
    int one=0;
    int two=0;
    int i,j,k;
    for(i=0;i

もう一つの分かりやすい方法

#include

void findNum(int *a,int n)
{
    int ans=0;
    int bits[32]={0};
    for(int i=0;i>j)&1);
        }
    }
    for(int i=0;i<32;i++){
        if(bits[i]%3==1) ans+=1<

3.3.3つの数のグループを適用すると、2つの数だけが1回現れ、残りは2回現れ、1回現れたものを見つける.
に質問
Given [1,2,2,3,4,4,5,3] return 1 and 5
問題を解く構想.
第1題の基本的な考え方があれば,1つの2つの要素がx,yであると仮定してもよいが,最終的にすべての要素が異なる結果はres=x^yである.そしてres!=0であれば、resバイナリ表現のいずれかが1であり、この1つの1がこの2つの数xに対してyが1つの数しかない位置が1であることを見つけることができる.元の配列については,この位置が1であるかどうかによって配列を2つの部分に分けることができる.x,yのうちの1つを求めると,2つを求めることができる.
C言語解題コード

#include

void findNum(int *a,int n)
{
    int ans=0;
    int pos=0;
    int x=0,y=0;
    for(int i=0;i>=1;
    }
    for(int i=0;i>pos)&1){//   pos   
            x^=a[i];
        }
    }
    y=x^ans;
    if(x>y) swap(x,y);//      x,y
    printf("%d %d
",x,y);
}
int main()
{
    int a[8]={1,2,2,3,4,4,5,3};
    findNum(a,8);
}

もう一つの書き方

#include

void findNum(int *a,int n)
{
    int diff=0;
    int x=0,y=0;
    for(int i=0;iy) swap(x,y);
    printf("%d %d
",x,y);
}
int main()
{
    int a[10]={1,2,2,3,4,4,5,3};
    findNum(a,8);
}

参考自大神:微信:ninechapter.