• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

An overview of the

All numbers in a computer program are stored in binary form. Bitwise operations are operations performed directly on integers in binary. As a programmer, it is very important to master the basic use of bit operations, and for algorithm programmers, the flexible use of bit operations can be more flexible and efficient to solve many problems.

What are the bit operations

symbol describe algorithm
& with It’s going to be 1 for both, 0 for everything else
| or It’s 0 if it’s both 0 and 1 if it’s all else
^ Exclusive or Equal to 0, different to 1
~ The not 0 becomes 1,1 becomes 0
<< Shift to the left Everybody move left, high discard, low fill 0
>> Moves to the right If you move to the right, the low position is discarded. If the number is the regular high position, 0 is added. Vice fill 1
>>> Unsigned shift to the right Also known as logical right shift, regardless of positive or negative, high order complement 0

Operator logic

Press and (&)

The two numbers involved in the operation are and in binary.

0&0=0
0&1=0
1&1=1
Copy the code

USES:

reset

Any sum with 0 is 0.

Take to specify a

For example, to take the lower four bits of a number, you simply run and with (0000 1111). The result is the lower four bits of the number.

Odd-even judgement

If the binary ends in 0, it’s even, and if it ends in 1, it’s odd. So (x&1)==0.

Bitwise or (|)

The two numbers involved in the operation are either operated on in binary.

0|0=0
0|1=1
1|1=1
Copy the code

USES:

Set one to 1

Such as X = 0101, needs to be set to 1, 2 results into 0111, simply and or operation (0010), 0101 | 0010 = 0111.

Bitwise xor (^)

The two numbers involved in the operation are xOR in binary.

0^0=0
0^1=1
1^1=0
Copy the code

USES:

Flip the specified bit

To flip the lower 4 bits of X=0101 1010 to 0101, simply perform an xor with Y=0000 1111, X^Y=0101 0101.

Interchange two values

If X=0101 and Y=0100, the values of X and Y need to be swapped.

x ^= y; // x= 0101 ^ 0100 = 0001
y ^= x; // y = 0100 ^ 0001 = 0101
x ^= y; // x = 0001 ^ 0101 = 0100
Copy the code

Reverse by bit (~)

The values of 1 data in the operation change from 0 to 1, and 1 to 0.

~0101=1010
Copy the code

USES:

Take the inverse operation and used to quickly obtain a specific value, such as to obtain a minimum of 0 and other bits are 1, then take the inverse of 1, ~1.

Left-shift operator (<<)

One data involved in the operation moves to the left, discards the high one, and adds 0 to the low one.

0101 << 1 = 1010
Copy the code

If the highest left shift is not equal to 1, it is equivalent to multiplying by 2.

Right shift operator (>>)

1 data involved in the operation moves right, if the number is regular high fill 0, otherwise fill 1, low discard.

0101 >> 1 = 0010
Copy the code

Shifting something to the right is the same thing as dividing by 2.

Unsigned right-shift operator (>>>)

Also known as logical right shift, regardless of positive or negative, high order complement 0.

0101>>>1=0010
Copy the code

If negative 5 is shifted to the right, the result is as follows. (binary representation of 11111111111111111111111111111011-5)

11111111111111111111111111111011>>>1=01111111111111111111111111111101
Copy the code

Note: The binary representation of negative numbers is the complement.

What SAO operation

Skills a

X & x minus 1 is used to cancel out the 1 in the last digit of x

Application: Check whether the integer x is a power of 2

A power of 2 satisfies the following conditions:

  1. Greater than zero
  2. There’s only one place that’s a 1

So x minus x minus 1 is equal to 0, which means x is a power of 2.

Technique 2

a ^ b ^ b = a

Find the number in a data set where only one number appears once and all other numbers appear twice.

You just xor all the data and you get this number.

Find two numbers in a data set that appear only once and all the other numbers appear twice.

Thinking: assuming that the two Numbers is the X, Y, as a result of all digital vision or X ^ Y, because the logic of an exclusive or operation is the same as 0, different is 1, is to find out the results of the binary is equal to 1, then all Numbers is divided into two parts according to whether the bit is 1, the X and Y will be separated, then respectively made exclusive or operation and the result is the X and Y.

summary

Bit operation often appears in the face of Internet companies, and is also frequently used in various algorithm problems. I hope this article can give you a preliminary understanding of bit operation. If it helps, just give it a thumbs up and go