The most basic unit of operation in a computer is a byte. A byte consists of eight bits. Each bit can only store a 0 or a 1. All data is stored and processed in a computer using binary codes, ones and zeros.

This is an attempt to implement four operations using bit operations in PHP. First, some basic concepts are introduced:

Source code: Use the highest bit as a sign bit (0 for positive, 1 for negative), and the other digits represent the absolute value of the value itself

Inverse code: positive and inverse code is the same as the original code; If it’s negative, the sign bit stays the same, and the rest of it is reversed

Complement: the positive complement is the same as the original; The negative complement is the inverse plus 1

Numbers in computers are stored in the form of complement

___________ addition

In binary, only 0 and 1 are carried. 0 + 0 and 0 + 1 are not carried, but 1 + 1 is carried. So, the first thing to do is to get the sum of the bits that don’t need to be carried. And then I’m going to do and, and I’m going to get 1 when both of these two digits are 1. Therefore, if the result of the and operation is greater than 0, it indicates that carry is required. At this time, the result of the and operation is moved 1 bit to the left, and the result of the or operation is repeated until the result of the and operation is 0.


      

    function add($summand, $addend)
    {
        $sum = $summand ^ $addend;
        // Determine the carry
        $carry = $summand & $addend;

        while ($carry <<= 1) {
            $summand = $sum;
            $addend = $carry;

            $sum = $summand ^ $addend;
            $carry = $summand & $addend;
        }

        return $sum;
    }

Copy the code

This subtraction

Subtraction can be thought of as addition where the subtraction is negative. For example, 2 -1 can be thought of as 2 + (-1).


      
    require 'addition.php';

    function subtract($minuend, $subtrahend)
    {
        // First find the subtraction complement, and then sum
        $subtrahend = add(~$subtrahend, 1);

        return add($minuend, $subtrahend);
    }
Copy the code

3. The multiplication

Multiplication can also be seen as a variant of addition; for example, m * n can be seen as the result of adding n m’s. But there are faster ways to do multiplication using bits. For example, the binary representation of 3 * 10:3 is 0011 and the binary representation of 10 is 1010

1 1 0 0

Times 1, 0, 1, 0

— — — — — —

            0 0 0 0

0, 0, 1, 1, 0

0 0 0 0 0 0 0

0 0 1 1 0 0 0 0 0

— — — — — —

0 0 1 1 1 1 1 0

As can be seen from the figure above, the result of the multiplication is: When the bit value of the multiplier is 1, the multiplicand is shifted to the left by the corresponding bit, and the results obtained by the bit shift are added up to the final result.


      
    require 'addition.php';

    function multiply($multiplicand, $multiplicator)
    {
        // Check the sign bit
        $flag = ($multiplicand ^ $multiplicator) < 0 ? false : true;
        // Take the absolute value of the multiplicand
        $multiplicand = $multiplicand < 0 ? add(~$multiplicand, 1) : $multiplicand;
        $multiplicator = $multiplicator < 0 ?  add(~$multiplicator, 1) : $multiplicator;

        $product = 0;
        $multiplicator = decbin($multiplicator);
        $length = strlen($multiplicator);

        for ($i = 0; $i < $length; $i ++) {
            if ($multiplicator[$i]) {
                $product += $multiplicand << $length - $i - 1; }}if (! $flag) {
            $product = add(~$product, 1);
        }

        return $product;
    }
Copy the code

4. Division

Like multiplication, division can be thought of as how many divisor can be subtracted from the dividend.


      
    require 'addition.php';

    function divide($dividend, $divisor)
    {
        // Check the sign bit
        $flag = ($dividend ^ $divisor) < 0 ? false : true;
        // Get the dividend sign bit
        $dividend_flag = $dividend < 0 ? false : true;
        // Take the absolute value
       $dividend = $dividend < 0 ? add(~$dividend, 1) : $dividend;
       $divisor = $divisor < 0 ? add(~$divisor, 1) : $divisor;

       $quotient = 0;
       $remainder = 0;

       if ($dividend < $divisor) {
           // The dividend is less than the divisor
           $remainder = $dividend;
           return 'quotient = ' . $quotient . ' remainder = ' . $remainder;
       }

       while ($dividend >= $divisor) {
           $i = 0;
           $mul_divisor = $divisor;

           while ($dividend >= ($mul_divisor << 1)) {
               $i ++;
               $mul_divisor <<= 1;
           }

           $dividend -= $mul_divisor;
           $quotient += 1 << $i;
       }

      $remainder = $dividend;
      if (! $flag) {
          $quotient = add(~ $quotient, 1);
      }
      if (! $dividend_flag) {
          $remainder = add(~$remainder, 1);
      }

      return 'quotient = ' . $quotient . ' remainder = ' . $remainder;
    }Copy the code

The above.

It should be noted that the above code was successfully implemented without taking into account data overflow. Two very large numbers add up and you can overflow; Positive minus negative numbers can also overflow; If you multiply two large numbers, you will overflow; Any number divided by 0 will overflow.