What is a bit operation?

So before we look at what a bit operation is, let’s look at what a bit operation is. A bit is the smallest unit of information stored in a computer. In a binary number system, a bit is represented by a 0 or a 1. When we learn the data type of a programming language, we will always tell us that the storage of int needs 4 bytes, ranging from -2 147 483 648 to 2 147 483 647. The value of 1 in int is 0000 0000 0000 0000 0000 0001. So bitwise operations operate directly on the binary bits of an integer in memory.

For convenience, the following study demonstrates the two bytes of int

Conversion from decimal to binary

Positive integers are converted to binary

Conversion of positive integers to binary is usually done by dividing by two and modulating. The following shows how to use this method to find the binaries of 10, 13, and 42.

0000 0000 0000 1010
0000 0000 0000 1101
0000 0000 0010 1010
Mod by two

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1

For example: 10 binary: 10 = 8 + 2:1010 42 binary: 42 = 32 + 8 + 2:101010 13 binary: 13 = 8 + 4 + 1:1101

Negative integers are converted to binary

To compute the binary of a negative integer, first convert the positive integer corresponding to the negative integer to binary, then invert the binary, and then add one to the result. Find the binary of -10:

- 10The binary of theta is evaluated first10The binary0000 0000 0000 1010Take the:1111 1111 1111 0101
加 1:1111 1111 1111 0110
Copy the code

so- 10The binary of1111 1111 1111 0110.Note:The highest bit in binary is zeroThe sign bit0 represents a positive number and 1 represents a negative number, sointThe binary of the largest integer of0111 1111 1111 1111 1111 1111 1111 1111 1111 1111, the value ranges are as follows:

An operation

Bitwise operations operate on bits of integer values. Bitwise operators include the following:

&:Bitwise andThe operator

Returns 1 if the corresponding bit of both integer values is 1, and 0 otherwise. Such as:

10 & 13
10 : 0000 0000 0000 1010
13 : 0000 0000 0000 1101-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- result:0000 0000 0000 1000
Copy the code

|:Bitwise orThe operator

Return 0 if the corresponding bit of both integer values is 0, otherwise return 1(both 0 is 0). Such as:

42 | 13
42 : 0000 0000 0010 1010
13 : 0000 0000 0000 1101-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- result:0000 0000 0010 1111
Copy the code

^:The bitwise exclusive orThe operator

Returns 1 if the corresponding bits of two integer values are not identical, or 0 if they are not. Such as:

42 ^ 13
42 : 0000 0000 0010 1010
13 : 0000 0000 0000 1101-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- result:0000 0000 0010 0111
Copy the code

~:According to the notThe operator

Invert the integer value, 1 becomes 0, 0 becomes 1.

42 : 0000 0000 0010 1010-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -42: 1111 1111 1101 0101
Copy the code

<<:Shift to the leftThe operator

X << yThe integerXTo the leftyposition At the end of filling0. That’s the same thing as X star.

13 << 2
13 : 0000 0000 0000 1101
----------------------------------------
<<2: 0000 0000 0011 0100
13 << 2The result is:52 -----> 13 * (2^2) = 52
Copy the code

>>:Moves to the rightThe operator

X >> yThe integerXTo the rightyposition Fill in the sign bit at the beginning. That’s the same thing as X divided byTake an integer.

13 >> 2
13 : 0000 0000 0000 1101
----------------------------------------
>>2: 0000 0000 0000 0011
13 >> 2The result is:3 -----> 13 / (2^2) = 3 
Copy the code
- 10 >> 2
- 10 : 1111 1111 1111 0110
----------------------------------------
>>2 : 1111 1111 1111 1101
- 10 >> 2The result is:- 3 -----> - 10 / (2^2) = - 3 
Copy the code

Simple application

Judge parity

Since the binary end of an odd number is always 1, we can determine whether an odd number is odd by determining whether there is a 1 at the end of x & 1.

// Take the last bit of binary through: a&1.
#include<stdio.h>
int main(a){
	int a = - 3;
	if(a & 1) {printf("Odd number: %d\n",a);
	}else{
		printf("Even: %d\n",a);
	}
	return 0;
} 
Copy the code

exchange

In swaps, the result of the ^ operator can be interpreted as recording the difference between two numbers. For example, I tell you that there are two different colored balls (red, blue) in a box. When you take out a blue ball with your hand inside, the rest of the ball inside do not have to look, the color is definitely red.

#include<stdio.h>
int main(a){
	int a = 3;
	int b = 2;
	printf("a = %d, b = %d\n",a,b);
	a = a^b;// Tell the difference between a and B, and assign to A.
	b = a^b;// select a from b and assign it to b
	a = a^b;// The value of b is the original number a,a can find the original number B through different records a, and assign the value to A
	printf("a = %d, b = %d\n",a,b);
	return 0;
} 
Copy the code

Take the average of two numbers

Average the two numbers by (x & y) + ((x ^ y) >> 1). Take the common part of the two numbers by (x & y), then add the rest by (x ^ y) and sum by >> 1 over 2. Take a decimal number :(12 + 8) / 2; 12 = 8 + 4, 8 = 8 + 0; So the common part is 8, the rest is (4 + 0)/2 = 2, and the average is 8 + 2 = 10;

#include<stdio.h>
int avarge(int x, int y){
	return (x & y) + ((x ^ y) >> 1);
}
int main(a){
	int a = 6;
	int b = 2;
	printf("A = %d, b = %d, mean: %d\n",a,b,avarge(a,b));
	return 0;
} 
Copy the code

Determine if a number is a power of two

In binary,A power of 2 timesIs an integer that contains only one1, such as:0100.:1000. So, when we get rid of the last digit1When, the result becomes0. throughx & (x - 1)To get rid of the last digit1.

#include<stdio.h>
int main(a){
	int a = 7;
	if (a & (a- 1)) {printf("A = %d is not a power of 2 \n",a);
	} else{
		printf("A = %d is a power of 2 \n",a);
	}
	return 0;
} 
Copy the code

conclusion

This chapter has learned how to convert decimal to binary, bitwise operators, and simple applications of bitwise operations.

Public id: HarLearn