c binary inversion method

The original problem

An integer can be represented in base 2. Give as many ways as possible to invert base 2. For example, the reverse order of 10000110 11011000 is 00011011 01100001

Analysis of the

They're saying it's an integer, and they're going to invert its base two. It's not a string of 01, or an array of 01. So how do we solve this problem? The methods are still more, some in the rules, some very clever. We should master the method of the rule and see more ingenious methods. Slowly, can lift 1 anti 3, in the face of new problems, be able to think.

The most direct way

The direct method is easy to think of: have the following code:

 The direct method is easy to think of: have the following code:  int v = 111;
int r = v;
int s = 32; 
for (; 0 != v; v >>= 1) { 
    r <<= 1;
    r |= v & 1;
    s--;
}
r <<= s;
System.out.println(r);

The code is easy to understand. Take the lowest bit of v as the highest bit of r. v moves 1 bit to the right every time it takes the lowest position. r moves one bit to the left for each bit determined. Record how many bits have been moved at the same time, and eventually make up.

By looking up a table

In the case of a bit operation, the total number of bits is often limited. For example, in this case, we can think of 32 bits. This brings us 1 with the space for time solution idea: looking up the table method. The number of digits is fixed, you can apply for space and store the pre-calculated results. When calculating other results, you can look up the table.

32-bit is still too big for a table lookup. So if we narrow it down, we have 32 bit, so we have 4 byte. Each byte 8bit can represent an integer from 0 to 255. You can save the 256 integers by requesting a 256-size array, the integers after the reverse order of 2. Then a 32-bit integer, divided into four byte, each 1 byte look-up table get reverse integers: r1, r2, r3, r4. Joining together in r4r3r2r1 order 2 base is the result of the final solution.

So that's one way to think about it, and you can go ahead and think about it and try it.

Ingenious method

Here we will focus on this ingenious method, the core idea is: divide and conquer. That is:

The & # 8226; The reverse order 32-bit decomposes into two reverse order 16-bit
The & # 8226; Inversions of 16 bits are decomposed into two inversions of 8 bits
The & # 8226; Inversions of 8 bits are decomposed into two inversions of 4 bits
The & # 8226; Inversions of four bits are decomposed into two inversions of two bits
The last 1-2 - bit inversion, direct exchange can be. That's the termination condition for divide-and-conquer recursion. However, in the above procedure, the technique of in-place operation has not been applied. According to the idea of dynamic programming, we can solve this problem from the bottom up:

The & # 8226; Every 2 bits is a group, exchange, complete the 2 bit inversion
The & # 8226; Every 4 bits is in 1 group. The first 2 bits are exchanged with the last 2 bits to complete 4 bit inversion
The & # 8226; Each 8-bit group is 1, and the first 4 bits and the last 4 bits are swapped to complete the 8-bit inversion
The & # 8226; Every 16 bits is a group. The first 8 bits and the last 8 bits are exchanged to complete the 16 bit inversion
Two groups of 16 - bit exchange, complete 32 - bit inversion

To elaborate on the above process, let's take the 16-bit example: 10000110 11011000

1 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1

After 4 steps, the reverse order is completed. By extension, the total time complexity is O(logn), which is the number of bits in base 2. This method can be generalized to any bit.

The sample code is as follows:

int v =111;
v =((v > > 1)&0x55555555)|((v &0x55555555) < < 1);
v =((v > > 2)&0x33333333)|((v &0x33333333) < < 2);
v =((v > > 4)&0x0F0F0F0F)|((v &0x0F0F0F0F) < < 4);
v =((v > > 8)&0x00FF00FF)|((v &0x00FF00FF) < < 8);
v =( v > > 16)|( v < < 16); System. out. println (v); The above idea is understood, the code is not difficult to understand. So for example, in line 2, you take an even digit in the front, an odd digit in the back, an odd digit to the left, an even digit to the right, and then you take or, you swap the odd and even digits. So that's step 1.

There are many clever ways to do bit-based 1's. You can do your own research and share more interview questions later.

[finished analysis]