PHP shift operation, shift operation study notes_PHP tutorial-PHP Tutorial-php.cn

The following are some commonly used study notes on PHP shift operations and shift operations. I hope the article will bring value to all students.

Bit operation application tips

To clear the bit, use AND, a certain position is available or

To negate and swap, easily use XOR

Shift operation

Point 1 They are both binary operators, both operation components are integers, and the result is also an integer.

2 "<<" Shift left: Fill the vacated bits on the right with 0, and the bits on the left will be squeezed out from the beginning of the word, and its value is equivalent to multiplying by 2.

3 ">>"Shift right: The bit on the right is squeezed out. For the empty bits moved out from the left, if it is a positive number, the empty bit is filled with 0. If it is a negative number, it may be filled with 0 or 1, depending on the computer system used.

4 ">>>" operator, the bits on the right are squeezed out, and the vacancies shifted out on the left are filled with 0.

Application of bitwise operators (source operand s mask mask)

(1) Bitwise AND-- &

1 Clear specific bits (specific bits in mask are 0, other bits are 1, s=s&mask)

2 Take the specified bit in a certain number (the specific position in the mask is 1, other bits are 0, s=s&mask)

(2) Bitwise OR-- |

Often used to set certain bits of the source operand to 1, leaving other bits unchanged. (Specific position in mask is 1, other bits are 0 s=s|mask)

(3) Bit XOR-- ^

1 inverts the value of a specific bit (the specific position in the mask is 1, other bits are 0 s=s^mask)

2 Do not introduce the third variable, exchange the values of the two variables (assume a=a1,b=b1)

Target Operation Status after operation

a=a1^b1 a=a^b a=a1^b1,b=b1

b=a1^b1^b1 b=a^b a=a1^b1,b=a1

a=b1^a1^a1 a=a^b a=b1,b=a1

Two’s complement arithmetic formula:

-x = ~x + 1 = ~(x-1)

~x = -x-1

-(~x) = x+1

~(-x) = x-1

x+y = x - ~y - 1 = (x|y)+(x&y)

x-y = x + ~y + 1 = (x|~y)-(~x&y)

x^y = (x|y)-(x&y)

x|y = (x&~y)+y

x&y = (~x|y)-~x

x==y: ~(x-y|y-x)

x!=y: x-y|y-x

x< y: (x-y)^((x^y)&((x-y)^x))

x<=y: (x|~y)&((x^y)|~(y-x))

x< y: (~x&y)|((~x|y)&(x-y))//Unsigned x,y comparison

x<=y: (~x|y)&((x^y)|~(y-x))//Unsigned x, y comparison

Application examples

(1) Determine whether the int type variable a is an odd number or an even number

a&1 = 0 even number

a&1 = 1 odd number

(2) Take the k-th bit of int type variable a (k=0,1,2...sizeof(int)), that is, a>>k&1

