Bit Manipulation

Posted on Edited on

Operator

&

& 1 0
1 1 0
0 0 0

|

\ 1 0
1 1 1
0 1 0

^

^ 1 0
1 0 1
0 1 0

~

~ 1 0 0 1 1
=> 0 1 1 0 0

<<

1
2
3
4
5
int a = 8;
a << 3;

before：0000 0000 0000 0000 0000 0000 0000 1000
after：0000 0000 0000 0000 0000 0000 0100 0000

>>

1
2
3
4
5
6
7
8
9
unsigned int a = 8;
a >> 3;
before：0000 0000 0000 0000 0000 0000 0000 1000
after：0000 0000 0000 0000 0000 0000 0000 0001
​
int a = -8;
a >> 3;
before：1111 1111 1111 1111 1111 1111 1111 1000
after：1111 1111 1111 1111 1111 1111 1111 1111

Common Problem

  1. Implement division

    1
    2
    3
    int a = 2;
    a >> 1; ---> 1
    a << 1; ---> 4

  2. Swap two digits

    1
    2
    3
    4
    5
    void swap(int &a, int &b) {
         a ^= b;
         b ^= a;
         a ^= b;
     }

    Explaination:
    Step 1：a ^= b —-> a = (a^b);

    Step 2：b ^= a —-> b = b\^(a^b) —-> b = (b\^b)^a = a

    Step 3：a ^= b —-> a = (a\^b)^a = (a\^a)^b = b

  3. Odd or Even
    If the last digit is 0, then even. Otherwise, odd

    1
    2
    3
    if(0 == (a & 1)) {
        even
     }

  4. Change the sign

    1
    2
    3
    int reversal(int a) {
         return ~a + 1;
     }

  5. Detect opposite sign

    1
    2
    3
    4
    int oppositeSigns(int x, int y) {
       // -1 if opposite, 0 if not
       return ((x ^ y) >> 31); 
    }
    1
    2
    3
    4
    int oppositeSigns(int x, int y) {
       // 1 if opposite, 0 if not
       return ((x ^ y) >>> 31); 
    }