算法积累二(位操作部分) Algorithms - Bit Operation

Posted on |

算法积累二(位操作部分) Algorithms - Bit Operation

  1. Achieve Multiplication without *

    Simulate multiplication with bit operation. Actually each int could be represent by binary format, like 10 == 1010, 4 == 0100, so it can use distributive law of multiplication. 10 = 8 + 2, so 10 4 = (8+2) 4 = 2^34 + 2\4

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int multiply(int a, int b){
      	bool sign = true;
      	if(a<0 && b < 0) {
            a = -a;
          	b = -b;
        }
      	else if(a < 0){
            sign = false;
          	a = -a;
        }
      	else if(b < 0){
            sign = false;
          	b = -b;
        }
        int c = 0;
      	while(b > 0){
            if((b & 1) == 1){
                c += a;
            }
          	b >> 1;
          	a << 1; // a * 2
        }
      	return c;
    }

    ​

  2. Some common bit operations

    1. Setting a bit

      1
      number |= 1<<x;

    2. Clearing a bit

      1
      number &= ~(1<<x);

    3. Toggling a bit

      1
      number ^= 1<<x;

    4. Checking a bit

      1
      bit = (number >> x) & 1;

    5. Changing the nth bit to X(0 or 1)

      1
      number ^= (-x ^ number) & (1 << n);

      In computer, the negativative number is represented by complemental code(补码)