位运算_奇巧淫技

1. 判断奇偶数

1 2	// 奇数最后一位二进制为 1，偶数最后一位二进制为 0 return (i & 1);

2. 求一个数的负数

1	return (~n + 1);

3. 求绝对值

/*
先移位来取符号位，$i = a >> 31;
如果a为正数，i等于0，为负数，i等于-1。
*/
function abs($a) {  
    $i = $a >> 31;  
    return $i == 0 ? $a : (~$a + 1);  
}  

优化：
任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反，
a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）

function abs($a) {
	$i = $a >> 31;  
    return (($a ^ $i) - $i);  
}

4. 判断一个数转为二进制后的第i位数是0还是1

比如85的二进制为1010101.

我们要求第五位二进制位数上是0还是1，那么我们可以通过位运算符的移位操作来进行

比如我们可以将85的二进制1010101与1向左移4位来做与运算

就是1010101 与 0010000做与运算，看第五位是0还是1，

得出这个结果，我们可以将结果0010000右移4位然后将结果与1进行比较即可

1	return ((((x&(1<<4))>>4)==1) ? 1 : 0 );

5. 找出唯一成对的数

function findRepeatNum () {

    $arr = range(1, 12);
    $arr[] = mt_rand(1, 12);
    
    //交换位置,使相同的数字排在一起
    $k = count($arr) - 1;
    $v = $arr[count($arr) - 1];
    $arr = swap ($arr, $k, $v);
    
    // 求得1到N-1这些连续的数的异或
    $b = 0;
    $arrlength = count($arr);
    for ($i = 1; $i <= $arrlength - 1; $i++) {
        $b = ($b ^ $i);
    }

    // 再与原来的数组arr异或，这样重复的数就有三个，
    //不重复的数有两个，异或消除重复后，剩下的就是重复的数了
    for ($i = 0; $i < $arrlength; $i++) {
        $b = $b ^ $arr[$i];
    }

    echo '=========暴力破解==============';
    $helper = array();
    for ($b = 0; $b < $arrlength - 1; $b++) {
        $helper[$arr[$b]] += 1;
    }
    foreach ($helper as $k => $index) {
        if ($index == 2) {
            echo $k;
            break;
        }
    }
}

function swap ($arr, $k, $v) {
    $arr[$k] = $arr[$k] ^ $arr[$v];
    $arr[$v] = $arr[$k] ^ $arr[$v];
    $arr[$k] = $arr[$k] ^ $arr[$v];
    return $arr;
}

6. 找出落单的这个数

相同两个数异或结果是0, 任意一个数和0异或的结果还是自己，异或满足交换律;

$arr = [1, 3, 9, 1, 3, 4, 5, 4, 5];
function findUnique($arr) {
    $res = 0;
    foreach ($arr as $key => $value) {
        $res ^= $value;
    }
    return $res;
}

7. 二进制中一的个数

首先二进制数有这么一个性质，当一个数减去1再与原来的数字去&运算，
得到的结果其实是将原来的那个数字的最右边的那个1变成0后的数字。
/举个粒子：
10101010
10101010 - 1 = 10101001
10101010 & 10101001 =
10101000/
1
2
3
4
5
6
7
8
function bitNums($i) {
    $count = 0;
    while ($i != 0) {
        $i = ($i - 1) & $i;
        $count++;
    }
    return $count;
}

8. 判断整数是不是2的整数次方；

/* 
    判断一个正整数num是否为2的N次方
    基本思想：
    十进制    二进制      N-1        N&N-1        是否为2的乘方
    8        1000       111        0            是
    16       10000      1111       0            是
    32       100000     11111      0            是
    100      1100100    1100011    1100000      否
   算法时间复杂度为O(1)，空间复杂度为O(1)
*/

return (num & (num-1)) == 0;

9. 将整数的奇偶互换

/*
1.将原始数与1010做与运算
----- 1 0 0 1
----- 1 0 1 0 &
-------------------
----- 1 0 0 0

2.将原始数与0101做与运算
----- 1 0 0 1
----- 0 1 0 1 &
-------------------
----- 0 0 0 1

3.移位后做异或
----- 1 0 0 0 =>右移一位 0 1 0 0
----- 0 0 0 1 =>左移一位 0 0 1 0
-------------------------------
---针对移动结果最异或     0 1 1 0
*/

function interchange ($i) {
    $ou = $i & 0xaaaaaaaa; //1010 1010 1010 ......做与运算去除保留位
    $ji = $i & 0x55555555; //0101 0101 0101 ......做与运算取出奇数位
    return ($ou >> 1) ^ ($ji << 1);//异或运算
}