Interview question: Explanation of the implementation idea of ​​reversing binary bits (PHP general version)

This is an interview question, and some students expressed that they could not understand it. It is not difficult to give you a simple training, but to write a perfect comparison tests the basic skills, and also requires some logical thinking ability. Since the students' direction is PHP, then I will use PHP to explain it. At the same time, it also tells everyone that learning PHP is not It is said that as long as you can write two sentences of echo "hello world", or loop output to a web page, you can call PHP.

Here are a few pieces of knowledge: (Recommended learning: PHP video tutorial)

##1 , a number occupies one byte, that is, 8 bits

For example, the decimal number 1 is expressed in binary on the computer as 00000001 (If you forget to convert decimal to binary, please Baidu, this Forget that you can’t understand the following~~~)

You can use

echo bindec("00000001");   //bindec函数可以让你体会到 二进制和10进制之间的 骚转换<br/>

#2 in PHP. Add decimal numbers 1 1 =2 (This tip is very important~~, Carefully understand)

Use binary to do it with displacement

Answer: 00000010 This is exactly 2 (2 raised to the power of 1)

What about decimal 2 1=3?

Answer: 00000011 This is exactly 3 (2 to the power of 1 2 to the power of 0 = 2 1 = 3)

Then What about decimal 3 1=4?

Answer: 00000100 This is 4 (2 to the power of 2)

So what about decimal 4 1=5?

Answer: 00000101 This guy is 4 (2 to the power of 2, 2 to the power of 0 = 4 1 = 5)

Start to solve the problem

Suppose there is a binary number 00000101. Now we need to turn it upside down and turn it into 10100000. How to play?

The answers are all over the Internet, so let’s talk about the ideas below:

1. First, there must be 2 variables,

1 ) The temporary variable is called $xxoo, and the initial value is 0 (decimal), which is 00000000

in binary. 2) The original value variable is called $shit, which is 00000101 to be processed

2. 3 steps

1) Move $xxoo one bit to the left

2) Determine whether the last digit of the binary value of $shit is 1. If so, give $ The decimal value of xxoo is increased by 1. It is very important to regard it as binary and change 00000000 into 00000001. Otherwise, the initial value of $xxoo is 00000000. This is shifted by p. . . They are all zero, so how to determine whether the last bit of the binary number is 1? You have to judge by intercepting strings or regular expressions (not impossible)

Answer: Just perform a logical AND operation on the original value and 1 (that is, 00000001) (1&1 is 1, 1&0 or 0&1 are always 0)

3) Next, move $shit to the right by 1 position

1) If it was originally 00000101, it becomes 00000010 after the move ( That is to say, $xxoo and shit are moved at the same time, one to the left and one to the right. When the last bit of shit is 1, we can judge it, so the last bit of $xxoo is also set to 1, so that both xxoo and shit can be realized. Synchronization and reverse)

Repeat the above process 8 times to get 10100000

The complete code is as follows

function rev($n)<br/>{<br/>    $xxoo = 0;<br/>    for ($i = 0; $i < 8; $i++) {<br/>        $xxoo = $xxoo << 1;<br/>        if (($n & 1) == 1) {<br/>            $xxoo++;<br/>        }<br/>        $n = $n >> 1;<br/>    }<br/>    return $xxoo;<br/>}<br/>echo decbin(rev(5));<br/>

But be careful The thing is, the above function supports 1-byte numbers (only supports 8 digits)

The online interview questions are 32-bit numbers, and the following code supports

general digits (this code is not available online~~~). Let’s think about it and understand it, so I won’t explain too much. You need to have some PHP code skills:

function rev($n)<br/>{<br/>    $num=intval(strlen(decbin($n))/8); //整除 8<br/>    if($num==0)<br/>        $bitLen=8;//最小8位<br/>    else<br/>    {<br/>        if((strlen(decbin($n)) % 8)>0)<br/>            $bitLen=($num+1)*8;<br/>        else<br/>            $bitLen=$num*8;<br/>    }<br/>    echo “原始值二进制:”.str_pad(decbin($n),$bitLen,’0′,STR_PAD_LEFT).”<br/>”;<br/>    $xxoo = 0;<br/>    for ($i = 0; $i < $bitLen; $i++) {<br/>        $xxoo = $xxoo << 1;<br/>        if (($n & 1) == 1) {<br/>            $xxoo++;<br/>        }<br/>        $n = $n >> 1;<br/>    }<br/>    echo “反转后值二进制:”.str_pad(decbin($xxoo),$bitLen,’0′,STR_PAD_LEFT).”<br/>”;<br/>    return $xxoo;<br/>}<br/>

Call test

echo rev(4);<br/>echo rev(43261596);<br/>

Result

原始值二进制:00000100<br/>反转后值二进制:00100000<br/>32原始值二进制:00000010100101000001111010011100<br/>反转后值二进制:00111001011110000010100101000000<br/>964176192<br/>

The above is the detailed content of Interview question: Explanation of the implementation idea of ​​reversing binary bits (PHP general version). For more information, please follow other related articles on the PHP Chinese website!