Bit operation¶
Here I have summarized a few bit calculation problems to share with you. They are 136 and 137, 260 and 645, and there are four problems in total. The four questions are all bitwise calculation routines. If you want to practice bitwise calculation, don't miss it~~
Appetizer¶
Before we start, let's understand the XOR, which will be used later.
- The nature of XOR
The result of the exclusive OR of two numbers a^b is the number obtained by operating each bit of the binary of a and b. The logic of the operation is 0 if the same digit is the same, and 1 if it is different
- The law of XOR
-The exclusive OR of any number and itself is 0
-Any number and 0 are exclusive or itself
- The exclusive OR operation satisfies the commutative law, namely:
a ^ b ^ c = a ^ c ^ b
OK, let's take a look at these three questions.
136. The number 1 that appears only once¶
The main idea is that except for one number that appears once, the others appear twice. Let us find the number that appears once. We only need to perform XOR for all members once.
class Solution:
def singleNumber(self, nums: List[int]) -> int:
single_number = 0
for num in nums:
single_number ^= num
return single_number
Complexity Analysis
-Time complexity: \(O(N)\), where N is the length of the array. -Space complexity: \(O(1)\)
137. The number 2 that appears only once¶
The main idea is that except for one number that appears once, the others appear three times. Let us find the number that appears once. Flexible use of bit operations is the key to this question.
Python3:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for i in range(32):
cnt = 0 # Record how many 1s the current bit has
bit = 1 << i # Record the current bit to be operated
for num in nums:
if num & bit != 0:
cnt += 1
if cnt% 3 != 0:
# Not equal to 0 means that the only number that appears on this bit is 1
res |= bit
return res-2 ** 32 if res> 2 ** 31-1 else res
-Why does Python need to judge the return value at the end?
If you don't do this, when the test case is [-2,-2,1,1,-3,1,-3,-3,-4,-2], 4294967292 will be output. The reason is that Python is a dynamically typed language, in which case it will treat the 1 at the symbol position as a value, rather than as a symbol "negative number". this is not right. The correct answer should be-4. The binary code of -4 is 1111...100, which becomes 2^32-4=4294967292. The solution is to subtract 2 ** 32.
The reason why this is not a problem is that the range of the array limited by the title will not exceed 2 ** 32
JavaScript:
var singleNumber = function(nums) {
let res = 0;
for (let i = 0; i < 32; i++) {
let cnt = 0;
let bit = 1 << i;
for (let j = 0; j < nums.length; j++) {
if (nums[j] & bit) cnt++;
}
if (cnt % 3 != 0) res = res | bit;
}
return res;
};
Complexity Analysis
-Time complexity: \(O(N)\), where N is the length of the array. -Space complexity: \(O(1)\)
645. Wrong collection¶
The idea is the same as the above 137. The number 2 that only appears once This question does not limit the space complexity, so it is no problem to store the hashmap directly. Not much to say, let's look at a solution with space complexity \(O(1)\).
Because the idea is basically the same as 137. The number 2 that only appears once, I reused the code directly. The specific idea is to extract all the indexes of nums into an array idx, then the array composed of idx and nums forms the input of singleNumbers, and the output is the only two different numbers.
But we don't know which is missing and which is duplicate, so we need to traverse again to determine which is missing and which is duplicate.
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret = 0 # The result of exclusive OR of all numbers
a = 0
b = 0
for n in nums:
ret ^= n
# Find the first digit that is not 0
h = 1
while(ret & h == 0):
h <<= 1
for n in nums:
# Divide it into two groups according to whether the bit is 0
if (h & n == 0):
a ^= n
else:
b ^= n
return [a, b]
def findErrorNums(self, nums: List[int]) -> List[int]:
nums = [0] + nums
idx = []
for i in range(len(nums)):
idx.append(i)
a, b = self.singleNumbers(nums + idx)
for num in nums:
if a == num:
return [a, b]
return [b, a]
Complexity Analysis
-Time complexity: \(O(N)\) -Space complexity: \(O(1)\)
260. The number 3 that appears only once¶
The main idea of the question is that except for the two numbers appearing once, the others appear twice. Let us find these two numbers.
We perform a full exclusive OR operation, and the result is the exclusive OR result of the two different numbers that only appear once.
We just talked about the exclusive OR law, there is a any number and its own exclusive OR is 0, so our thinking is whether these two different numbers can be divided into two groups A and B. Grouping needs to meet two conditions.
-
Two unique numbers are divided into different groups
-
The same number is divided into the same group
In this way, each group of data can be XORed to get those two numbers.
The key point of the question is how do we group it?
Due to the nature of XOR, if the same bit is the same, it is 0, and if it is different, it is 1. The result of we XOR all numbers must not be 0, which means that at least one bit is 1.
Let's pick one at random, and the basis for grouping will come, that is, the one you take is 0 and divided into 1 group, and the one you took is divided into 1 group. This will definitely ensure that 2. The same numbers are divided into the same group, will different numbers be divided into different groups? Obviously of course it can, so we choose 1, which means Say that two unique numbers must be different in that one, so two unique elements must be divided into different groups.
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret = 0 # The result of exclusive OR of all numbers
a = 0
b = 0
for n in nums:
ret ^= n
# Find the first digit that is not 0
h = 1
while(ret & h == 0):
h <<= 1
for n in nums:
# Divide it into two groups according to whether the bit is 0
if (h & n == 0):
a ^= n
else:
b ^= n
return [a, b]
Complexity Analysis
-Time complexity: \(O(N)\), where N is the length of the array. -Space complexity: \(O(1)\)
Related topics¶
-190. Reverse binary bits (simple) -191. Number of bit 1 (simple) -338. Bit count (medium) -1072. Flip by column to get the maximum and other rows (medium)
For more solutions, please visit my LeetCode solution repository: https://github.com/azl397985856/leetcode. Currently it has 38K stars.
Pay attention to the official account and try to restore the problem-solving ideas in clear and straightforward language, and there are a lot of illustrations to teach you to identify routines and to efficiently solve the problems.