A preliminary study on bit operation
Basis of bitwise operation
Bit operations, is refers to according to the binary arithmetic, a total of six and (&), or (|), the (-), or (^), left (< <) and moves to the right (> >).
| Bit operation | define |
|---|---|
| And (&) operation | Only if both sides are 1, the answer is 1. This can be thought of as a bit operation, for example: x & (1 << n) is the NTH bit of the integer x |
| Or (|) operation | As long as one of the left and right sides is 1, it’s going to be 1. Operations can be thought of as an assignment, such as: x | (1 < < n) is the first n bits assignment for 1 x |
| Take the inverse (~) operation | If you reverse an integer bit, 1 becomes 0,0 becomes 1. On signed integers, the take inverse operation needs to be used with care, because the highest in the signed integer store is the sign bit |
| Xor (^) operation | If it’s the same, it’s 0. If it’s not, it’s 1. |
| Move left (<<) and move right (>>) | To the left is to move all the bits to the left, add 0 back, move n bits to the left is the same thing as multiplying by 2 to the n To the right is to move all the bits to the right, discard the low place, and that’s the same thing as dividing by 2 to the n |
And (&) operation
Only if both sides are 1, the answer is 1
Here the left and right are the left and right of exponents converted to binary, such as 3&5
3 & 5 011 // 3 binary & 101 // 5 binary 001 // the result is 1Copy the codeIf the ampersand is an accessory (such as -3 & -5), it is represented as a binary number in the form of a complement, followed by a bitwise ampersand operation
The complement is just taking the inverse and adding 1
6binary110The not..001.
加1.002.binary2To carry..010.
Copy the code
- Clearing zeros out the second digit of the binary number 11100101 where we are right to left, and the first digit on the right is 0 bits, similar to an array index
1110 0101 & 1111 1011 ------------- 1110 0001 Copy the code - Take some specified bits of a number
1111 1010Take the last four ampersands0000 1111 ------------- 0000 1010 Copy the code
Or (|) operation
As long as one of the left and right sides is 1, it’s going to be 1
0011 0000
| 0000 1111
-------------
0011 1111
Copy the code- Use bitwise operations to convert lowercase letters to uppercase letters and uppercase letters to lowercase letters
| The letter | ASII | binary |
|---|---|---|
| A | 65 | 0100, 0001, |
| a | 97 | 0110, 0001, |
| B | 66 | 0100, 0010, |
| b | 98 | 0110, 0010, |
| Z | 90 | 0101, 1010, |
| z | 122 | 0111, 1010, |
-
Lowercase letters to uppercase letters
First of all, we can see four low uppercase and lowercase letters are the same, as long as fifth as 1 is a capital letter, we consider or (|) operation, according to the characteristics of or (|) operation that we are looking for the number of the lower four should be 0.
Let’s look at the higher four
High four A0100 a 0110 Copy the codeTo this we can see, or (|) operation, when the bit is 1 cannot be changed, this is so, or (|) operation is not desirable.
As with the ampersand operation, the lower four digits of the number we’re looking for should all be 1’s
High four A0100 a 0110 ------ 010? Z 0101 z 0111 ------ 0101 Copy the codeAnd from that we know that the number we’re looking for is 0101, 1111 in binary, 95 in decimal
/ / C language
printf("%c".'z' & 95);
// js
// 'a'.toLocaleUpperCase(); // Uppercase method...
String.fromCharCode(("a".charCodeAt() & 95)); // What a mess...
Copy the code- Uppercase letters to lowercase letters
/ / C language
printf("%c".'Z' | 32);
// js
String.fromCharCode(("A".charCodeAt() | 32));
Copy the codeXor (^) operation
If the left and right sides are the same, it is 0; if the left and right sides are not the same, it is 1
0011 1001
^ 0010 1010
-------------
0001 0011
Copy the code- Inverts a particular bit
Let’s say 0111, 1010, and I want to reverse it in a low four position, that is, 1 becomes 0, 0 becomes 1.
0111 1010
^ 0000 1111
-------------
0111 0101
Copy the code- Swap two values without using temporary variables
a ^= b;
b ^= a;
a ^= b;
Copy the codea = 1binary0001
b = 2binary0010
a ^= b;
0001
^ 0010
------
0011
b ^= a;
0011
^ 0010
------
0001
a ^= b;
0011
^ 0001
------
0010
Copy the codeMove left (<<) and move right (>>)
To the left is to move all the bits to the left, to fill in the zeros, to move n bits to the left is the same thing as multiplying by 2 to the n. To the right is to move all the bits to the right, to get rid of the low place, is the same thing as dividing by 2 to the n
-
X & (1 << n) is the NTH bit of the integer x, which is 1 if the result is greater than 0 and 0 otherwise
-
X | (1 < < n) is the first n bits assignment for 1 x,
5 | 1 = 7
5 | (1 << 1) = 7
0101
| 0010
--------
0111
Copy the codeCompute the sum of two positive integers
- Do not use + and –
0001
+ 0101
--------
0110
Copy the code-
Take the same bit of two numbers and assign 1 to each if both left and right carry 1, otherwise 0
-
Take a
let bitA = a & flag;
let bitB = a & flag;
Copy the code- The assignment
let carry = false;// Whether to carry
if (bitA && bitB) { / / 1
/ / carry
if (carry) { // The low level is carried (this bit has three ones)
let sum |= flag;
}
carry = true;
} else if (bitA || bitB) { // Single is 1
if(! carry) {// There is no carry assignment at the low level
/ / assignment
let sum |= flag;
}
// If the low level is carried (this bit has two ones), it is carried
} else { / / to zero
if (carry) { // The low level is carried
let sum |= flag;
carry = false; }}Copy the codeconst getSum = function (a, b) {
let sum = 0;
let flag = 1;
let carry = false;
while (flag <= a || flag <= b) {
let bitA = a & flag;
let bitB = b & flag;
if (bitA && bitB) {
if (carry) {
sum |= flag;
}
carry = true;
} else if (bitA || bitB) {
if (carry) {
carry = true;
} else{ sum |= flag; }}else {
if (carry) {
sum |= flag;
}
carry = false;
}
flag <<= 1;
}
if (carry) {
sum |= flag;
}
return sum;
};
Copy the code