preface

About bit operation, I believe that we are not unfamiliar, especially wrote some of the performance requirements are very strict project students, after all, this is a program to improve performance and efficiency of the magic weapon.

As we all know, all the numbers in the program are stored in the form of binary in the computer memory, and bitwise operation is directly operating on the binary bits of the integer in memory. For example, bit and bit or, xor, etc.

This article focuses on the bit operation skills summary, the difficulty is not too big, master can also improve their own code forced case, but the key is to be patient, understand the role of bit operation.

The body of the

Judge odd and even

Let’s take a look at how we implement the operations we provide in a high-level language:

if (n % 2) == 0) {
    // n 是个奇数
} else{// n is an even number}Copy the code

If n is presented 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, in the way of bitwise operation, the integer to be determined is bitwise and 1. For example, 8 (1000) &1, the result is 0, indicating that it is even.

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

Now, one might say, well, the compiler will optimize for bitwise operations for us, but, but, well, you can just go into the IDE and see the time efficiency comparison, hahaha.

Swap two numbers

Swapping two numbers should be written by many people, but should always require the use of a temporary auxiliary variable, code as follows:

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

So, can you swap variables without using auxiliary variables? Let’s see:

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

May here we see a face of meng (if I guess wrong you also don’t call me haha), or explain, we use here is exclusive or operation, so what is the exclusive or operation, 0 ^ 1 result is 1, only the rest of the case is 0, so there is a characteristic of an exclusive or operation, are the two do not equal the number of exclusive or operation, the result is 1, then

  1. If (1) is substituted into (2), y = x ^ y ^ y = x ^ 0, which is x
  2. Substituting (1) and (2) into (3) yields x = x ^ y ^ x = y ^ 0, resulting in y

Find numbers that don’t repeat

I have encountered this problem in LeetCode, where all the other numbers appear twice except one:

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 numberCopy the code

We look at the topic, all of the data, there is only one number appear only once, and the others are all appear twice, as long as the two key information is ok, we have seen through the front of the subject, in two of the same number of an exclusive or operation or when the result is 0, and several other with 0 or for itself, that use an operation method are very obvious:

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

M to the n

What’s your first reaction? Is that right?

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

It’s pretty conventional and not very efficient, but think about how math.pow () is implemented in Java. No, math.pow () is a native modification method that is not implemented in Java, and I have not looked at the C code. If you are interested, go to the JDK and find the corresponding path to the class. Since it was implemented by the JDK itself using native methods, it certainly wouldn’t be as efficient (O(n)) as above, and we’d all be writing the Java language. Let’s take a look at the implementation of bit operations:

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

Time complexity is almost O(logn), does it feel a lot more efficient? For example, if n = 15, then the binary representation of n is 1111, then m ^ 15 can be divided into: M ^ 1111 = M ^ 0001 * M ^ 0010 * M ^ 0100 * m ^1000, then we can read 1101 bit-by-bit by &1 and >>1, multiplying the digit represented by 1 to the final result.

Find the largest power of two not greater than N

Let’s start with the old ways:

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

Let’s look at the largest power of two, and how it works if we use bits. Let’s look at the binary of powers of two. Suppose we have an 8-bit binary (integers are usually 32 bits). 00010, 000, et cetera, these are all powers of two, so our goal is to get zeros after binary ones. First, we change all the numbers to the right of n (let’s say eight bits) to 1

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

And then we have n plus 1

N + = 1;Copy the code

Finally, we move n 1 to the right

n >> 1;
Copy the code

Is this complete to find a number (e.g. 5 => 00000101, the largest power of 2 is 4) the largest binary number conversion? Attach the complete code:

int findN (int n) {
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    return (n + 1) >> 1;
}
Copy the code

conclusion

Bit operations, it is through the converted into a binary integer to operation, we need to be familiar with the function of various kinds of bit operations, then get a problem, first converted to binary, have a look at what is the distinguishing feature of it, then according to the characteristics of it to quasi operation, may feel difficult at the beginning, but see some examples, how to, Slowly will be able to easily come ~ everyone friends refueling ~

By the way

There is a problem? Can you leave me a message or chat privately? Just give it a thumbs up

Of course, you can also go to my official account “6 Xi Xuan”,

Reply to “Learn” and receive a copy of the Video tutorial for Advanced Architects for Java Engineers

Answer “interview”, can obtain:

MySQL brain Map MySQL brain map