花里胡哨的位运算

位运算，虽然说是一种十分精妙的算法技巧，但是除了花里胡哨好像并不能大幅提升时间复杂度。虽说如此，但不得不说，位运算的诸多技巧还是非常有趣的！

初识位运算

初次见到位运算的应用，那是在一个夏天的下午，有同学在班群问：“如何写交换函数？”不久，有人贴了这么段代码：

void swap(int* a, int* b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

我一脸懵，这都行？这是怎么交换的？异或还能这么使？记得那天我在草稿纸上花了半天，才搞懂了个大概：

我们以 3 和 6 为例：

初始状态时：		a = 3 = 011		b = 6 = 110
第一句执行： 	    a = 101			b = 110
第二句执行：		a = 101			b = 011 = 3
第三局执行：		a = 110 = 6		b = 011 = 3

确实交换过来了，但为啥呢？但其实，我们可以将代码简单地变一下：

1	b = (a ^ b) ^ b;

使用交换律，也就是 b = a ^ (b ^ b) ，而这时，便可以清晰地看出来：因为一个数异或本身等于 0 ，所以代码的前两句也便是 b = a。那 a 又是怎么变过来的呢？

1	a = (a ^ b) ^ ((a ^ b) ^ b)

同样，进行变换 a = ((a ^ b) ^ (a ^ b)) ^ b ，也就是 a = b，至此便完成了交换的操作。

常见的位运算技巧

位运算说是技巧，但实质上也是利用了逻辑运算的基本技巧：

一个数异或自己本身为 0
与或非的基本定义
……

只出现一次的数字（`LeetCode 136`）

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

题目解答：这道题便可以利用异或的性质，将数组元素挨个异或，便可以将所有成对的数据消去，最终剩下的，便是只出现了一次时数字。

代码如下：

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) 
            ret ^= nums[i];
        return count;
    }
}

位1的个数（`LeetCode 191`）

题目说明： 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

题目解答： 这题便是相当明显的需要利用位操作的题目，因为需要一位一位地判断。所以一边右移一边判断最右边那位是0还是1即可！

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) ret++;
            n >>= 1;
        }
        return ret;
    }
}

说明： 数字和1与，可以判断该数的奇偶！因为 1 的二进制是 00...1 ，所以与完的结果便只有最后一位，1 为奇数，0 为偶数。

虽是如此，官方还给出来一个更为特殊的解法：

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            ret++;
            n &= (n-1);
        }
        return ret;
    }
}

说明：在二进制表示中，数字 n 中最低位的 1 总是对应 n - 1 中的 0 。因此，将 n 和 n - 1 与运算总是能把 n 中最低位的 1 变成 0 ，并保持其他位不变。

所以，优化之后，只运算 1 的个数次即可！

2的幂（`LeetCode 231`）

题目说明： 给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

题目解答： 这题如果能想到 位运算 这仨字，那么便可以比较容易地想出算法，因为毕竟 2 的幂次在二进制中来看是“整”的，相当于十进制中的 10...100...1000等等！

比如： 8的二进制表示为1000，8-1 也就是 7 的二进制为 0111 。如果把这俩数相与，不刚好是 0 吗？但是由于负数的补码问题，所以首先还需要判断是否正数。

所以可以写出代码：

bool isPowerOfTwo(int n) {
    if ((n > 0) && ((n & (n-1))== 0))
        return true;
    else
        return false;
}

4的幂（`LeetCode 342`）

题目说明： 给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

题目解答： 这算是上题的进阶，如果熟悉二进制，便知道4的幂实质上用二进制来表示实质上为 10 间隔，4 -> 10 16 -> 10000 64 -> 1000000。利用此特点，便可以发现这样一个数：01010101010101010101... ，也就是十六进制的 0x55555555，其和4的幂相与，不会改变 0x55555555 的值。

综上写出代码：

class Solution {
    public boolean isPowerOfFour(int num) {
        if (num <= 0 || (num & (num-1)) != 0)   return false;
        return ((num & 0x55555555) == num);
    }
}

说明： “0x55555555，其和4的幂相与，不会改变 0x55555555 的值”是一个充分条件，并非必要条件。故可能还有别的数和 0x55555555，其与4的幂相与，不会改变 0x55555555 的值，因此需要进行限制！即将非 2 的幂次和小于 0 的数除外。

初识位运算

常见的位运算技巧

只出现一次的数字 （LeetCode 136）

位1的个数（LeetCode 191）

2的幂（LeetCode 231）

4的幂（LeetCode 342）

只出现一次的数字（`LeetCode 136`）

位1的个数（`LeetCode 191`）

2的幂（`LeetCode 231`）

4的幂（`LeetCode 342`）