Bitwise operations are the same in other languages, not just JS, so the bitwise operations mentioned in this article are applicable to other languages as well.
Bitwise operations are low-level operations, so they tend to be the fastest (compared to other operations such as addition, subtraction, multiplication and division), and some algorithms can be implemented by virtue of bitwise operations. There are many benefits to using arithmetic properly. Here are a few examples.
1. Use bit-based non-~ to check that the index exists
This is a very common technique, such as determining whether a number is in an array:
// If the url contains? ", followed by an ampersand, or? No.
url += ~url.indexOf("?")?"&" : "?";Copy the codeBecause:
~ 1 = = = 0
-1 in the memory representation of the binary symbol is 1, after the bit is not changed to 0. 0001, the first digit 0 means the sign bit is positive, and if it’s -1, the sign bit is negative 1 means 1000… 0001, this is the original code of -1, and then the sign bit does not move, the rest of the bits are reversed to 1111… 1110, this is the inverse of -1, the inverse plus 1 becomes 1111… 1111, this is the complement of -1, negative numbers are represented in memory using the complement, positive numbers are represented in source code. So the number of machines that are all ones becomes all zeros by transposioning them. All the rest of the numbers are bitwise non-zero, so using this feature can be used to determine indexOf to make the code look cleaner.
2. Use xor to swap two numbers
The most intuitive way to swap two integers is with a temporary variable:
let a = 5,
b = 6;
// Switch the values of a and b
let c = a;
a = b;
b = c;Copy the codeIt is now required that you cannot exchange two integer values using additional variables or content space. This is where bit operations are used. Xor can be used to do this:
let a = 5,
b = 6;
a = a ^ b;
b = a ^ b; // b 等于 5
a = a ^ b; // a 等于 6Copy the codeWhy is that? Very simple, put formula 1 and 2:
a = a ^ b;
b = a ^ b;Copy the codeThis is equivalent to:
b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a;Copy the codeSimilarly, together with formula 3, it can be obtained:
a = (a ^ b) ^ a // By the time we perform formula 3, b has become A, and A is a ^ b of formula 1
= a ^ a ^ b = 0 ^ b = b;Copy the codeWhy is a to the a equal to 0 and b to the b equal to 0? Because that’s what xOR does. The following is an example:
01011010
^ 10010110
-----------
11001100Copy the codeThe xOR operation can be thought of as adding two numbers and carrying them away. 0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0. It’s easy to remember. So a to the a, in all the binary bits, is either equal to 0 or equal to 1, and they all add up to 0, and then it’s equal to 0.
Xor is also often used for encryption.
3. Use bitwise and & to remove the high position
Bitwise and has many functions. One of them is to remove the high level of the operands and keep only the low level of the operands, such as a and b:
let a = 0b01000110; // The decimal value is 70
let b = 0b10000101; // The decimal value is 133Copy the codeNow it is considered that their high position is useless, and only the lower four digits are useful, namely the last four digits. In order to compare the sizes of the last four digits of a and B, we can compare them like this:
a & 0b00001111 < b & 0b00001111 // trueCopy the codeThe first four digits of a and B, 0000, become 0, and the last four digits, 1111, remain the same. The actual effect of this is to have A number where the first bits are used for purposes A and the last bits are used for purposes B, and to get rid of the influence of the first bits on the purposes B, we can add it like this.
Another example is a subnet mask. Suppose I am now a network administrator and I can manage IP addresses from 192.168.1.0 to 192.168.1.255, which is only the last eight bits. The IP addresses are divided into six subnets and distinguished by IP addresses. Since 6 is equal to 110 in binary, the first three bits of the last eight bits represent subnets and the last five bits represent hosts (the total number of hosts ranges from 00001 to 11111, which is a total of 30 hosts). The subnet mask of the current network is 255.255.255.111 00000, that is, 255.255.255.224. Assume that the IP address of a host is 192.168.1.120. To know which subnet it belongs to, use the IP address and subnet mask as follows: 120&224 = 96 = 0B 011 00000, the subnet is 011, that is, subnet 3.
This is an example of keeping the high and removing the low, just the opposite of the above example.
4. Use bitwise and & to judge the flag bit
Now there is a background management system, operation permissions are divided into level 1, level 2 and level 3 administrators, among which level 1 administrator has the highest authority, level 2 and level 3 are lower, some operations only allow level 1 and level 2 administrators to operate, some operations only allow level 1 and level 3 administrators to operate. What kind of data structure would make it easy for a logged-in user to perform an operation?
We use bits to represent the management permissions, level 1 uses bit 3, level 2 uses bit 2, level 3 uses bit 1, that is, level 1 permissions are expressed as 0B100 = 4, level 2 permissions are expressed as 0B010 = 2, level 3 permissions are expressed as 0B001 = 1. If A can only be operated by the first and second levels, then this value is expressed as 6 = 0b110, which is the same as the first level and the following: 6&4 = 0b110&0b100 = 4, the value obtained is not 0, so it is considered to have permission. Similarly, the value of 6&2 = 2 is not 0, and the value of 6&1 = 0, so the level 3 has no permission. Here the flag bit 1 means open and 0 means closed.
The advantage of this is that we can use a number instead of an array to represent the set of permissions for an operation, and it is also very convenient to make permissions judgments.
5. Use the bitwise | tectonic attribute sets
It constructs a permission set of attributes, attribute sets and the examples, such as I mentioned in the Google map development summary “an example of a boundary judgment – to play in the current mouse position up a suspension box, as shown in the diagram below left, but when the mouse is on the side will lead to suspension box is beyond the border, the following figure to the right:
To do this, you need to make a boundary judgment. There are three overruns in total: right, up, and left, and they may overlap. For example, when the mouse is in the upper left corner, both left and top will be overridden. It is necessary to record the exceedance for adjustment. 001 represents the exceedance on the right, 010 represents the exceedance on the top, and 100 represents the exceedance on the left. The calculation code is as follows:
let postFlag = 0;
// The right side is out
if(pos.right < maxLen) posFlag |= 1;
// The above exceeds
if(pos.top < maxLen) posFlag |= 2;
// The left side exceeds
if(pos.left < maxLeftLen) posFlag |= 4;
// Handle the overflow, code omitted
switch(posFlag){
case 1: / / right
case 2: / /
case 3: / / right
case 4: / / left
case 6: / / left
}Copy the codeIf the left and above and beyond, then through calculation or 2 | 4 = 6, 6 = 0 b110. You know what happens when you exceed, which is better than writing two judgments in if.
6. Comprehensive application of bit operation
Here’s an example — addition without the use of addition, subtraction, multiplication and division is often used to test mastery of paraphernial operations. Readers can first try their own analysis and implementation.
You can’t add, subtract, multiply, and divide, which means you have to do it in bits. For example, a = 81 = 0B1010001, b = 53 = 0B0110101. By xOR, we find that xor adds two numbers but cannot carry. By and, we know which bits need to be carried, as shown below:
1010001 ^ 0110101 --------- 1100100 1010001&0110101 --------- 0010001Copy the codeIt shouldn’t be hard to understand why you carry the sum by moving it one bit to the left and adding it to the xOR. To add the two numbers, you can repeat the process: xor, sum, and carry until you don’t need to carry anymore. So it’s not hard to write the following code:
function addByBit(a, b) {
if (b === 0) {
return a;
}
// Do not add the digits
let c = a ^ b;
// The record needs to carry
let d = a & b;
d = d << 1;
// Keep adding until d carries 0
return addByBit(c, d);
}
let ans = addByBit(5.8);
console.log(ans);Copy the codeBitwise operations are often used to generate random numbers and hashes. For example, Chrome hashes strings like this:
uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
running_hash += c;
running_hash += (running_hash << 10);
running_hash ^= (running_hash >> 6);
return running_hash;
}Copy the codeContinuously increments the ASCII value of the current string, using xor, left and right shift.
This article introduces several practical examples of using bit operations, hoping to deepen the understanding of bit operations and help development.