I’m not going to tell you how fast a bitwise algorithm is, but you can simulate it with a billion data points, but I’m going to give you some classic examples of bitwise algorithms. However, the most important thing is not to understand these examples, but in the future to use more bit operations these skills, of course, the use of bit operations, but also can be installed force, do not believe, you look down. I’ll start with the simplest ones, one by one more difficult, but it’s actually about skills, so it’s not too difficult, I believe you can understand it in a minute.

Judge odd and even

To determine whether a number is based on an even number, which I believe many of you have done, the general code is as follows

if( n % 2) == 01
    // n 是个奇数
}
Copy the code

If n is displayed in binary form, in fact, we only need to determine whether the last binary bit is 1 or 0. If it is 1, it represents an odd number, and if it is 0, it represents an even number. Therefore, the code of bit operation is as follows:

if(n & 1 == 1){// n is an odd number. }Copy the code

One might say, well, if we write it in n % 2 form, the compiler will automatically optimize it for us, and that’s true, some compilers will automatically optimize it for us. But it would be nice if we could write it ourselves in bitwise terms. People see your code? Shit, it’s awesome. You can still hold a pussy, can’t you? Of course, time efficiency is also much faster, do not believe you to test the test.

2. Swap two numbers

Swap two numbers. I’m sure many of you have written this every day, and I’m sure you use an extra variable every time. For example, we want to swap x and y values.

int tmp = x;
x = y;
y = tmp;
Copy the code

Is there a problem with writing this? What if someone asks you a hard time and ** doesn’t allow you to use extra helper variables to complete the swap? ** Before you mention it, someone was actually asked for an interview, which is when bitwise computing comes in. The code is as follows:

X = x ^ y // (1) y = x ^ y // (2) x = x ^ y //Copy the code

Oh, my god! All three are x to the y, so somehow the swap works. And just to explain, we know that two identical numbers either or are going to be equal to 0, which is n to the n is equal to 0. And any number that is xor to 0 is equal to itself, that is, n to the 0 is equal to n. So, here’s the explanation:

If you substitute the x in PI (1) into the x in PI (2), you get PI

Y = x^y = (x^y)^y = x^(y^y) = x^0 = x. The value of x is successfully assigned to y.

For (3), the derivation is as follows:

X = x^y = (x^y)^x = (x^x)^y = 0^y = y.

And just to explain, xOR supports commutative and associative properties of operations.

In the future, if others do not understand your code, you can use such a formula in the code to exchange the values of two variables, do not call me.

Talk about this, is to tell you the powerful bit operation, so that you can use more bit operation to solve some problems in the future, temporarily learn not to also have nothing, read more will learn, do not believe? Let’s move on, and these are some of the most common problems that you’ve probably done before.

3. Find numbers that are not repeated

You are given a set of integer numbers, in which one number appears only once and the others appear twice, and you are asked to find a number.

This is a problem that a lot of people might store in a hash table, and each time you store it, you keep track of how many times that number occurs, and then you iterate over the hash table to see which number occurs only once. This method is O(n) in time and O(n) in space.

However, I want to tell you that using bit operations to do, absolutely high force lattice!

We just said that the result of two identical numbers is 0, and the result of a number and 0 is itself, so let’s take the whole set of integers as xOR, for example: 1, 2, 3, 4, 5, 1, 2, 3, 4. Five of them only appeared once, the others all appeared twice, and the result was as follows:

Since xOR supports the commutative and associative laws, so:

1 ^ 2 ^ 3 ^ ^ 4 5 ^ 1 ^ 2 ^ 3 ^ 4 = ^ ^ 1 (1) (2 ^ 2) ^ ^ (3 ^ 3) (4 ^ 4) 5 = 0 ^ ^ ^ ^ ^ 0 0 0 5 = 5.

In other words, the number that appears twice and then becomes zero, the number that appears once and then equals itself. Is this solution awesome? So here’s the code

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1; i < arr.length; i++){ tmp = tmp ^ arr[i]; }return tmp;
}
Copy the code

It’s O(n) in time, O(1) in space, and it looks pretty cool.

Four, three to the n

