算法练习——(7)位运算

1.最简单地位运算使用场景就是在进行除法和乘法运算的时候了，例如每次遇到 n / 2，n / 4，n / 8这些运算的时候，完全可以使用位运算，可以代码运行效率更高，例如

n / 2 等价于 n >> 1

n / 4 等价于 n >> 2

n / 8 等价于 n >> 3。

如果测试下 n / 2 和 n >> 1 的运行效率，可能会发现没啥差别，但其实并非没有差别，而是大部分编译器会自动把 n / 2 优化成 n >> 1，这可以让你的代码显的更加牛逼一些，给面试官的印象可能也会好一些。

2.还有一个非常常用的就是奇偶的判断，判断一个数是否说奇数，原本我会

if( n % 2 == 1){
  dosomething();
}

现在可以采用与运算来代替 n % 2，改成这样

if( (n & 2) == 1){
  dosomething();
}

3.利用 n & (n - 1)消去 n 最后的一位 1

在 n 的二进制表示中，如果我们对 n 执行

n = n & (n - 1)

那么可以把 n 最右边的 1 消除掉，例如

n = 1001

n - 1 = 1000

n = n & (n - 1) = (1001) & (1000) = 1000

用处一：判断一个正整数 n 是否为 2 的幂次方

如果一个数是 2 的幂次方，意味着 n 的二进制表示中，只有一个位 是1，其他都是0。我举个例子，例如

2^0 = 0……0001

2^1 = 0……0010

2^2 = 0….0100

那么我们完全可以对 n 执行 n = n & (n - 1)，执行之后结果如果不为 0，则代表 n 不是 2 的幂次方，代码如下

boolean judege(int n){
     return (n & (n - 1)) == 0;// 
}

如果使用常规手段对话，得把 n 不停着除以 2，最后判断得出结果，用这个位运算技巧，一行代码搞定。

用处二：判断 正整数 n 的二进制表示中有多少个 1

例如 n = 13，那么二进制表示为 n = 1101,那么就表示有 3 个1，这道题常规做法还是把 n 不停着除以 2，然后统计除后的结果是否为奇数，是则 1 的个数加 1，否则不需要加1，继续除以 2。

不过对于这种题，我们可以用不断着执行 n & (n - 1)，每执行一次就可以消去一个 1，当 n 为 0 时，计算总共执行了多少次即可，代码如下：

 public int NumberOf12(int n) {
        int count = 0;
        int k = 1;
        while (n != 0) {
            count++;
            n = (n - 1) & n;
        }
        return count;

代码不仅更加短小精悍，而且效率更高

4.异或(^)运算的妙用

关于异或运算符，我们先来看下他的特性

特性一：两个相同的数相互异或，运算结果为 0，例如 n ^ n = 0;

特性二：任何数和 0 异或，运算结果不变，例如 n ^ 0 = n;

特性三：支持交换律和结合律，例如 x ^ ( y ^ x) = (x ^ y) ^ x;

问题：数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}