preface

In the previous section, we introduced several basic operators and operation rules of bit operation. In this section, we will explain some common skills and application scenarios of bit operation combined with specific cases. To introduce more organized, this article will, in accordance with the and (&), or (|), xor (^), the displacement of the (~) and operation order of operation, to introduce respectively corresponding to the operations of the common used techniques. Some techniques will be explained later if you need to combine more than one operator, and the bits for a number in this article will all start at zero.

Skills summary

  1. & common techniques

    We know that ampersand is only 1 if both digits are 1. So this feature is also at the heart of some of the techniques for & (more than a magic number used to place a number at some position 0). For example, if the second position of a number x is 0, x and 0xFFFF FFFB can be applied & (b corresponds to 1011). Here are some specific skills related to & :

    • In general, we can judge the odd and even of a number by the result of x % 2. In fact, we can also judge by the result of x & 1. From the above, we know that x & 1 will set all the bits except the 0th bit to 0. The binary number of odd numbers is 1 and the binary number is 0. So it can be used to judge even and odd in this way.

      In particular, because of operator precedence, for x & 1 == 1, 1 == 1 is evaluated first, so for x & 1 == 1, it must be changed to for (x & 1) == 1. Because Java does not use statements like if (x & 1) {} in languages like C. Therefore, in Java, it is convenient to use x % 2 == 0 directly.

    • In the first tip, we covered a seemingly impractical technique, but this time we’ll use a slightly more useful one. We all know that in the ASCII table a-z corresponds to 65(0100 0001) -90 (0101 1010) and a-z corresponds to 97(0110 0001) -122 (0111 1010). By careful comparison, we can see that for binary representations of lowercase and uppercase letters, such as A and A, 0100 0001(A) and 0110 1010(A), only the fifth bit is different, so we can quickly convert lowercase letters to uppercase by simply setting the fifth bit to 0 with am& and leaving the other bits. The magic number is -33(0xFFFF FFDF), so in Java we can quickly convert a letter C to its corresponding uppercase letter by using the statement (char) (c & -33). If there is a case to case, is there a case to case method? There are of course, but not use &, but use, is | operations, will soon be talking about below.

    We have covered two basic skills above, and here is a slightly more complex one, with some examples to help you understand it better.

    • First, the conclusion that n & (n-1) is used to remove the 1 from the rightmost part of the binary digit n corresponds to. Then we’ll explain why (in binary terms for convenience) : For any number, since we are concerned with setting the last 1 of the binary digit of a number to 0, we can represent a number n as xxx100 of the form (x represents any 0 or 1, the digit before the right-most 1, and since it is the last 1 in the digit, That 1 must be followed by a number of zeros.

      So for n(xxx100), n-1(xxx011), the result, I don’t need to tell you, is XXX 000, which achieves the goal of setting the last 1 of n(XXX 100) to 0. This is just a simple proof, so you can try it out on your own. Here is an example based on this technique (not necessarily the best result of the problem, but it can be used to improve the understanding of the technique) :

      Counting the number of 1 bits in a number without using Java’s bitCount method.

      When we look at this problem, we can easily think of something like this:

      count = 0
whilen ! =0:
    Count is incremented if each bit of the binary is 1, and 0 if not, the total number of operations depends on the position of the n highest 1 bits.
    count += n & 1
    n >>= 1
print(count)
Copy the code

      But, try to think, how can we use the method we have just described? If you think about it, the trick can be used to set the position of the last digit of a number to 0, so every time you remove the last 1, you can then remove the penultimate 1…… If you think about it carefully, the number of operations in this method only requires the number of 1’s in the digit. Here is the code implementation:

      count = 0
whilen ! =0:
    # remove one 1 at a time from the binary representation of n
    n &= n - 1
    count += 1
print(count)
Copy the code

    The essence of the trick is still to set the digit to 0 (the last 1 in a binary digit is set to 0), so the core of the ampersand trick is to set some digit to 0. There is also a technique for setting zero by combining and ~, which we will save for ~.

  2. | common skills

    From the above discussion & skills core (0) the position of the number, believe clever you must know, | core skills is the advantage of the characteristics of | operation, certain number 1 position. Or, for example, such as a number of x position 1, 3, just need to x and zero x0000 0008 | operation can be corresponding, 1000 (8). Here are a few tips related to this core:

    • In point one, we’ll start with the method of converting uppercase letters to lowercase letters mentioned above. As mentioned in the discussion of binary uppercase and lowercase letters above, each lowercase letter differs from its uppercase letter only in the fifth bit, which is 1 for all lowercase letters and 0 for all uppercase letters. Therefore, we can through the | operation, will position is 1, 5 can be a capital letter to lowercase letters, the magic number is 32 x0000 (0 0040), so we can in the Java by (char) (c | 32) this statement, quickly will a letter c converted to their corresponding capital letters.

      | operation more than that, of course, a simple common skills, but for the sake of flat (qiang) scale (Po) (zheng), also combined with the technique used in displacement calculation, while the core is |, I still will be put in place on the computation.

  3. ^ Common techniques

    Unlike & and | ^ operator can have some of the commonly used operation type, use ^, mostly USES the (both have the same number, the result is 0, otherwise not 0) this feature, here are two tips, first has some use scenarios:

    • Before we get to the first technique, let’s look at a question:

      Given two integers, determine whether two numbers have the same sign (that is, both positive and negative).

      When we first see the problem, it’s easy to think of two types of code:

      def f(a:int, b:int) :
    return (a >= 0 and b >= 0) or (a < 0 and b < 0)

def f(a:int, b:int) :
 # may overflow, incorrect
    return a * b >= 0
Copy the code

      In this case, if we use ^, it will not only make the code look very concise, but also don’t need to worry about multiplication overflow. The corresponding code is as follows:

      def f(a:int, b:int) :
    return (a ^ b) >= 0
Copy the code

      And the principle is also very simple, because two if the same number, then the highest sign bit must be the same, after xor will become 0, then xor result is non-negative, so we can judge whether two numbers are the same number according to the positive and negative of two xor results.

    • The second technique is less practical and more interesting, and I believe many of you have seen it. The code and explanation are as follows:

      a ^= b // The original a becomes a ^ b
b ^= a // b = (a ^ b) ^ b = a
a ^= b // The current value of a is a ^ b, and the value of b is a, so a = (a ^ b) ^ a = b
Copy the code

      The above code and explanation may be a little confusing at first glance, but if you think about it a little, you’ll see that this operation is just swapping the values of two numbers. This method is not recommended in the actual coding, more to expand their way of thinking.

    ​

  4. Common skills of ~

    In fact, the common skills of ~ can be said to have no, the only one is not as the protagonist, in order to balance, put here to speak, I believe that read the above already know, the protagonist is who, right, is &! To recap, ~ is used to convert a binary digit from 1 to 0,0 to 1, and the negative value of an integer (~x + 1). N & (~n + 1) can be used to set the binary digits of a number to 0 except for the last 1. That’s right. This is actually the last example we had in ampersand, the reverse effect, where you set the last 1 of a number to 0, and here you protect the last 1, and all the other bits go to 0! Here’s why: 1 = 0; 2 = 0; 2 = 0; Consider n(xxx100). In order to calculate ~n + 1, we calculate ~n first and get zzz011 (where z stands for the opposite of x). Then we add 1 to get zzz100, so the calculation of n and ~n + 1 is as follows:

    x x x 1 0 0

    &

    z z z 1 0 0

    0 0 0 1 0 0 0

    Here’s an example of a problem where you can use this technique, and of course the core of the problem is using ^, but you can try it out.

  5. Common techniques for displacement operations (>>, <<, >>>)

    From the previous section, we learned the rules and details of displacement operation. Generally speaking, displacement operation can be used to multiply or divide by 2 instead of multiplication. Just like in the Source code of ArrayList in Java, when capacity expansion is carried out, By x + (x >> 1) to achieve the original capacity of 1.5 times, I will talk about some of the displacement calculation techniques:

    • In binary search, (left + right) / 2 will overflow due to the large number of left and right, so the desired result cannot be obtained. The general solution is: Left + (right-left) / 2, but in Java, since we have the >>> unsigned right shift, I just need to use (left + right) >>> 1 to avoid overflow. Of course, not all languages support this, So >>> This technique is also somewhat limited.

    • Finally, let’s talk about a more practical operation (although this is only useful in brush problems, there are several problems in LeetCode that can use this idea). Because of the complexity, let’s jump to the conclusion, and then analyze and prove it in detail:

      1. a |= a >> 16;	// The whole operation is used to make a the highest
2. a |= a >> 8;		// Bits 1 and below change to 1, for example
3. a |= a >> 4;		// 1010 0000
4. a |= a >> 2;		// will change to 1111 1111.
5. a |= a >> 1;
Copy the code

      Has demonstrated the specific below, in terms of the interpretation based on 8-bit integer (easy to explain, so we just need to step 3-5), digital starting from 0, due to the Numbers 0 does not contain 1, so after operating results still is 0, 0 to 7, suppose you have a number to its highest level in the first 1 x bits (0 < = x < = 7), So after the first operation, the first x and x – 4 will be into 1 (advantage of the characteristics of the | operation buy 1), and then perform step 4 operations, because we are the first and the first x – 4 x 1, so after step 5, we can now let the x – 2 a and the x – six into 1, in the same way after step 5, We can set the x-7 ~ x bits to 1 (if x is 3, then the corresponding -4 ~ 3, negative digit discard, that is, the 0 ~ 3 bits will be 1), and finally realize the operation of setting the x bits and the bits below x to 1. And one last problem, just to take advantage of the idea above, you can try it out, the complement of numbers.

summary

This is about the use of a few common bit operation skills and specific case, of course, there are many commonly used techniques, due to reasons such as generality, may be on the back to tell, but interest is the best teacher, still hope everybody can discover more yourself, and then communicate together, later also will summarize related to bit operation data structure, If possible, there will be a summary of practical application scenarios. This time, I will stop here. If there are mistakes, please help to point out.