Single Num

https://leetcode.com/problems/single-number/
给定一个数组，除了数字A出现一次以外，其他数字都出现两次，找出这个数字。时间复杂度必须是O(n)，并且空间复杂度为O(1)

正常思路毫无疑问，一个排序，逐个遍历，肯定找出来了。本题有个先决条件，时间复杂度和空间复杂度都有要求，就来到了位运算的世界

image.png

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $res = 0;
        foreach ($nums as $val) {
            $res = $res^$val;
        }
        return $res;
    }

Single Num II

https://leetcode.com/problems/single-number-ii/
升级版Single Num，给定一个数组，除了A出现一次以外，其他数字都出现了三次，找出这个数字

采用位运算来解是一个好的主意。数是int类型，也就是一个64位的整数。那么把数组A的各个数将其二进制的各个位分别求和，然后再模除3就是单独数字的二进制位，再拼装成一个整数，就是单独的数字。

    /**
     * singleNumber2
     * @param $nums
     * @return int
     */
    function singleNumber2($nums) {
        $res = 0;
        for ($i = 0; $i < 64; $i++) {
            $sum = 0;
            for ($j = 0; $j < count($nums); $j++) {
                //$sum += ($nums[$j] >> $i) & 1;
                $tmp = $nums[$j] >> $i;
                $tmp = $tmp & 1;
                $sum += $tmp;

            }

            $res |= ($sum % 3) << $i;
        }
        return $res;
    }

如果上面算法不好理解，请看下面这种写法（思路一样）

    function singleNumber2New($nums) {
        $res = [];
        foreach ($nums as $val) {
            for ($i = 0; $i < 64; $i++) {
                if (!isset($res[$i])) {
                    $res[$i] = 0;
                }
                $res[$i] += ($val >> $i) & 1;
            }
        }

        $out = 0;
        foreach ($res as $k => $v) {
            $out += ($v % 3) << $k;
        }
        return $out;
    }