In the previous section we looked at three common stack and queue questions during the interview process. In this section, I will familiarize you with some common bit operations through several topics of bit operations.

Compared with stack and queue, the author thinks that bit operation needs to master more knowledge, including binary representation of numbers, binary inverse code, complement code. And common operations in binary. Of course, if you systematically learn, you may have no experience, or even after learning, you still can’t do the questions. Therefore, the author thinks that it is a more convenient way to brush some corresponding topics directly.

Given an integer, write a function to determine whether the integer is even or odd (✭

This topic serves as a foreshadowing for subsequent topics, and it seems to have no difficulty at all. The main investigation of the interview can think of using binary bit operation method to solve.

First of all, integers can be positive, negative, and zero. You can divide it into odd and even numbers. An even number is defined as an even number if it is a multiple of 2. If we do not use the method of bit operation, we can completely use the following way:

public boolean isOdd(int num){/ / odd odd
    return num % 2! =0;
}
Copy the code

But it’s impossible to look at such a simple solution, and then we think of binary if a number is even then the last digit must be 0 and if a number is odd then the last digit must be 1; Decimal 1 is represented as 0000 0001 in 8-bit binary. We only need to add (&) to a number of ones to get a result of 1 indicating that the number is odd, not even. So the best way to solve this problem is as follows:

public boolean isOdd(int num){
    return num & 1! =0;
}
Copy the code
#include "iostream" using namespace std; // declare bool IsOdd(int num); bool IsOdd(int num) { int res = (num & 1); return res ! = 0; }Copy the code

Testing:

int main(int argc, const char * argv[]) {
  std: :cout << "Is it odd?" << IsOdd(1) < <endl;
  std: :cout << "Is it odd?" << IsOdd(4) < <endl;
  return 0;
}

/ / the resultIs it odd:1/ / is trueIs it odd:0/ / not false
Copy the code

Also given an integer, write a function to determine whether the integer is an integer power of 2 (✭

If an integer is a power of 2, then when it is represented in binary, only one of the digits must be 1, and the rest of the digits must be 0. 0100… 0. For example, if 8 is 2 to the third power, this number is represented as the binary bit 0000, 1000.

In addition, we should also consider that a binary if represented as 0.. 0100… 0, then the binary representation of the number minus 1 must be 0.. 0011.. Student: 1. So this is going to be equal to the number that you subtract from yourself and you’re going to get 0.

Such as:

Therefore, the best solution to the problem is:

public boolean log2(int num){
   return (num & (num - 1)) = =0;
}
Copy the code
#include "iostream"  
using namespace std;  
//声明
bool IsLog2(int num)；
//定义
bool IsLog2(int num)
{
    return (num & (num -1)) == 0;
}
Copy the code

Testing:

int main(int argc, const char * argv[]) {
    std: :cout << "Is it an integer power of 2?" << IsLog2(1) < <endl;
    std: :cout << "Is it an integer power of 2?" << IsLog2(3) < <endl;
    return 0;
}

/ / the resultWhether it is2The integer power of:1 / / is trueWhether it is2The integer power of:0 / / not false
Copy the code

Given an integer, write a function to determine the number of 1’s in the binary representation of the integer (✭✭

The number of 1’s in the binary representation of an integer, assuming that the integer is represented by 32 bits, can be positive or negative or 0, then how many 1’s in this number, we need to consider the problem of sign bit.

I’m sure the reader can think of the most recent basic solution which is to calculate the result by the right shift and the result of 1. If this solution is adopted, then the trap of this problem is that there is a negative number, and if there is a negative number, the flag bit should count as a 1. So when you move to the right you have to move to the right unsigned to get the right solution.

Ps A right shift for a positive number gives the same result as an unsigned right shift. If it is negative, a right shift adds an additional 1 to the left of the binary complement, while an unsigned right shift adds a 0.

So one way to solve this problem is as follows:

public int count1(int n) {
   int res = 0;
   while(n ! =0) {
       res += n & 1;
       n >>>= 1;
   }
   return res;
}
Copy the code
#include "iostream"  
using namespace std;
  
// note that there is no unsigned right shift in C++, so we pass in an unsigned number as params
int count1(unsigned int n){
    int res = 0;
    while(n ! =0){
        res += n & 1;
        n >>= 1;
    }
    return res;
}
Copy the code

Test results:

int main(int argc, const char * argv[]) {
    std: :cout << "The number of ones in binary:" <<  count1(- 1) < <endl;
    std: :cout << "The number of ones in binary:" <<  count1(1) < <endl;
    return 0;
}

/ / the resultIn the binary1The number of:32In the binary1The number of:1
Copy the code

You would certainly pass the interview if you could answer the above questions, but as an exercise, are there any extra solutions? First, the worst-case scenario of the above results may require 32 cycles. So we did a little bit of an example of how to figure out if something is a multiple of 2, and we used n ^ (n-1)==0. Actually, the second solution to this problem could have been done the same way. Why is that? Let’s take a look at the picture above:

Can we see that every time a number is 1 less than itself and then the binary representation of that number is the last 1 bit will be erased. In fact, this is a method that you can only think of when you know this principle, so you don’t have to lament how I can’t think of this, and it’s not so bad to remember this rule and have another idea next time.

Let’s look at the complete diagram for determining how many ones there are in a number:

So we can solve the problem in the following way, so we can reduce the number of moves

public int countA(int n){
   int res = 0;
   while(n ! =0){
       n &= (n - 1);
       res++;
   }
   return res;
}
Copy the code
#include "iostream"  
using namespace std;  
// Pass unsigned integers as above
int countA(unsigned int n){
    int res = 0;
    while(n ! =0){
        n &= (n - 1);
        res++;
    }
    return res;
}
Copy the code

Test results:

int main(int argc, const char * argv[]) {
    std: :cout << "The number of ones in binary:" <<  countA(- 1) < <endl;
    std: :cout << "The number of ones in binary:" <<  countA(1) < <endl;
    return 0;
}

/ / the resultIn the binary1The number of:32In the binary1The number of:1
Copy the code

Find the number that occurs only once in an array where all other numbers occur twice (✭✭ offshore)

This problem is also a survey for a bit operation, but if not familiar with the bit operation of friends may not at all to this aspect, perhaps on the spot directly on the bottom of the number of times to remember the number of times the number of the code. In fact, this problem requires that under the condition that the time complexity is O(n) space complexity is O(1), that solution does not meet the requirements. So let’s think about how to do bitwise operations.

The first thing we should know about binary xor operations is that the xor result is that two bits in binary are equal to 0 and different to 1. So there’s a pattern:

Any integer n that is either or equal to 0 is always equal to n, and a number that is either or to itself is always equal to 0.

One more rule to know:

Multi – number xOR operations follow commutative and associative laws.

The first rule is easy to understand, but the second rule is the key to this question. If we have a variable, eO= 0, then if we go through the list of numbers, if we make each number xor with eO equal to eO ^ num, then the value of eO must be the value of the number that occurred once. Why is that? Here’s an example:

Suppose we have A sequence C, B, D, A, B, C where D occurs only once, then because xor satisfies commutative and associative laws, our process of traversing the xor sequence is equivalent to

eO ^ (A ^ A ^ B ^ B ^ C ^ C ) ^ D = eO ^ 0 ^ D = D
Copy the code

So for any array, if only one number occurs an odd number of times, and all the other numbers occur an euclide, then the xOR result must be the number that occurs an odd number of times.

So the problem can be solved as follows:

Java solution

public int oddTimesNum(int[] arr) {
   int eO = 0;
   for (int cur : arr) {
       eO = eO ^ cur;
   }
   
   return eO;
}
Copy the code

C + + solution

int oddTimesNum(vector<int> arr) {
    int eO = 0;
    for (int cur : arr) {
        eO = eO ^ cur;
    }
    return eO;
}
Copy the code

Testing:

int main(int argc, const char * argv[]) {
  vector<int>  arr = {2.1.3.3.2.1.4.5.4};
  std: :cout << "The number occurring an odd number of times:" << oddTimesNum(arr) <<endl;
  return 0;
}

/ / the resultThe number that occurs an odd number of times:5
Copy the code

An extended version of this problem is how to get two one-occurrence numbers in an array.

Find the two numbers that occur only once in an array where all other numbers occur twice (✭✭✭ offshore)

So let’s think about it the same way, if I have two numbers, eO is equal to a to the b, and the key is how do I get a and B respectively. We should remember that any two numbers that are different can’t have the same bits except for themselves, which means that two numbers a and B that are different must have a 1 in their binary representation. That’s the key.

We can assume that the KTH bit is not 0, so that means that a and B have different values on this one. So what we’re going to do is we’re going to set a number where the KTH bit is 1 and the rest bits are 0 and we’re going to call that rightOne.

EOhasOne = 0 is used to xor through the array, but any values that match rightOne to 0 are ignored. Because the sum equals zero means that this number must be the KTH digit of the two numbers that is not 1. So eOhasOne is the one in A b whose k is equal to 1.

So now there is only one problem to solve, how to find rightOne, here we use the method of matching with its complement, namely int rightOne = eO & (~eO + 1).

To understand the process, consider the following:

Let’s take a look at the final code:

Java write

public void printOddTimesNum(int[] arr) {
   int eO = 0;
   int eOhasOne = 0;

   for (int cur : arr) {
       eO = eO ^ cur;
   }

   int rightOne = eO & (~eO + 1);
   for (int cur : arr) {
       if((rightOne & cur) ! =0) {
           eOhasOne = eOhasOne ^ cur;
       }
   }

   System.out.println("eOhasOne = " + eOhasOne + "" + (eOhasOne ^ eO));
}
Copy the code

C + + written

void printOddTimesNum(vector<int> arr) {
    int eO = 0;
    int eOhasOne = 0;
    
    for (int cur : arr) {
        eO = eO ^ cur;
    }
    
    int rightOne = eO & (~eO + 1);
    
    for (int cur : arr) {
        if((cur & rightOne) ! =0) { eOhasOne = eOhasOne ^ cur; }}std: :cout<<"A number that occurs once." << eOhasOne << endl;
    std: :cout<<"Two occurrences of one." << (eO ^ eOhasOne) <<endl;
}
Copy the code

Testing:

int main(int argc, const char * argv[]) {
    vector<int>  arr1 = {2.1.3.3.2.1.4.5};
    printOddTimesNum(arr1);
    return 0;
} 

/ / the result:A appear1The number of times5Two appear1The number of times4
Copy the code

Reference:

“Jian Finger Offer Second Edition” “Programmer code Interview Guide – Cheng Yun Zuo”

Welcome to follow my wechat public number, receive first-hand technical dry goods