Originally published in “The application of bitwise operations”. If you find something, please give it a thumbs up
Basic introduction
As a big category of algorithm questions, bit operation related topics often appear in the interview/pen questions of major companies, the following first talk about the basic principle of bit operation.
Bit operation allows the computer to directly calculate each bit, and the efficiency will be very high.
In JS, the bit operation will calculate the operand as a 32-bit binary string. If the binary string exceeds 32 bits, only the last 32 bits will be reserved for calculation, for example:
11100110111110100000000000000110000000000001 # input binary string
10100000000000000110000000000001 # The actual binary string used
Copy the codeIn JS, there are seven types of bitwise operators:
- Bitwise and (a & b) : In the bitwise representation of a and b, return 1 if each corresponding bit is 1, otherwise return 0
# 15&9 -> 90000 0000 0000 0000 0000 0000 0000 0000 0000 1001 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 1001Copy the code- Bitwise or (a | b) : in a, b a said, each of the corresponding position, as long as there is a 1 is returned 1, otherwise it returns 0
# 15 | 9 - > 150000 0000 0000 0000 0000 0000 0000 1111 | 0000 0000 0000 0000 0000 0000 0000 1001 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 1111Copy the code- Bitwise xor (a ^ b) : in the bit representation of a and b, 1 is returned if the two bits are different, and 0 is returned if the two bits are the same
# 15 ^ 9 -> 60000 0000 0000 0000 0000 0000 0000 1111 | 0000 0000 0000 0000 0000 0000 0000 1001 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 0110Copy the code- Bitwise non-(~a) : reverses the operand’s bits, that is, each 0 becomes 1, and 1 becomes 0
# ~ 15 - > - 161111 ~ 0000, 0000, 0000, 0000, 0000, 0000, 0000 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 1111, 1111, 1111, 1111, 1111, 1111, 1111 0000Copy the code- Left shift (a << b) : The binary string of A is moved b bits to the left and 0 bits to the right
# 9 << 2 -> 36
<< 0000, 0000,, 0000, 0000, 0000, 0000, 0000, 1001 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0010 0100Copy the code- Signed right shift (A >> B) : The binary representation of A is moved b bits to the right, the bits removed to the right are discarded, and the leftmost bits are copied to fill the left. This right shift preserves the original sign of a number by preserving the leftmost binary bit
# 9 >> 2 -> 2> > 0000 0000 0000 0000 0000 0000 0000 1001 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000, 0000, 0000, 0000, 0000, 0000, 0010 0010# -9 >> 2 -> 3> > 1111 1111 1111 1111 1111 1111 1111 0111 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 1111, 1111, 1111, 1111, 1111, 1111, 1111 1101Copy the code- Unsigned right shift (A >>> B) : Moves the binary representation of A to the right by b bits, discarding the bits moved to the right and padding all the left bits with zeros. This shift to the right is due to the fact that the left side is directly supplemented with 0, so the resulting number must be non-negative
# 19 >>> 2 -> 4> > > 0000 0000 0000 0000 0000 0000 0001 0011 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000, 0000, 0000, 0000, 0000, 0000, 0010 0010# -19 >>> 2 -> 1073741819> > > 1111 1111 1111 1111 1111 1111 1110 1101 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0011, 1111, 1111, 1111, 1111, 1111, 1111 0011Copy the codeCommon properties
In algorithmic problems solved using bitwise computing techniques, there are the following common properties:
- Operation between A and itself
a & a = a
a | a = a
a ^ a = 0
Copy the code- Operation between a and 0
a & 0 = 0
a | 0 = a
a ^ 0 = a
Copy the code- Calculation by bitwise and, bitwise or reduction
a | ( a & b ) = a
a & ( a | b ) = a
Copy the code- Exchange variable values by xor
a ^= b
b ^= a
a ^= b
Copy the code- Determine odd and even (extract the last bit by & 1 to achieve modulo 2 effect)
# Bit operation efficiency is higher
a & 1 === a % 2
Copy the code- Compare two values for equality (a ^ a === 0)
a ^ b === 0
Copy the code- Set the I + 1 bit to 1
a |= 1 << i
Copy the code- Set the I + 1 binary bit to 0
a &= ~(1 << i)
Copy the code- Retrieves the value of the I + 1 binary bit
a & (1 << i)
Copy the code- At the I + 1 bit of A, insert the corresponding bit of B
a |= 1 << i
a & (b & 1 << i)
Copy the code- Deletes the position in the binary sequence where the last value is 1
a &= (a - 1)
Copy the code- Compute the negative of A
-a === ~a + 1
Copy the code- Leave a in the last 1 in the binary
a &= (-a)
Copy the code- Generates a number with all 1 bits
~ 0Copy the code- Retain the last i-1 bit in the a binary sequence and complement the remaining zeros
a & ((1 << i) - 1)
Copy the code- Sets all the last i-1 bits in the a binary sequence to 0
a & ~((1 << i) - 1)
Copy the code- Determines whether the highest bit of the binary sequence of A is 1
a < 0 # the highest digit 1 must be negative
Copy the code- In a binary sequence, retain only the highest bit of 1, set the rest to 0, and output that number
a = a | (a >> 1)
a = a | (a >> 2)
a = a | (a >> 4)
a = a | (a >> 8)
a = a | (a >> 16)
return (a + 1) >> 1
Copy the codeNow, let’s take a look at some simple to medium problems to see how clever bit arithmetic can be.
The title
78 – a subset
Leetcode-cn.com/problems/su… You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array. The solution set cannot contain duplicate subsets. You can return the solution set in any order. Example 1: Input: nums = [1,2,3] Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] from the bit operations to think, if use 0 and 1 mark whether there is a number in the subset, this column, The input [1,2,3] in the example produces the relationship between the subset and the 0/1 sequence shown in the table below, so we can directly traverse the 0/1 sequence to construct the data for each subset.
| 0/1 of the sequence | A subset of | The binary number corresponding to the 0/1 sequence |
|---|---|---|
| 000 | {} | 0 |
| 001 | {3} | 1 |
| 010 | {2} | 2 |
| 011 | {2, 3} | 3 |
| 100 | {1} | 4 |
| 101 | {1, 3} | 5 |
| 110 | {1, 2} | 6 |
| 111 | {1, 2, 3} | 7 |
The code can be implemented by 1 << nums.length to obtain the total number of subsets; Property 9 can be used to extract the values of the corresponding binary bits to construct the concrete structure of the subset. The specific code is as follows:
/ * * *@param {number[]} nums
* @return {number[][]}* /
var subsets = function(nums) {
var res = [], len = nums.length
for (var i = 0; i < (1 << len); i++) {
var currSubset = []
for (var j = 0; j <= len; j++) {
if (i & (1 << j)) currSubset.push(nums[j])
}
res.push(currSubset)
}
return res
};
Copy the codeComplexity analysis: the time complexity is O(n2n))O(n2^n))O(n2n)), the total number of subsets is 1 << n that is, 2n2^n2n, so O(2n)O(2^n)O(2n). When constructing each subset, we need to traverse the original array once, so O(n)O(n)O(n) O(n)O(n). The space complexity is O(n)O(n)O(n), and only temporary arrays used when constructing subsets require the overhead of extra space.
136 – A number that appears only once
Leetcode-cn.com/problems/si… Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once. Note: Your algorithm should have linear time complexity. Can you do it without using extra space? Example 1: input: [2, 2, 1] output: 1 example 2: input:,1,2,1,2 [4] output: 4
From the aspect of bit operation, we can find properties 1 and 2, two equal numbers are different or then 0, and a number is equal to itself. Then, after all elements in the array are different or, all the numbers that appear twice will be removed, leaving only the numbers that appear once, the code is as follows:
/ * * *@param {number[]} nums
* @return {number}* /
var singleNumber = function(nums) {
var res = 0
for (var i = 0; i < nums.length; i++) {
res ^= nums[i]
}
return res
};
Copy the codeComplexity analysis: The time complexity is O(n)O(n)O(n), because there is only one iteration of the number group operation. The space complexity is O(1)O(1)O(1) and there is no extra space overhead.
169 – Most elements
Leetcode-cn.com/problems/ma… Given an array of size N, find most of the elements. Most elements are those that occur more than ⌊ n/2 ⌋ in the array. You can assume that the array is non-empty and that a given array always has most elements. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1, 2,2] Output: 2
Dry requirements of most elements, occurrences is greater than n / 2, starting from an operation can be concluded that thinking if each number with 32-bit binary sequence list, to statistics every bit is 0 or 1 more much, most of each element is made of binary sequence, can form the most element numerical finally. The code is as follows:
/ * * *@param {number[]} nums
* @return {number}* /
var majorityElement = function(nums) {
var res = 0, len = nums.length
for (var i = 0; i < 32; i++) {
var ones = 0, zero = 0
for (var j = 0; j < len; j++) {
if (ones > len / 2 || zero > len / 2) {
break
}
if ((nums[j] & (1 << i)) === 0) {
zero++
} else {
ones++
}
}
if (ones > zero) res |= 1 << i
}
return res
};
Copy the codeComplexity analysis: the time complexity is O(n)O(n)O(n), enumerating all bits (32 bits) on the binary sequence once, traversing the entire array once. The space complexity is O(1)O(1)O(1) and there is no extra space overhead.
342 minus 4
Leetcode-cn.com/problems/po… Given an integer, write a function to determine whether it is a power of 4. If so, return true; Otherwise, return false. The integer n is a power of 4. There exists an integer x such that n == 4 ^ x. Example 1: Input: n = 16 Output: true Example 2: input: n = 5 Output: false Example 3: input: n = 1 Output: true
Spreading out the 32 bits, a power of four means that there is a unique 1 in the odd position of the sequence.
0000 0000 0000 0000 0000 0001# 10000 0000 0000 0000 0100# 4
0000 0000 0000 0000 0000 0000 0001 0000 # 160000 0000 0000 0000 0100 0000# 64
Copy the codeTherefore, the property 11 can be used to determine whether there is a unique 1 in the binary sequence of numbers according to whether the result is 0 after the elimination of the last 1. You can also count the initial position of 1 by using the >>> right shift operator in the loop until the number reaches 0. So the code looks like this:
/ * * *@param {number} n
* @return {boolean}* /
var isPowerOfFour = function(n) {
// is there a unique 1
var onlyOne = (n & (n - 1= = =))0
// find 1
var pos = 0, temp = n
while(temp ! = =0) {
temp >>>= 1
pos++
}
// If there is a unique 1 and 1 is odd, it is considered to be a power of 4
return onlyOne && ((pos & 1)! = =0)};Copy the codeComplexity analysis: the time complexity is O(1)O(1)O(1), and the only cycle in the solution is moving on the binary sequence. When the number itself is 0, the original position of the unique 1 can be obtained. The space complexity is O(1)O(1)O(1) and there is no extra space overhead.
461-Hamming distance
Leetcode-cn.com/problems/ha… The Hamming distance between two integers refers to the number of different positions of the two numbers corresponding to the binary bits. Given two integers x and y, calculate the Hamming distance between them. Note: 0 ≤ x, y < 231. Example: Input: x = 1, y = 4 Output: 2 The arrows above indicate the different locations of the corresponding binary bits.
Start by listing the binary sequence of the two numbers in the example:
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100Copy the codeObviously, the solution can be obtained by counting the number of 1’s in the result using property 11 if the two numbers are different or the binary bits are different. So the code looks like this:
/ * * *@param {number} x
* @param {number} y
* @return {number}* /
var hammingDistance = function(x, y) {
var xorRes = x ^ y, count = 0
while(xorRes ! = =0) {
xorRes &= (xorRes - 1)
count++
}
return count
};
Copy the codeBoth time complexity and space complexity are O(1)O(1)O(1).
1356 – Sort by the number of ones under the numeric binary
Leetcode-cn.com/problems/so… I give you an integer array arr. You sort the elements of the array in ascending order by the number of digits 1 in their binary representation. If there are multiple numeric binaries with the same number of 1s, they must be sorted in ascending numerical order. Please return the sorted array. Example 1: Input: arr = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7] Explanation: [0] is the only number that has zero ones. [1,2,4,8] all have a 1. [3,5,6] we have two ones. [7] There are three ones. The result array sorted by the number of 1s is [0,1,2,4,8,3,5,6,7]
The most violent method is to directly call the sorting function of the language. In the comparison function, property 11 is used to count the number of 1 in the binary sequence of Value1 and Value2, and the final number of 1 is in ascending order according to the number of 1, and in ascending order according to the value size at the same time. So the code looks like this:
/ * * *@param {number[]} arr
* @return {number[]}* /
var sortByBits = function(arr) {
return arr.sort((v1, v2) = > {
var temp1 = v1, temp2 = v2, count1 = 0, count2 = 0
while(temp1 ! = =0) {
temp1 &= temp1 - 1
count1++
}
while(temp2 ! = =0) {
temp2 &= temp2 - 1
count2++
}
return count1 === count2 ? v1 - v2 : count1 - count2
})
};
Copy the codeComplexity analysis: The overhead comes from the system’s own sorting function. Array.prototype.sort of JS is implemented using quicksort, so its complexity is consistent with that of quicksort: time complexity is O(nlogn)O(nlogn)O(nlogn) O(n)O(n)O(n) O(n)O(n).
conclusion
Of the questions listed above, I think 78 – subset and 169 – majority elements are representative questions. The common feature of these questions is that they can be broken down into multiple combinations of true and false questions. 78 – a subset is a set of problems broken down into the existence of each number in the array; The 169 – majority elements are split into multiple values at each position in the statistical binary sequence. So you can think in this direction when you’re solving problems.
A bitmask
Although this article is from an algorithmic perspective, there are some practical tips for bit computing in daily development, such as the bitmask technology used in the well-known JS function library Lodash.
Bitmasks are usually used to handle combinations of multiple Boolean variables. BaseClone, the base function for copying related functions of JS objects in Lodash, uses bitmasks to control different cloning methods. Let’s dive right into its core code.
First, we need several default masks, each consisting of a single binary sequence of 1’s (so they are all powers of 2), each bit representing a switch, and in subsequent code we can use some binary operations to represent different combinations of relationships:
const CLONE_DEEP_FLAG = 1 // 0001: deep copy
const CLONE_FLAT_FLAG = 2 // 0010: Copy the prototype chain flag bit
const CLONE_SYMBOLS_FLAG = 4 // 0100: Copy the Symbol type Symbol bit
Copy the codeThen the cloneDeep code, it calls the baseClone, and passed the mask CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG, this expression computing result is 5, 0101 is the binary. We found that the two mask by | operation combination, can let two flags at the same time become 1:
function cloneDeep(value) {
// cloneDeep requires both a deep clone and a clone Symbol
4 - > / / 1 | 0001 | 0100 - > 0101
return baseClone(value, CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG)
}
Copy the codeFinally found baseClone core code, it will just incoming CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG and three mask respectively for & operation, suddenly found here is used in the nature of common properties of 3! At this time, it will be found that we only need to conduct & operation between the mask bitmask passed in and the mask of each flag. If the corresponding binary bit in bitmask is 1, the result is the value of the mask. If the corresponding binary bit in bitmask is 0, the result is 0. In this way, the corresponding Boolean variable can be generated for each flag bit, which can be used for the subsequent function judgment:
/ / so we just the incoming value is 1 | 4 = 5
// So isDeep is 5&1 = 1
/ / 0101
/ / & 0001
// ------
/ / 0001
// It can be found that the corresponding flag bit exists in the binary sequence passed into the mask
// & returns the mask of the current flag bit
// If the result is 0, it means there is no flag bit in the mask. The result is 0 == false
// If the result is greater than 0, it means that the corresponding flag bit exists in the mask, and the result is any number, which is converted to a Boolean value of true
function baseClone(value, bitmask, customizer, key, object, stack) {
const isDeep = bitmask & CLONE_DEEP_FLAG
const isFlat = bitmask & CLONE_FLAT_FLAG
const isFull = bitmask & CLONE_SYMBOLS_FLAG
...
}
Copy the codeReferences bit operation has what strange skill fancy-craft? How does Lodash implement deep copy