Hand tearing operation

0x00 — Overview of bit operations

symbol describe algorithm
& Bitwise and, Both ones are 1, so that’s 1
| Bitwise or, One bit is 1, the result is 1
^ Bitwise xor, Identical is 0, dissimilar is 1
~ Inverse by bit, 1 becomes 0,0 becomes 1
<<n Shift to the left Each binary all left n bits, high discard, low fill 0
>>n Moves to the right For unsigned numbers, add 0 to the high level, and add 0 to the signed number. Different compilers handle this differently. Some add sign bits (arithmetic right shift), and some add 0 (logical right shift).

0x01 — bitwise and &

Operation rules: 0&0=0 0&1=0 1&1=1

If both bits are the same, it is 1; otherwise, it is 0

3&5 = 1
3 0000 0011
5 0000 0101
& 0000 0001
Copy the code
use
  • reset

If you want a cell to be zeroed out, that is, if all the bits of the number are zeroed out, place the number bitwise with a number that is zeroed out. The result is 0

  • Takes the specified bit of a number

An 🌰 :

A is equal to 1010, 1110, take the lower four digits of a. All you need to do is find a B and set the lower four bits of B to 1 and the rest to 0, i.e

b= 0000 1111 .

&= 0000 1110. The specified part of A can be obtained. In this process, B is also the so-called mask of A.

  • Judge parity

You just check whether it’s odd or even based on whether it ends at 0 or 1.

Zero is even, one is odd. If (a % 2) == 0

Replace this with if(a&1==0) to see if a is even.

0x02 — bitwise or |

Operation rule: 0 | 0=0 0 | 1=1 1 | 1=1

As long as one of them is 1, the result is 1.

3|5 = 7
3 0000 0011
5 0000 0101
| 0000 0111
Copy the code
use
  • Used to set bit 1 for some bits of a data

An 🌰 :

A = 1010 1110, set the lower four bits of A to 1. All you need to do is find a B and set the lower four bits of B to 1 and the rest to 0, i.e

b= 0000 1111 .

| = 1010 1111. You can get after the bitwise and as a result,

0x03 — xor ^ by bit

Operation rule: 0^0=0 0^1=1 1^0=1 1^1=0

The same bit is 0, and the different bit is 1.

Several properties of xor:

  1. Commutative law

  2. Associative law (a^b)^c == a^b ^c

  3. For any number x, x to the x is equal to 0, x to the 0 is equal to x

  4. Reflexivity: A ^b^b=a^0=a;

use

  • Flip the specified bit

    An 🌰 :

    A = 1010, 1110, flip the lower four digits of A. All you need to do is find a B and set the lower four bits of B to 1 and the rest to 0, i.e

    b= 0000 1111 .

    ^= 1010 0001. The bitwise xor result can be obtained. I flipped the lower four bits of a.

  • Different from or unchanged from 0

     1010 1110
 0000 0000
^1010 1110
   a 3 0000 0011
   b 4 0000 0100
   a^b 0000 0111 a
   
   b 4 0000 0100
   b^a 0000 0111 a
   		 0000 0011 b
Copy the code

  • Switch two numbers

    void swap(int a, int b) {
  if(a!=b) {
    a^=b;
    b^=a;
    a^=b;
  }
}
Copy the code

0x05 — reverse ~ by bit

Operation rule: ~1=0 ~0=1

If the lowest value of a is 0, it can be expressed as a & ~1. The value of ~1 is 1111 1111 1111 1110. Press “and” to calculate the value. The lowest value must be 0. The ~ operator takes precedence over arithmetic, relational, logical, and other operators.

0x06 — Left-shift operator <<

If the lowest value of a is 0, it can be expressed as a & ~1. The value of ~1 is 1111 1111 1111 1110. Press “and” to calculate the value. The lowest value must be 0. The ~ operator takes precedence over arithmetic, relational, logical, and other operators.

0x07 — Right shift operator >>

Definition: all binary bits of a number are moved right several bits, positive number left complement 0, negative number left complement 1, right discard.

For example: a=a>>2 Move the binary bits of A to the right by two bits, adding either 0 or 1, depending on whether the number is positive or negative.

Every time the operand moves one bit to the right, it is equal to dividing the number by 2.

Integrated application of

For example, if you have two variables x and y of type int, divide the sum of x+y by 2, but it is possible that x+y will exceed the maximum representation of int, so the bitwise operation will come in useful.

(x&y)+((x^y)>>1);

For an integer greater than 0, determine if it’s 2 to some power

`((x&(x-1))==0)&&(x! = 0);

Beg absolute value

int abs( int x ) { 
   int y ; 
   y = x >> 31 ; 
   return (x^y)-y ;        //or: (x+y)^y 
}
Copy the code

Modular operation, using bit operation to achieve:

A % of 2 to the n is the same thing as a minus 2 to the n minus 1.

The multiplication operation is realized by bit operation

A times 2 to the n is the same thing as a << n

The division operation becomes a bit operation

A over 2 to the n is the same thing as a>> n

Strives for the opposite

(~x+1)

A % 2 is the same thing as a & 1