位运算符及PHP中位运算的应用笔记

发表评论     2,470 人阅读

一、逻辑运算符

正式说位运算符之前，先简单提一下逻辑运算符。分3个角度：
0、数学上
记得高中数学讨论复合命题的时候，使用过基本的逻辑运算符
“非”（¬）、”与”（∧）、”或”（∨）、”条件”（→）以及”双条件”（↔）

大学离散数学中讨论复合命题的时候，出现过异或逻辑符
p ⊕ q p 异或 q p、q 真值相同为假，相异为真

1、集成电路
继承电路的逻辑门中出现过异或，讨论的是高低电平。
A ⊕ B 只有其中一个输入为高时，输出为高；否则为低。

2、计算机世界
以PHP语言为例, 逻辑运算符如下：

1
2
3
4
$a && $b    And（逻辑与）    TRUE，如果 $a 和 $b 都为 TRUE。
$a || $b    Or（逻辑或） TRUE，如果 $a 或 $b 任一为 TRUE。
$a xor $b   Xor（逻辑异或）   TRUE，如果 $a 或 $b 任一为 TRUE，但不同时是。
! $a            Not（逻辑非）    TRUE，如果 $a 不为 TRUE。

因为运算符优先级不同，逻辑与和逻辑或还有下面两种写法

1
2
$a and $b   And（逻辑与）    TRUE，如果 $a 和 $b 都为 TRUE。
$a or $b    Or（逻辑或） TRUE，如果 $a 或 $b 任一为 TRUE。

注意：这里有一个逻辑异或。

二、位运算符

位运算符是计算机系统中对二进制整数的操作符号。

0、以PHP语言为例，位运算符如下：

1
2
3
4
5
6
$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
2
php -r "var_dump(1 ^ 2);"
int(3)

2、两个字符串的异或
按每个字符的ASCII来异或，输出对于ASCII码对于的字符，字符可能不可见，所以直接打印输出结果可能是空字符串，这里通过ord转换。

单个字符

1
2
3
php -r "var_dump('a' ^ 'b', ord('a' ^ 'b'));"
string(1) ""
int(3)

字符串

1
2
3
4
5
6
$result = "hallo" ^ "hello";
var_dump($result);
 
for($i = 0; $i < strlen($result); $i++) {
    echo ord($result[$i]), PHP_EOL;
}

以上输出

1
2
3
4
5
6
7
php test_code/bit.php
string(5) ""
0
4
0
0
0

3、按位与
整数支持

1
2
php -r 'var_dump(3 & 5);'
int(1)

字符串不支持

1
2
3
4
5
php -r 'var_dump(3 & "a");'
PHP Warning:  A non-numeric value encountered in Command line code on line 1
 
Warning: A non-numeric value encountered in Command line code on line 1
int(0)

4、按位或
整数支持

1
2
php -r 'var_dump(5 | 3);'
int(7)

字符串不支持

1
2
3
4
5
php -r 'var_dump(5 | "a");'
PHP Warning:  A non-numeric value encountered in Command line code on line 1
 
Warning: A non-numeric value encountered in Command line code on line 1
int(5)

三、位运算符应用

0、debug的时候在index.php中加入的以下语句你一定不陌生。
打印除了Notice和Strict外的所以异常。

1
2
ini_set('display_errors', 'on');
error_reporting(E_ALL & ~E_STRICT & ~E_NOTICE);

这里E_ALL都是常量，使用对于的整数进行按位运算。

1、不用+ -实现两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 
    /**
     * @param Integer $a
     * @param Integer $b
     * @return Integer
     */
    function getSum($a, $b) {
        while ($b != 0) {
            $carray = ($a & $b) << 1;
            $a = $a ^ $b;
            $b = $carray;
        }
 
        return $a;
    }
}

2、不用额外的存储空间，实现两数交换

1
2
3
4
5
6
7
8
$a = "abc";
$b = "def";
 
$a = $a ^ $b;
$b = $a ^ $b;
$a = $a ^ $b;
 
var_dump($a, $b);

以上输出

1
2
3
php test_code/bit.php
string(3) "def"
string(3) "abc"

说明：
一个数异或本身结果是0，

1
2
php -r 'echo "0" ^ "a" ^ "a" ^ 4;'
4

看上面3个赋值语句

1
2
3
4
5
6
// 初始赋值
$a = $a ^ $b;
// $b = $a ^ $b = $a ^ $b ^ $b = $a;
$b = $a ^ $b;
// $a = $a ^ $b = $a ^ $b ^ $a = $a ^ $a ^ $b = $a
$a = $a ^ $b;

3、给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
 
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $res = $nums[0];
        for ($i = 1; $i < count($nums); $i++) {
            $res = $res ^ $nums[$i];
        }
 
        return $res;
    }
}

同类型题目
给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
 
    /**
     * @param String $s
     * @param String $t
     * @return String
     */
    function findTheDifference($s, $t) {
        $res = $t[strlen($t) - 1];
        for ($i = 0; $i < strlen($s); $i++) {
            $res ^= $s[$i] ^ $t[$i];
        }
 
        return $res;
    }
}

4、给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
思路：
使用位运算，把数字看成二进制字符串，二进制每4位对于一位16进制字符串，不断移动4位，转成16进制字符进行拼接。

算法：

1
2
3
4
定义16进制字符序列。
取出数字对应二进制字符的最后4位，num & 15【15的二进制字符串是'1111', 所以按位与的结果就是取后4位】，并获取对应16进制的字符hex[$num & 15]。
然后把num右移4位，获取下一个字符，拼接在上一个字符前。$res = hex[hex[num & 15] . $res;【>>算数位移，其中正数右移左边补0，负数右移左边补1。】
直到num为0, 或者$res的长度 >= 8。位移运算并不能保证num==0，需要使用32位int保证（对应16进制小于等于8位）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 
    /**
     * @param Integer $num
     * @return String
     */
    function toHex($num) {
        if ($num == 0) {
            return '0';
        }
 
        $hex = '0123456789abcdef';
        $res = '';
        while ($num != 0 && strlen($res) < 8) {
            $res = $hex[$num & 15] . $res;
            $num >>= 4;
        }
 
        return $res;
    }
}

5、大写字符转小写

1
2
3
4
5
6
7
function toLowerCase($str) {
        for ($i = 0; $i < strlen($str); $i++) {
            $str[$i] = chr(ord($str[$i]) | 32);
        }
 
        return $str;
}

参考：
关于位运算看这个就够了位运算详解以及在 Python 中需要的特殊处理
bin2hex

发表评论

电子邮件地址不会被公开。 必填项已用*标注