The origin of this topic was the “left-pad” incident in the NPM community in March 2016, and shortly after that someone in the community released a remedy, the now-available Left-pad library.
The original code for this library looks like this.
module.exports = leftpad;
function leftpad (str, len, ch) {
str = String(str);
var i = - 1;
if(! ch && ch ! = =0) ch = ' ';
len = len - str.length;
while (++i < len) {
str = ch + str;
}
return str;
}Copy the codeWhen I first saw this code, I didn’t see anything wrong with it and thought it was clear. When @Left Ear Mouse pointed out that the code could be written more efficiently, he posted his own version and gave left-pad a PR, with the following code:
module.exports = leftpad;
function leftpad (str, len, ch) {
//convert the `str` to String
str = str +' ';
//needn't to pad
len = len - str.length;
if (len <= 0) return str;
//convert the `ch` to String
if(! ch && ch ! = =0) ch = ' ';
ch = ch + ' ';
var pad = ' ';
while (true) {
if (len & 1) pad += ch;
len >>= 1;
if (len) ch += ch;
else break;
}
return pad + str;
}Copy the codeWhen I saw the ampersand and >> operators in this code, I was a little confused. I only knew that this was the ‘bitwise and’ and ‘right shift’ operations in bitwise operations, but I had no idea why it was efficient to write this way. So I want to understand the essence of bit operation and use scenarios.
Before we look at bitwise operations, we must first understand what source code, inverse code and complement code are, and the conversion between binary and decimal.
Source, complement and inverse
The original code
In a computer, a number in binary form, where the first digit holds the symbol and the positive number is 0 and the negative number is 1. Source code is the binary value of the symbol in the first digit. For example, the original code of 2 is 00000010 and that of -2 is 10000010.
Radix-minus-one complement
The inverse of a positive number is itself. The inverse of a negative number is based on its original code, the sign bit is unchanged, the other bits are reversed, that is, 0 becomes 1,1 becomes 0.
[+3] = [00000011Original = []00000011] the [- 3] = [10000011Original = []11111100] theCopy the codeIt can be seen that if an inverse code represents a negative number, its value cannot be seen intuitively. It is usually converted to the original code and then calculated.
complement
The complement of a positive number is itself. The complement of a negative number is based on its original code, with the same sign bits, the other bits reversed, and finally +1. (that is, the complement of a negative number is +1 on the basis of its inverse).
[+3] = [00000011Original = []00000011Against] = [00000011Fill] [- 3] = [10000011Original = []11111100Against] = [11111101] to fillCopy the codeIt can be seen that for negative numbers, the expression way of complement code also makes it difficult for people to see its value intuitively, and it usually needs to be converted to the original code before calculation.
The conversion of binary to decimal
The difference between binary and decimal is that numbers are computed in increments. Binary is one digit in every two, and decimal is what we call 0-9 is one digit in every ten
The decimal conversion of positive integers to binary
The decimal conversion of a positive integer to binary is done by dividing a decimal number by 2, dividing the resulting quotient by 2, and so on until the quotient is equal to 1 or 0. The remainder of the reverse division is the result of the binary conversion.
For example, to convert 52 to a binary number, the calculation process is shown as follows:
The remainder of 52 divided by 2 is 0, 0, 1, 0, 1, 1, in reverse order, so the binary number corresponding to 52 is 110100.
The decimal conversion of negative integers to binary
The decimal conversion of a negative integer to binary means that the positive integer corresponding to the negative integer is first converted to binary, then “invert” it, and then invert the result +1. That is, negative integers are stored as their binary complement. As for why negative numbers should be stored in the form of binary complement, please refer to an article by Ruan Yifeng “on the complement of 2”. For example, the source code of -52 is 10110100, its inverse code is 11001011, and its complement code is 11001100. So -52, when converted to binary, is 11001100.
Decimal decimal to binary
The method of converting decimal from decimal to binary is “integer by 2”. The integer part and decimal part obtained by multiplying decimal by 2 are the corresponding binary number, and then multiplied by 2 (the new decimal part is obtained by multiplying decimal before), and then the integer and decimal part are obtained. This is repeated until the decimal part is zero or precision is achieved. The first gain is the highest, and the last gain is the lowest.
Such as:0.25The binary0.25 * 2 = 0.5Integer is0
0.5 * 2 = 1.0Integer is1
即0.25The binary of0.01(The first win is the highest, the last win is the lowest)0.8125The binary0.8125 * 2=1.625Integer is1
0.625 * 2=1.25Integer is1
0.25 * 2 = 0.5Integer is0
0.5 * 2 = 1.0Integer is1
即0.8125The binary of0.1101Copy the codeBinary to decimal
Starting from the last digit, the list is 0, 1, 2… Bits, the NTH digit (0 or 1) multiplied by 2 to the n, add up the resulting decimal number.
For example, if the binary number is 110, the process for converting it to decimal is as follows
The units digit 0 multiplied by 2º : 0 × 2º = 0
Ten digits 1 multiplied by 2¹ : 1 × 2¹ = 2
Hundreds multiplied by 2² : 1 × 2² = 4
Add up the results: 0+2+4=6
So the decimal value of binary 110 is 6.
Decimals and binaries multiply the number by the negative power of two and add.
Bit operations in JavaScript
Bitwise operators in ECMAScript convert their operands to signed 32-bit integers in complement form. Here’s how bitwise operations are performed in the ECMAScript specification:
The production A : A @ B, where @ is one of the bitwise operators in the productions above, is evaluated as follows:
1. Let lref be the result of evaluating A.
2. Let lval be GetValue(lref).
3. ReturnIfAbrupt(lval).
4. Let rref be the result of evaluating B.
5. Let rval be GetValue(rref).
6. ReturnIfAbrupt(rval).
7. Let lnum be ToInt32(lval).
8. ReturnIfAbrupt(lnum).
9. Let rnum be ToInt32(rval).
10. ReturnIfAbrupt(rnum).
11. Return the result of applying the bitwise operator @ to lnum and rnum. The result is a signed 32 bit integer.Copy the codeNote that in steps 7 and 9, according to the ES standard, integers larger than 32 bits are truncated and decimal parts are discarded. So it can be known that in JS, when there is an operand greater than or equal to 2³² in the bit operation, unexpected results will occur.
In JavaScript bit operations are: & (bitwise and), | (bitwise or), ~ (against), ^ (the bitwise xor), < < (left), > > (signed moves to the right), and > > > (unsigned moves to the right).
& click with
Performs an AND operation on each bit. A & b is only 1 if both a and B are 1. For example: 9(Base 10) &14 (base 10) = 1001(base2) &1110 (base2) = 1000(Base 2) = 8(base 10)
Since a&b is equal to 1 only if both a and b are 1, the bitwise and operation of any value x and 0 (every bit of binary is 0) results in 0. Bitwise and operation of any number x with -1 (each bit of binary is 1) results in x. With the characteristics of & operation, we can simply judge the odd and even numbers by the formula:
(n & 1) = = =0 //true is even, false is odd.Copy the codeSince only the last bit of binary 1 is 1 and the rest bits are 0, the essence of its parity judgment is to determine whether the last bit of binary number is 0 or 1. Odd binary ends with 1 and even binary ends with 0.
X &-1=x when x is an integer, so x&-1=== math.floor (x) when x is a decimal.
| or by location
Performs an OR operation on each bit. If a or b is 1, a | b result is 1. For example: 9 (base 10) | 14 (base 10) = 1001 (base2) | 1110 (base 2) = 1111 (base 2) = 15 (base 10)
As long as one is 1 a or b, a | b is equal to 1, so any numerical x and 1 (binary each are 1) the bitwise and operator, the result is 1. Bitwise and operation of any number x with 0 (each bit of binary is 0) results in x.
Also, bitwise or can do the whole operation down, because when you have x | 0 = x x as an integer, so when x for decimal when x | 0 = = = Math. The floor (x).
To take the
Performs a NOT operation on each bit. The result of ~a is the inversion of A.
9 (base 10) = 00000000000000000000000000001001 (base 2) -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -9 (base 10) = 11111111111111111111111111110110 (base 2) = - 10 (base 10)Copy the codeThe rule for converting negative numbers from binary to decimal is that the sign bit remains the same, and the other bits are inverted and incremented by 1.
The bitwise nonoperation on any number x results in -(x + 1). ~ ~ = = = x x.
Similarly, the inverse can be rounded down, because ~~x===x when x is an integer, so ~~x=== math.floor (x) when x is a decimal.
^ Bitwise xOR
An XOR operation is performed on each pair of bits. When a and B are different, a to the b is equal to 1. For example: 9(base 10) ^ 14(base 10) = 1001(base2) ^ 1110(base 2) = 0111(base 2) = 7(base 10)
The xor operation of any number x with 0 results in x. Xor of any number x with -1 yields ~x, that is, x^-1=~x. Similarly, bitwise xor can also be used to round down, because (x^0)===x when x is an integer, so (x^0)=== math.floor (x) when x is a decimal.
<< left shift operation
It moves all the digits of a number to the left by a specified amount, discarding the left bits and replacing the right with zeros. For example, moving the number 2 (equal to 10 in binary) five bits to the left gives 64 (equal to 1000000 in binary) :
var iOld = 2; // is binary 10
var iNew = iOld << 5; // Equal to binary 1000000 decimal 64Copy the codeBecause the process of binary converted to decimal 10 to 1 + 0 x 2 x 2 creates DHS, 2 in the operation number corresponding to the index and location, when left five becomes 1 x 2 creates ⁺ ⁵ + 0 x 2 DHS ⁺ ⁵ = creates 1 x 2 x 2 ⁵ + 0 x 2 DHS x 2 ⁵ = (1 + 0 x 2 x 2 creates DHS) x 2 ⁵. So you can see that when you move 2 five places to the left it becomes 2 times 2⁵ is 64. So we have a number that we shift to the left n is equal to 2 to the n. X < < n = = = x * 2 ⁿ. Similarly, the left shift can be rounded down, because when x is an integer (x<<0)===x, so when x is a decimal (x<<0)=== math.floor (x).
>> There is a sign shift operation
It moves all the digits of a 32-bit number to the right as a whole, while preserving the number’s sign (plus or minus). The signed right shift operator is exactly the opposite of the left shift operator. For example, if you move 64 five places to the right, it becomes 2. Because we have the sign shift right operator as opposed to the left shift operator, so we have a number that moves to the left n is equal to n divided by 2 to the n. X < < n = = = x / 2 ⁿ. Similarly, a signed shift to the right can also do a round down, because when x is an integer (x>>0)===x, so when x is a decimal (x>>0)=== math.floor (x).
>>> Unsigned right shift operation
It shifts all of the unsigned 32 digits to the right as a whole. For positive numbers, the unsigned right shift results in the same result as the signed right shift, while negative numbers are treated as positive numbers.
9 - (base 10) :11111111111111111111111111110111 (base 2) -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --9 - >>> 2 (base 10) :00111111111111111111111111111101 (base 2) = 1073741821 (base 10)Copy the codeAccording to the characteristic that the unsigned right shift of positive numbers is the same as the signed right shift operation, while the unsigned right shift of negative numbers is definitely non-negative, it can be used to judge the positive and negative numbers, as follows:
function isPos(n) {
return (n === (n >>> 0))?true : false;
}
isPos(- 1); // false
isPos(1); // trueCopy the codeconclusion
According to the JS bit operation, the following information can be obtained: 1, all the bit operation can take the base of the decimal. (n & 1) === 0 //true = even, false = odd To judge even and odd. Use x&-1=== math.floor (x) to take the bottom. 3, for a bitwise or |, can use x | 0 = = = Math. The floor (x) to the bottom. 4, ~~x=== math.floor (x). (x^0)=== math.floor (x); 4. For the left shift operation <<, x<
>0=== math.floor (x) to take the bottom down. (n === (n >>> 0)) true : false; To determine whether the numbers are positive or negative, use x>>>0=== math.floor (x).
It is more efficient to use shift operation instead of ordinary arithmetic. Shift operations translate into machine code with a shorter length, faster execution, and less hardware overhead.
Bit operations from left-pad to JS