A brief discussion on how to use bit operations to implement addition, subtraction, multiplication and division operations in PHP

How does PHP use bit operations to implement four arithmetic operations? This article will introduce to you how to use bit operations to implement the four arithmetic operations (addition, subtraction, multiplication, and division) in PHP.

#The most basic operating unit of a computer is a byte. A byte consists of 8 bits, and a bit can only store a 0 or a 1. All data in the computer is stored and operated in binary, that is, the encoding of 1 and 0.

This time I try to use bit operations to implement four arithmetic operations in PHP. First, I introduce some basic concepts:

Original code: use the highest bit as the sign bit (0 means positive, 1 means negative), The other digits represent the absolute value of the value itself

The complement code: the complement code for positive numbers is the same as the original code; if it is a negative number, the sign bit remains unchanged, and the remaining digits are complemented

Code: Positive number's complement is the same as the original code; negative number's complement is the inverse code plus 1

Numbers in computers are stored in the form of 's complement

⒈ Addition

There are only 0 and 1 in binary. Neither 0 0 nor 0 1 requires a carry, but 1 1 requires a carry. Therefore, first obtain the result of adding those bits that do not require carry through the or operation. Then perform and operations. When the two added bits are both 1, the result is 1. Therefore, if the result of the AND operation is greater than 0, it means that a carry is required. At this time, the result of the AND operation is shifted to the left by 1 bit. At this time, the result of the left shift is combined with the result of the OR operation and the above operation process is repeated until the result of the AND operation is The result is 0.

<?php

    function add($summand, $addend)
    {
        $sum = $summand ^ $addend;
        //  判断进位
        $carry = $summand & $addend;

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

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

        return $sum;
    }

⒉ Subtraction

Subtraction can be regarded as addition with a negative subtraction, for example, 2 - 1 can be regarded as 2 (- 1).

<?php
    require &#39;addition.php&#39;;

    function subtract($minuend, $subtrahend)
    {
        //  先求得减数的补码，然后求和
        $subtrahend = add(~$subtrahend, 1);

        return add($minuend, $subtrahend);
    }

⒊ Multiplication

Multiplication can also be regarded as a variant of addition, for example, m * n can be regarded as n The result of adding m. But there is a faster way to implement multiplication using bitwise operations. For example, 3 * 10: The binary representation of 3 is 0011, and the binary representation of 10 is 1010

        0 0 1 1

×     1 0 1 0

—— ——————————

                                                                                                                                                  0 1 1 0 0 0

——————————————

0 0 1 1 1 1 0

From the above picture you can It can be seen that the result of the multiplication calculation is: when the value of the multiplier's bit is 1, the multiplicand is shifted to the left by the corresponding number of digits, and finally the results obtained after the bitwise left shift are added to the final result. .

<?php
    require &#39;addition.php&#39;;

    function multiply($multiplicand, $multiplicator)
    {
        // 判断符号位
        $flag = ($multiplicand ^ $multiplicator) < 0 ? false : true;
        //  被乘数和乘数取绝对值
        $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;
    }

⒋ Division

Similar to multiplication, division can be seen as how many divisors can be subtracted from the dividend.

<?php
    require &#39;addition.php&#39;;

    function divide($dividend, $divisor)
    {
        //  判断符号位
        $flag = ($dividend ^ $divisor) < 0 ? false : true;
        //  取得被除数符号位
        $dividend_flag = $dividend < 0 ? false : true;
        // 取绝对值
       $dividend = $dividend < 0 ? add(~$dividend, 1) : $dividend;
       $divisor = $divisor < 0 ? add(~$divisor, 1) : $divisor;

       $quotient = 0;
       $remainder = 0;

       if ($dividend < $divisor) {
           // 被除数小于除数的情况
           $remainder = $dividend;
           return &#39;quotient = &#39; . $quotient . &#39; remainder = &#39; . $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 &#39;quotient = &#39; . $quotient . &#39; remainder = &#39; . $remainder;
    }

and above.

It should be pointed out that the above code does not consider data overflow when it is successfully implemented.

The addition of two very large numbers may overflow; subtracting a positive number from a negative number may also overflow; the multiplication of two large numbers may also overflow; any number divided by 0 may overflow.

Recommended learning: "

PHP Video Tutorial

"

The above is the detailed content of A brief discussion on how to use bit operations to implement addition, subtraction, multiplication and division operations in PHP. For more information, please follow other related articles on the PHP Chinese website!