비트 치트 시트(C++)

연산자

&      (and)     - (1&0)  = 0       // 0 when one of them 0
|       (or)     - (1|0)  = 1       // 0 when both 0
^      (xor)     - (1^0)  = 1       // 0 when both same
<< (left shift)  - (1<<n) = 2^n     // Multiply by 2
>> (Right shift) - (1>>n) = 1/(2^n) // divided by 2 

비트의 기초

// 32 bit - 2^32-1 Numbers
// a 1 2 3 4 5 6 b - a:Most significant bit, b:Least significant bit
// Set bit - 1
// Unset bit - 0

//     10011101
//   & 00010000   1 << 4
//  -------------------
//     00010000

토글 비트

void printBinary(int n){
    for(int i=9;i>=0;i--){
        cout<<((n>>i)&1);
    }
    cout<<endl;
}
void solve(){
    int a = 9;
    printBinary(a);
    int i = 3;
    if((a&(1<<i))!=0){
        cout<<"Set bit"<<endl;
        printBinary((a&(~(1<<i))));
        printBinary((a^(1<<i)));
    }else{
        cout<<"Unset bit"<<endl;
        printBinary((a|(1<<i)));
    }
}

비트 카운터 설정

int cnt = 0;
for(int i=20;i>=0;--i){
    cnt+=((a>>i)&1);
}
cout<<cnt;
cout<<__builtin_popcount(a)<<endl;
cout<<__builtin_popcountl((1LL<<50)-1)<<endl;

LSB 제거

printBinary((a&(~((1<<(i+1))-1))));

//    1101011001
//  & 1111100000 - 0000011111 - 0000100000 - 1<<5
// ---------------
//    1101000000

MSB 제거

printBinary((a&(((1<<(i+1))-1))));

//    1101011001
//  & 0000011111 - 0000100000 - 1<<5
// ---------------
//    0000011001

2의 거듭제곱

//   000100000 - Power of two
// & 000011111 - Power fo two-1
// -------------
//   000000000

if(n&(n-1)) cout<<"Not power of two.";
else cout<<"Power of two";

XOR 기본 사항

// 0^0 = 0
// 0^1 = 1
// 1^0 = 1
// 1^1 = 0
// x^x = 0
// x^0 = x

교환

a = a ^ b;
b = a ^ b;
a = a ^ b;