當前位置：首頁 > 编程语言 > php >内容正文

php

PHP算法学习（5）位运算

發布時間：2023/12/31 php 24 豆豆

生活随笔收集整理的這篇文章主要介紹了 PHP算法学习（5）位运算小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

svn地址：svn://gitee.com/zxadmin/live_z?

2019年2月14日11:38:46

<?php/** 位運算學習筆記* * 1，php所有的數都是有符號的，無法指定是否是無符號的 unsign* 2.計算機底層運算都是補碼運算的* 3，0反碼，補碼都是0* 4，正數的反碼，補碼全都一樣* 5，二進制的最高位是符號位，0是正數，1是負數* 6，負數的反碼符號位不變，其他未取反* 7，負數的補碼等于反碼+1* 8，負數(取反)=》反碼 +1 =》補碼* 9，補碼-1=》反碼(取反)=》負數* 10，右移低位溢出，符號位不變，并用符號位補溢出的到位* 11，符號位不變低位補0* * 32位的1表示是 31個0+1* 64位的1表示是 63個0+1* 參考 http://php.net/manual/zh/function.decbin.php* 測試： print_r(decbin(-50)) 32 位* $a & $b And(按位與) 將把 $a 和 $b 中都為 1 的位設為 1。$a | $b Or(按位或) 將把 $a 和 $b 中任何一個為 1 的位設為 1。$a ^ $b Xor(按位異或) 將把 $a 和 $b 中一個為 1 另一個為 0 的位設為 1。~ $a Not(按位取反) 將 $a 中為 0 的位設為 1，反之亦然。$a << $b Shift left(左移) 將 $a 中的位向左移動 $b 次(每一次移動都表示“乘以 2”)。$a >> $b Shift right(右移) 將 $a 中的位向右移動 $b 次(每一次移動都表示“除以 2”)。??右移 >>：將二進制進行右移，低位丟掉，高位補零符號位不變。??左移 <<：將二進制進行左移，低位補零，高位丟掉符號位不變。----------------------------------------------------------------------------------------------------------------------&按位與如果兩個相應的二進制位都為1，則該位的結果值為1，否則為0|按位或兩個相應的二進制位中只要有一個為1，該位的結果值為1^按位異或若參加運算的兩個二進制位值相同則為0，否則為1~取反~是一元運算符，用來對一個二進制數按位取反，即將0變1，將1變0<<左移用來將一個數的各二進制位全部左移N位，右補0>>右移將一個數的各二進制位右移N位，移到右端的低位被舍棄，對于無符號數，高位補0要使用八進制表達，數字前必須加上 0(零)。要使用十六進制表達，數字前必須加上 0x。要使用二進制表達，數字前必須加上 0b。Example #1 整數文字表達$a = 1234; // 十進制數$a = -123; // 負數$a = 0123; // 八進制數 (等于十進制 83)$a = 0x1A; // 十六進制數 (等于十進制 26)$a = 0b11111111; // 二進制數字 (等于十進制 255)** printf() - 輸出格式化字符串, using %b, %032b or %064b as the format*/final class BitOperation {/** 注意：位運算只能支持int類型*/public static $format = true;//計算原碼吧數字十進制轉換成二進制，并補充字符到系統的位數指定長度的原碼public static function OriginalCode(int $number) {$OriginalCode = self::DecimalToBinary($number);return $OriginalCode;}//計算反碼public static function InverseCode(int $number) {$OriginalCode = self::DecimalToBinary($number); // p($OriginalCode);$InverseCode = '';if ($number >= 0) {return $OriginalCode;} else {$array = str_split($OriginalCode);foreach ($array as $k => &$v) {//符號位不變if ($k == 0) {continue;}//1變0 0變1if ($v == '0') {$v = 1;} elseif ($v == '1') {$v = 0;}}foreach ($array as $k1 => $v1) {$InverseCode .= $v1;}}return $InverseCode;}//計算補碼public static function ComplementCode(int $number) {$InverseCode = self::InverseCode($number);$ComplementCode = '';if ($number >= 0) {return $InverseCode;} else { // $array = str_split($InverseCode); // for ($index = (count($array) - 1); $index >= 0; $index--) { // $str .= $return[$index]; // }/** 不好直接計算*/return decbin($number);}return self::Format($ComplementCode);}/** 十進制轉二進制* 或者直接借用 decbin函數直接轉換效率更高，這次是學習代碼，為了寫清楚原理* 注意這里的效率慢其實只要 self::PhpDigit()函數造成的，如果定義死計算是64,32效率快很多倍*/public static function DecimalToBinary(int $number) {$return = [];$abs = abs($number);while ($abs > 0) {$return[] = $abs % 2;$abs = $abs >> 1;}$str = '';for ($index = (count($return) - 1); $index >= 0; $index--) {$str .= $return[$index];}$plus_or_minus = $number >= 0 ? true : false;return self::FillingLength($str, $plus_or_minus);}//優化版十進制轉二進制public static function DecimalToBinaryFast(int $number) {$return = [];$str = decbin(abs($number));$plus_or_minus = $number >= 0 ? true : false;return self::FillingLength($str, $plus_or_minus);}/** $plus_or_minus true + false -*/public static function FillingLength($string = null, $plus_or_minus = true) {$length = self::PhpDigit();$res = '';if ($plus_or_minus) {$res = str_pad($string, $length, '0', STR_PAD_LEFT);} else {$res = str_pad($string, $length - 1, '0', STR_PAD_LEFT);$res = '1' . $res;}return $res;}public static function Format($string = null, $separation = 4) {if (mb_strlen($string) == 32 || mb_strlen($string) == 64) {$re = chunk_split($string, $separation, ".");$re = trim($re, '.');$re = str_replace('.', ' ', $re);return $re;} else {return $string;}}/** 你的系統是64，但是你運行的php版本不一定是64特別是在windows上*/public static function PhpDigit() {$phpinfo = self::PhpInfoArray();if (strtolower($phpinfo['General']['Architecture']) == 'x86') {return 32;} else {return 64;}}public static function PhpInfoArray() {ob_start();phpinfo();$info_arr = array();$info_lines = explode("\n", strip_tags(ob_get_clean(), "<tr><td><h2>"));$cat = "General";foreach ($info_lines as $line) {// new cat?preg_match("~<h2>(.*)</h2>~", $line, $title) ? $cat = $title[1] : null;if (preg_match("~<tr><td[^>]+>([^<]*)</td><td[^>]+>([^<]*)</td></tr>~", $line, $val)) {$info_arr[trim($cat)][trim($val[1])] = trim($val[2]);} elseif (preg_match("~<tr><td[^>]+>([^<]*)</td><td[^>]+>([^<]*)</td><td[^>]+>([^<]*)</td></tr>~", $line, $val)) {$info_arr[trim($cat)][trim($val[1])] = array("local" => trim($val[2]), "master" => trim($val[3]));}}return $info_arr;}public static function CountIntOne_1(int $n) {//計算一個十進制數轉換為二進制數中‘1’的個數//例如十進制11 = 二進制1011，則結果是3個1//解題思路：利用 n & (n - 1) 可以將最后一個1變0//xxxx1000 & (xxxx1000 - 1) = xxxx1000 & xxxx0111 = xxxx0000// 1011 & (1011 - 1) = 1011 & 1010 = 1010//直到最后一個1被與為0，得出結果$r = 0;while ($n != 0) {$r++;$n &= ($n - 1);}return $r;}/** */public static function CountIntOne_2(int $n) {/** 十進制轉二進制過程計算余數* 1%2 = 1 1 2~0* 2%2 = 0 10 2~1* 3%2 = 1 11 2~0 + 2~1* 4%2 = 0 100 2~3* 5%2 = 1 101 2~0 + 2~3 5%2 = 1 1%2 =1* * 利用的是數學計算過程，因為是對2求余，所有有可能是0 1 兩個元素，0就是二進制位數0 1就是二進制位數的1*/$r = 0;while ($n > 0) {$t = $n % 2;$n = $n >> 1;if ($t == 1) {$r++;}}return $r;}/*** @param int $a* @param int $b* @return int $a + $b;*/public static function add(int $a, int $b): int {$sum = $a;while ($b) {$sum = $a ^ $b; // 不考慮進位$b = ($a & $b) << 1; // 只考慮進位$a = $sum;}return $sum;}/*** 相反數 <= 二進制表達取反+1(補碼)* @param int $n* @return int*/public static function negateNumber(int $n): int {return self::add(~$n, 1);}/*** a-b = a + (-b)* @param int $a* @param int $b* @return int*/public static function minus(int $a, int $b): int {return self::add($a, self::negateNumber($b));}/*** @param int $a* @param int $b* @return int $a * $b*/public static function multiple(int $a, int $b): int {$res = 0;while ($b) {if (($b & 1)) {$res = self::add($res, $a);}$a <<= 1;$b >>= 1;}return $res;}// public static function isNegative(int $n): bool { // return $n < 0; // }//-1就是負數， 0就是正數直接右移31位即可看最左邊第一個public static function isNegative(int $n) {return $n >> 31;}public static function maxInt(int $n) {return PHP_INT_MAX;}//交換兩個int數public static function swap(int &$x, int &$y) {$x ^= $y;$y ^= $x;$x ^= $y;}//交換兩個int數,注意返回intpublic static function average(int $x, int $y) {return ($x & $y) + (($x ^ $y) >> 1);}//判斷奇偶public static function isOddEven(int $n) {return $n & 1;}public static function abs($x) {$y = $x >> 31;return ($x ^ $y) - $y;}/*** a/b a = MIN_INTEGER, b!=MIN_INTEGER ?* @param int $a* @param int $b* @return int*/public static function p(int $a, int $b): int {$x = self::isNegative($a) ? self::negateNumber($a) : $a;$y = self::isNegative($b) ? self::negateNumber($b) : $b;$res = 0;for ($i = 31; $i > -1; $i = self::minus($i, 1)) {if (($x >> $i) >= $y) {$res |= (1 << $i);$x = self::minus($x, $y << $i);}}return self::isNegative($a) ^ self::isNegative($b) ? self::negateNumber($res) : $res;}/*** @return int $a / $b*/public static function pide(int $a, int $b): int {if ($b === 0) {throw new RuntimeException("pisor is 0");}if ($a === self::MIN_INTEGER && $b === self::MIN_INTEGER) {return 1;} else if ($b === self::MIN_INTEGER) {return 0;} else if ($a === self::MIN_INTEGER) {$res = self::p(self::add($a, 1), $b);return self::add($res, self::p(self::minus($a, self::multiple($res, $b)), $b));} else {return self::p($a, $b);}}}

其實位運算的基礎能力對于算法是很重要的，特別是在優化算法的時候，如果代碼有問題進群反饋

參考：

https://www.cnblogs.com/kingkoo/p/6117690.html

https://www.cnblogs.com/XuYiHe/p/4966309.html

https://www.cnblogs.com/luowei010101/archive/2011/11/24/2261575.html

https://www.cnblogs.com/qiaogaojian/p/5873105.html

https://www.cnblogs.com/kiven-code/archive/2012/09/15/2686922.html

?https://blog.csdn.net/lmhacm/article/details/77287571