An operation
Bitwise operations are always good at dealing with relationships between numbers
The basic and or not are not covered here, but let’s take a look at some clever examples of bit operations:
Gets the destination bit
function getBit(number, bitPosition) {
return (number >> bitPosition) & 1
}
Copy the code
This method moves the target bit to the right, the 0th position in the bit array. The ADD operation is then performed on that number with a binary number of the form 0001. This clears up all bits of data except the target bit. If the destination bit is 1, the result is 1; otherwise, the result is 0
explain
Suppose we want to get the third bit of the number 23, so we move 2 bits to the right
So number=23, bitPosition=2
/ / so:
23 >> 2 & 1
// This is equivalent to:
(10111) ₂ > >2 & 1
// This is equivalent to:
(101) ₂ &1
// bit result:
1
Copy the code
Set the target bit to 1
function setBit(number,bitPosition) {
return (1 << bitPosition) && number
}
Copy the code
This method moves 1 to the left by the bitPosition, producing a binary value of the form 00100. We then take that value and the target number and perform the OR operation to set the target bit to bit 1 without affecting the other bits
explain
Assume number=23 and bitPosition=3
1 << 3 & 23
// This is equivalent to:
(1000) ₂ < <3 & (10111) ₂// This is equivalent to:
(1000) ₂ & (10111) ₂// bit result:
(11111) ₂// Decimal:
31
Copy the code
Set the target bit to 0
function clearBit() {
return~ (1 << bitPosition) & number
}
Copy the code
This method moves 1 to the left by the bitPosition, producing a binary value of the form 00100. Then invert each digit to get a binary value of the form 11011. Then ADD with the target value to clear the value of the target bit
~ Reverse operation
The ~ operation reverses binary bits bit by bit, including sign bits
Set the target to 0 or 1
function updateBit(number,bitPosition,bitValue) {
(bitValue <<< bitPosition) | // Set the target value
(number & ~(1 << bitPosition)) // Clear the target value
}
Copy the code
The above method combines ClearBit and SetBit
Why clear the target value? Can’t you just set it?
The answer is no, because we do not know whether the target bit (let’s say X) is 1 or 0. Direct calculation will lead to uncertain results, such as the following:
X | 0 = 0 //(X = 0)
X | 0 = 1 //(X = 1)
X | 1 = 0 //(X = 1)
X | 1 = 1 //(X = 1)
Copy the code
And we don’t care if X is 0 or 1, so if we set X to zero, we’ll get the exact right answer
X | 0 = 0 //(X = 0)
X | 1 = 1 //(X = 0)
Copy the code
Tests the parity of a certain number
function isOdd(number) {
return number & 1
}
Copy the code
The last digit of an odd number must be 1
Multiply the number itself by 2
function mutiplyByTwo(number) {
return number << 1
}
Copy the code
This method moves the original number one to the left. So all the bits are going to be multiplied by 2, so the number itself is going to be multiplied by 2
The number itself goes into 2
function divideByTwo(number) {
return number >> 1
}
Copy the code
And similarly, if we move to the right, we divide by 2
Change the number symbol
function switchSign(number) {
return ~number + 1;
}
Copy the code
This method turns positive numbers into negative numbers and vice versa. To do this, it uses the method of “binary complement”, which takes all the bits and adds one
Computes the significant digit of a number
function bitLength(number) {
let bitsCounter = 0;
while ((1 << bitsCounter) <= number) {
bitsCounter += 1;
}
return bitsCounter;
}
Copy the code
For example, number = 5, which is (0101)₂, has three significant bits
Simulation steps:
- 1 is less than or equal to 5 and the count is 1
- 2 is less than or equal to 5, and the count is 2
- 4 is less than or equal to 5, and the count is 3
- Stop counting if 8 is greater than 5
Determine if a number can be expressed as a power of two
function isPowerOfTwo(number) {
return (number & (number - 1= = =))0;
}
Copy the code
Let’s think about it for a moment. Common powers of 2 are: 2, 4, 8, 16
Take 16 as an example:
16&15 is equivalent to (1000)₂ & (0111)₂, and the result is of course 0
What’s the use of bit operations?
While bitwise operations that manipulate numbers by moving them left and right are fascinating, you might be wondering, can I do this without bitwise operations? So why do we need bitwise operations?
In fact, it is not, the role of bit operation is often reflected in the algorithm
Take this title from LeetCode: leetcode-cn.com/problems/si…
Obviously, since the same number is xor must be 0, the remaining number must remain. According to the commutative nature of xor, we do not care about the order of the digits, but xor or each digit can be:
var singleNumber = function(nums) {
let s = 0
for(let num of nums) {
s ^= num
}
return s
};
Copy the code
Thus, it is necessary to master bit operations
Let us know your thoughts in the comments below