算法积累二(位操作部分) algorithms – bit operation

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 + 24

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 (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; 
    }
  	return c;
}

​

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(补码)