(3) Clear the k-th bit of int type variable a to 0, that is, a=a&~(1<

(4) Set the k-th position of int type variable a to 1, that is, a=a|(1<

(5) The int type variable is circularly shifted to the left k times, that is, a=a<>16-k (assuming sizeof(int)=16)

(6) The int type variable a is cyclically shifted to the right k times, that is, a=a>>k|a<<16-k (assuming sizeof(int)=16)

(7) Average of integers

For two integers x, y, if you use (x+y)/2 to calculate the average, overflow will occur, because x+y may be greater than INT_MAX, but we know that their average will definitely not overflow. , we use the following algorithm:

int average(int x, int y) //Return the average of X, Y

{

return (x&y)+((x^y)>>1);

}

(8) Determine whether an integer is a power of 2. For a number x >= 0, determine whether it is a power of 2

boolean power2(int x)

{

return ((x&(x-1))==0)&&(x!=0);

}

(9) Exchange two integers without temp

void swap(int x , int y)

{

x ^= y;

y ^= x;

x ^= y;

}

(10) Calculate absolute value

int abs( int x )

{

int y ;

y = x >> 31 ;

return (x^y)-y ; //or: (x+y)^y

}

(11) Modulo operation is converted into bit operation (without overflow)

a % (2^n) is equivalent to a & (2^n - 1)

(12) Multiplication operations are converted into bit operations (without overflow)

a * (2^n) is equivalent to a<< n

(13) The division operation is converted into a bit operation (without overflow)

a / (2^n) is equivalent to a>> n

Example: 12/8 == 12>>3

(14) a % 2 is equivalent to a & 1

(15) if (x == a) x= b;

else x= a;

Equivalent to x= a ^ b ^ x;

(16) The opposite of x is expressed as (~x+1)

Finally add some information about binary shift operation

PHP is mainly designed for text operations. In fact, PHP is not suitable for mathematical operations and its efficiency is not high. However, because there is something in this project that must use binary displacement operations, I encountered some troubles in PHP.

Because PHP only has 32-bit signed integers, no 64-bit long integers, and no unsigned integers. The range of its integer type is -231-1~231. Anything outside this range will be interpreted as a floating point number. Therefore, 0xFFFFFFFF, printed directly, displays 4294967295, and 232:

>> 0xFFFFFFFF
4294967295
>> gettype(0xFFFFFFFF)
'double'

In a 32-bit signed integer, 0xFFFFFFFF should represent -1:

>> (int)0xFFFFFFFFF
-1

PHP does not support the binary shift operation of floating point numbers. If it is to be performed, it will be converted to an integer first, and the final result will also be returned as an integer:

>> 1 << 31
-2147483648
>> 1 << 30
1073741824
>> 1 << 32
1
>> 0xFFFFFFFF >> 1
-1

At the same time, PHP's right shift operation will fill the sign bit in the high bits, and PHP does not provide a Java-like >>> to force filling of 0:

>> 1 << 32
1
>> 0xFFFFFFFF >> 1
-1
>> 0xFFFFFFFF >> 2
-1
>> 0xFFFFFFFF >> 3
-1
>> 0xFFFFFFFF >> 31
-1

How to solve this problem? I have considered using the BCMath math function library to directly process integers represented by strings, or GMP/BigInt extensions. But I think since I am using strings, I can be more thorough with strings, convert the numbers into 32 binary strings, then manually fill in 0s, and finally convert them back.

I don’t know if anyone has a better method, please tell me.

The code is as follows:
Download the code directly: shift.php
(In addition, the code can actually be expanded to any binary bit shift operation, but I did not do it here)

PHP

代码如下

复制代码

/**
* 无符号32位右移
* @param mixed $x 要进行操作的数字，如果是字符串，必须是十进制形式
* @param string $bits 右移位数
* @return mixed 结果，如果超出整型范围将返回浮点数
*/
function shr32($x, $bits){
// 位移量超出范围的两种情况
if($bits <= 0){
return $x;
}
if($bits >= 32){
        return 0;
    }
    //转换成代表二进制数字的字符串
    $bin = decbin($x);
    $l = strlen($bin);
    //字符串长度超出则截取底32位，长度不够，则填充高位为0到32位
    if($l > 32){
        $bin = substr($bin, $l - 32, 32);
    }elseif($l < 32){
$bin = str_pad($bin, 32, '0', STR_PAD_LEFT);
}
//取出要移动的位数，并在左边填充0
return bindec(str_pad(substr($bin, 0, 32 - $bits), 32, '0', STR_PAD_LEFT));
}
/**
* 无符号32位左移
* @param mixed $x 要进行操作的数字，如果是字符串，必须是十进制形式
* @param string $bits 左移位数
* @return mixed 结果，如果超出整型范围将返回浮点数
*/
function shl32 ($x, $bits){
// 位移量超出范围的两种情况
if($bits <= 0){
return $x;
}
if($bits >= 32){
        return 0;
    }
    //转换成代表二进制数字的字符串
    $bin = decbin($x);
    $l = strlen($bin);
    //字符串长度超出则截取底32位，长度不够，则填充高位为0到32位
    if($l > 32){
        $bin = substr($bin, $l - 32, 32);
    }elseif($l < 32){
        $bin = str_pad($bin, 32, '0', STR_PAD_LEFT);
    }
    //取出要移动的位数，并在右边填充0
    return bindec(str_pad(substr($bin, $bits), 32, '0', STR_PAD_RIGHT));
}