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