What would you do if you had to solve for 3 to the n, and you couldn’t use the poW function that came with the system? This is not easy, just multiply n 3’s in a row, like this:

int pow(int n){
    int tmp = 1;
    for(int i = 1; i <= n; i++) {
        tmp = tmp * 3;
    }
    return tmp;
}
Copy the code

But if you do so, I can only ha ha, time complexity for O(N), afraid is primary school students will! If you had to do it in bits, what would you do?

For example, if n = 13, the binary representation of n is 1101, then 3 ^ 13 can be disassembled as:

3^1101 = 3^0001 * 3^0100 * 3^1000.

We can read 1101 bit by bit by &1 and >>1, multiplying the multiplier represented by the bit to the final result at 1. It’s easier to understand if you just look at the code:

int pow(int n){
    int sum = 1;
    int tmp = 3;
    while(n ! = 0) {if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
    
    return sum;
}
Copy the code

The time complexity is almost O(logn), and it looks pretty cool.

Here, an operation in many cases are very involved in binary, so we have to determine whether whether the bit operations, in many cases they are split into the binary, then observe features, or is the use and, or, to observe the characteristics of the exclusive or, in short, I feel more examples, plus himself begin, is easy to use. So, read on, notice, don’t look at the answer, see if you can do it first.

5. Find the largest power of 2 not greater than N

The traditional way is to multiply 1 by 2, as follows:

int findN(int N){
    int sum = 1;
   while(true) {if(sum * 2 > N){
            returnsum; } sum = sum * 2; }}Copy the code

If I do this, the time is order logn, but if I change it to bitwise, what do I do? Now, as I said, if we’re going to do it bitwise, a lot of times we’re going to split something into binary and see what we find. Let me give you an example.

For example, if N = 19, the conversion to binary is 00010011 (I’ll use 8-bit binary here for convenience). So what we’re looking for is we’re going to keep the leftmost 1 in binary, and all the ones after that are going to be zeros. So our target number is 00010,000. So how do we get this number? The corresponding solution is as follows:

1. Find the leftmost 1 and turn all the zeros to its right into ones

2, add 1 to the value, you can get 00100000 namely 00011111 + 1 = 00100000.

3, get 00100000 move one to the right, you can get 00010000, that is 00100000 >> 1 = 00010000.

So the question is, what do I do in step 1 to convert the last 0 in the leftmost 1 to 1? Let me show you the code and explain it later. This code converts all the zeros following the leftmost 1 to ones,

n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
Copy the code

That’s just by shifting n to the right and doing the or. Let me explain. If we assume that the leftmost 1 is in the KTH bit of binary (from left to right), then if we move n one bit to the right, the k+1 bit must be 1. Then if we do or with the right bit, the k and k+1 bits must be 1. Similarly, if you move n two places to the right again, the k+2 and k+3 bits in the result must be 1. Then do the or operation again, and you get the k, k+1, k+2, k+3 are all 1, and so on….

The final code looks like this

int findN(int n){ n |= n >> 1; n |= n >> 2; n |= n >> 4; 8 / / n | = n > > general is a 32-bit integer, I'm assuming 8 above.return (n + 1) >> 1;
}
Copy the code

The time complexity of this approach is approximately O(1), and the point is, high order.

conclusion

Above spoke 5 questions, originally wanted to write 10, discovered 5 already wrote for a long time ，，，， 10 words, afraid you also don’t have the patience to write, and a more difficult than a kind of ，，，，.

However, the examples I’ve given here are not meant to make you Ok with learning these problems, but to give you a sense that in many cases, bit arithmetic is a good choice, at least it’s a lot faster, and it’s a lot more efficient. So, in the future, you can try to use more bit operations, oh, I will give you some problems to talk about in the future, encounter high forced lattice, feel very good, will be used for you to learn.

If you think the article is good, fine

1, like, so that more people can see this content (collection does not like, are playing rogue -_-)

Focus on me, let’s become a long-term relationship

3. Follow the public account “Helpless and painful code Farmer”, which has more than 100 original articles, I also share a lot of video, book resources, and development tools, welcome your attention, the first time to read my article.