A girl carrying a pile of books out of the library in the morning, the results of the alarm rang, aunt let the girl see which book alarm ring, the girl poured out the book, ready for a test. Seeing this, the old woman divided the book into two parts. The first one passed and rang. This one is divided into two parts and then tested, three times to find, the old woman looked at the girl with contempt, as if to say that O(n) and O(logn) are not clear. (Please leave a message if you understand ~)
01. Basis of bit operation
All the numbers in the program are stored in the form of binary in the computer memory, and the bit operation is to operate directly on the binary bits of the integer in memory.
Let’s start by simply listing the usual bit operations:
02. Strange techniques of bit operation
The above content is relatively routine, but the average interview we encounter, are not routine content. So here’s what you need to know.
Here are eight tips that cover 90% of all interview questions:
- use
x & 1 == 1Judge odd and even. (Note that the bottom layer of some editors will automatically optimize the code using % to determine odd and even numbers into bitwise operations.) - Instead of using the third number, swap two numbers.
x = x ^ y，y = x ^ y，x = x ^ y. (Earlier years like to ask, now if anyone asked again, we will feel very low) - The result of two identical xor numbers is 0, and the result of a number and 0 xor is itself. (Xor often has a different use for finding numbers.)
x & (x - 1), you can set the rightmost 1 to 0. (This trick can be used to detect powers of two, or the number of ones in an integer binary, or how many bits change when someone asks you to change one number to another.)- Xor can be used as a no-carry addition, and the and operation can be used to get the carry.
i+(~i)=-1When I is inverted and then added to I, it is equivalent to setting all the binary bits to 1. The decimal result is -1.- For INT32, use
n >> 31I get n plus or minus. And can be accessed through(n ^ (n >> 31)) - (n >> 31)To get the absolute value. (n is positive,n >> 31All the bits of theta are equal to 0. If n is negative,n >> 31All bits of are equal to 1 and its value is equal to -1. - use
(x ^ y) >= 0To see if the signs are the same. (If both numbers are positive, then the first digit of binary is 0,x^y=0; If both numbers are negative, the first digit of the binary is 1.x^y=0If two numbers have opposite signs, the first digit of the binary is opposite,x^y=1. Except for 0, ^ same gets 0, different gets 1.
03. Sum of two numbers
Let’s start with the simplest one. This problem is very old, take it out to the students who can not have a look, will directly skip. (Worth mentioning is that this topic on the foreign, there are 2000 dislike, you can see everybody’s dislike!)
| 268: Calculate the sum of two integers A and b without using the operators + and -. |
|---|
 |
| Go straight to the bizarre techniques we discussed above: |
Xor is a carry – less addition, which literally means cutting the carry. For example, 01 ^ 01 = 00.
“And” can be used to get the carry result, such as 01&01=01, and then move the result one bit to the left to get the carry result.
Based on the above two techniques, suppose we have 12+7:
//JAVA
class Solution {
public int getSum(int a, int b) {
while(b ! =0) {
int temp = a ^ b;
b = (a & b) << 1;
a = temp;
}
returna; }}Copy the codeYes, it’s that simple.
4. A power of 2
Before you do this problem, you can flip to the front and see which technique you can use. If you find it, you will.
| Problem 231: Given an integer, write a function to determine whether it is a power of two. |
|---|
 |
| Let’s look at some binary numbers that are powers of two: |
 |
** can find these numbers, the highest bit is 1, the other bits are 0. ** So we convert the question to “determine whether there is a 1 in the binary of a number other than the highest digit 1”. Then we look at the following set of numbers, corresponding to the above number minus 1:
N&(N-1)=0So that’s our condition. (This technique can be memorized and used in some other bitwise operations.)
//go
func isPowerOfTwo(n int) bool {
return n > 0 && n&(n- 1) = =0
}
Copy the codeAgain, this is very simple. Just use the x & x minus 1 technique.
05. The number of one
To make it a little more difficult, this topic introduces the concept of a mask. A mask is the use of a string of binary code to perform bitwise operations on the target field, masking the current input bits.
| Problem 191: Write a function that takes an unsigned integer and returns the number of digits of ‘1’ in its binary expression (also known as hamming weight). |
|---|
| ` ` ` |
| Example 1: |
| Input: 00000000000000000000000000001011 |
| Output: 3 |
| Explanation: the input binary string in 00000000000000000000000000001011, a total of three for the ‘1’. |
Example 2: input: 00000000000000000000000010000000 output: 1: input binary string in 00000000000000000000000010000000, a total of a ‘1’.
Example 3: input, output: 11111111111111111111111111111101 31 explanation: input binary string in 11111111111111111111111111111101, a total of 31 as’ 1 ‘.
Tip: Note that in some languages, such as Java, there are no unsigned integer types. In this case, both input and output will be specified as signed integer types, and should not affect your implementation, because the internal binary representation of an integer is the same whether it is signed or unsigned.
In Java, the compiler uses binary complement notation to represent signed integers. Therefore, in example 3 above, the input represents the signed integer -3.
They're a little long, but I said that before. For most questions, the longer the question, the easier it is. First, the easiest way to think about it is: ** We simply convert the target number to binary, then iterate over each digit to see if it is a 1, and if it is a 1, write it down. ** does it in this rather violent way. For example, in Java, the int type is 32 bits, so we can solve the problem as long as we can calculate the current digit. So how do we calculate the current digit number? We can construct a mask to do this, and the mask may sound confusing to you, but it's just a 1. The binary of 1 looks like this:! [](https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/74cd6cfd5b384666ba1e60e17d153555~tplv-k3u1fbpfcp-zoom-1.image) All we need to do is move the mask one bit to the left at a time and evaluate it with an ampersand to determine whether the current bit of the target value is 1. For example, the binary with target value 21,21 looks like this:! [](https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/bb242969921446199f29da65eba76f21~tplv-k3u1fbpfcp-zoom-1.image) Then move the mask each time to calculate with the current bit:! [](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/0e5fc6d3d9c84b14ba9387774dcafce0~tplv-k3u1fbpfcp-zoom-1.image) Java public class Solution {public int hammingWeight(int n) {int result = 0; Int mask = 1; for (int i = 0; i < 32; i++) { if ((n & mask) ! = 0) { result++; } mask = mask << 1; } return result; }}Copy the codeThe only caveat: don’t write (n&mask) == 1 when judging n&mask, because you’re comparing decimal numbers. It’s easy for newcomers to make this mistake.
06. A number that appears only once
Let’s make it a little harder. So what’s the idea of solving this problem?
| Problem 136: Given an array of non-empty integers, every element appears twice except for one element. Find the element that appears only once. |
|---|
 |
In direct analysis, we’re looking for numbers that only appear once, and we know that all the other numbers only appear twice. So this sounds like a bit operation to solve it. The best is to read the topic at the moment, direct conditioning reflex! (Of course, if your first instinct is to do traversal statistics, or something like use hashMap, then I think you need to work on bitwise. If your first reaction, even the idea is not, then I think for the ability of the whole algorithm, are relatively lacking, need hard work!
So back to the question, how do we solve this using bit operations? For any two numbers a and b, we apply “xor” to them, which should have the following properties:
- Any number and 0 are either or still themselves:
A radius 0 = a - Any number is unique or 0 to itself:
A radius of a = 0 - Xor operations satisfy commutative and associative laws:
The radius radius b = the radius (a radius a) b = 0 radius b = b
Maybe some people don’t even know what xor is, so let’s take an example, like 5 Xor or 3, which is 5 × 3, which is 5 × 3, which is 5 × 3, and it looks like this:
(PP)
//CPP
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int num : nums) {
ans ^= num;
}
returnans; }};Copy the code(Java version)
//JAVA
class Solution {
public int singleNumber(int[] nums) {
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
ans = ans ^ nums[i];
}
returnans; }}Copy the code(python version)
//py
class Solution:
def singleNumber(self, nums: List[int]) - >int:
ans = 0
for i in range(len(nums)):
ans ^= nums[i]
return ans
Copy the code07. Numbers that appear only once ⅱ
Your uncle or your uncle, but your aunt is not your aunt!
| 137. Given an array of non-empty integers, every element appears three times except one. Find the element that appears only once. Note: Your algorithm should have linear time complexity. Can you do it without using extra space? |
|---|
 |
There’s really nothing to be said for using a HashMap.
func singleNumber(nums []int) int {
m := make(map[int]int)
for _, k := range nums {
// If it is a different language, please note the corresponding nullation operation!
m[k]++
}
for k, v := range m {
if v == 1 {
return k
}
}
return 0
}
Copy the codeOf course, there is another mathematical solution: Principles: [A,A,A,B,B,B,C,C,C] and [A,A,A,B,B,B, B,C], with two C’s missing. That is:
3 * (a + b + c) - (a + a + a + b + b + b + c) = 2 cCopy the codeIn other words, if you multiply the array by 3, you get exactly twice the value of the element you’re looking for. Here’s an example:
Use this property to solve the problem :(python code is shown below. Note that using int may cause an error because it is out of bounds.)
//python
class Solution:
def singleNumber(self, nums: List[int]) - >int:3
return int((sum(set(nums)) * 3 - sum(nums)) / 2)
Copy the codeIt works well, but it still uses extra space. So we still have to use bit operations. The reason why “every other element is quadratic” can be solved with “xor” is that “xor” operation can make two numbers return to 0. So for the rest of the elements that occur three times, if we can get all three of them to be equal to zero, is that enough?
It’s a simple idea, but it’s a little bit more difficult to understand. If you’re ready, you can start reading. I have read the solutions of leetcode, many of which are directly thrown out a formula. In fact, I think it is not particularly clear. So WHAT I’m going to do is I’m going to reduce this to a case where everything else happens twice.
Suppose we have [21,21,26] three numbers like this:
Think back to the reason whyExclusive or“We actually did oneTwo ones in the same place clear outIn the process. The diagram above may look easy if it looks like this:
How do we construct it? Let’s start with the first method. a ? A = 0), observe the xOR operation:
1 ^ 1 = 0 0 ^ ^ 0 = 1 1 = 1Copy the codeIs it, in fact, the addition of the binary, and then the reduction of the carry?
a ? a ? a = 0Is it just adding up all the bits of binary, and then modulo 3? (Again, if you want to define aa ? a ? a ? a = 0, then finally take the modulus of 4.)
//go
func singleNumber(nums []int) int {
number, res := 0.0
for i := 0; i < 64; i++ {
// Initialize each 1 to 0
number = 0
for _, k := range nums {
// Count the number of 1's in each digit by shifting it I bit right
number += (k >> i) & 1
}
// Finally put the remaining 1 in the corresponding digit
res |= (number) % 3 << i
}
return res
}
Copy the codeIf you don’t understand the code above, take a look at this diagram. If there is only one number [21], we get the 1 in each digit by moving it to the right. And, of course, since they’re all 1’s, they’re all going to be preserved, and then you’re going to do an and operation with 1, and then you’re going to put them in the corresponding digit.
In the above code, we use a number to record the number of occurrences of each digit. The downside, though, is that we record 64-bit (in Go, int is more than 32 bits)
So if we could count all the bits at once, wouldn’t that simplify the process? Because we’re trying to modulo each of these bits with 3, is it really a ternary system? If you don’t understand the ternary system, it can be simply understood as three times a cycle, which is 00-01-10-11. But since we need to chop off the 11, we only have three states, 00-01-10, so we use a and B to record the states. The state transfer process is as follows:
Here a and B mean the state of A and B next time. Next represents the value of the next bit. And then what is this? It’s a state machine… We do this by counting the states of A and B.
Then, because the graph is complex, it is simplified to a Carnot diagram of A and b, respectively (a carnot diagram is a graphical representation of a logical function. Two logical adjacent items are merged into one item, keeping the same variables and eliminating different variables.
| Next, a, b | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 1 | 1 | 0 | X | 0 |
| 0 | 0 | 1 | X | 0 |
| Next, a, b | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 1 | 0 | 1 | X | 0 |
| 0 | 0 | 0 | X | 1 |
Then we use the Carnot diagram (which is actually not ugly. It’s pretty easy if you learn it. Write the relationship:
a` = (a &~ next) | (b & next)
b` = (~a & ~b & next) | (b & ~next)
Copy the codeThen there is the formula :(Java code, note that the Go language does not naturally support ~ this kind of calculation)
//java
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0, tmp = 0;
for (int next : nums) {
tmp = (a & ~next) | (b & next);
b = (~a & ~b & next) | (b & ~next);
a = tmp;
}
returnb; }}Copy the codeOf course, in fact, the solution can be further optimized, which is to simplify the formula in the previous step:
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int next : nums) {
b = (b ^ next) & ~a;
a = (a ^ next) & ~b;
}
returnb; }}Copy the codeOf course, this solution is pretty cheesy. If you really do not understand it does not matter, please master the above two solutions.
I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download
