2.2.1、与

1
2
3
4

6 ：0 1 1 0
11：1 0 1 1
————————————
2 ：0 0 1 0

当且仅当两者都为 1 的时候，结果才为 1，所以在这里只有第三位两者都为 1 ，所以结果就是 0010。

2.2.2、或

1
2
3
4

6 ：0 1 1 0
11：1 0 1 1
————————————
15：1 1 1 1

当且仅当两者都为 0 的时候，结果才为 0，所以在这里所有的结果都为 1 ，所以结果就是 1111。

2.2.3、非

1
2
3

6 ：0 1 1 0
————————————
9 ：1 0 0 1

非的规则是将 1 变成 0，0 变成 1，所以0110非操作之后就是1001，为9.

2.2.4、异或

1
2
3
4

6 ：0 1 1 0
11：1 0 1 1
————————————
13：1 1 0 1

异或的运算规则：0^0=0 0^1=1 1^0=1 1^1=0 相同为 0，相异为 1.

2.2.5、左移和右移

左移：

1
2
3

6 ：0 1 1 0
————————————
12：1 1 0 0

左移就是将所有的 1 都左移一位，然后空位上补0，所以 6 左移一位的结果就是 12.相当于 6 乘 2 等于 12.
右移：

1
2
3

6 ：0 1 1 0
————————————
3 ：0 0 1 1

右移就是将所有的 1 都右移一位，然后空位上补0，所以 6 右移一位的结果就是 3.相当于 6 除 2 等于 3.

从上面可以看出，如果我们在平时需要用到乘法或者除法，就可以使用左移和右移来进行替代，可以更好地提高效率。

2.3.1、实现乘除法

数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2

1
2
3

int a = 2;
a >> 1; ---> 1
a << 1; ---> 4

2.3.2、交换两个数

使用位运算交换两个数的时候，可以不使用第三个变量，虽然这个操作普通的运算也能做到，但是效率远不如位运算。

1
2
3
4
5
6
7
8
9
10
11
12
13

//普通操作
void swap(int &a, int &b) {
  a = a + b;
  b = a - b;
  a = a - b;
}

//位与操作
void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

2.3.3、判断奇偶数

只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数。

1
2
3

if(0 == (a & 1)) {
 //偶数
}

2.3.4、交换符号

交换符号将正数变成负数，负数变成正数

1
2
3

int reversal(int a) {
  return ~a + 1;
}

2.3.5、求绝对值

整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

1
2
3
4

int abs(int a) {
  int i = a >> 31;
  return i == 0 ? a : (~a + 1);
}

上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 0xffffffff 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)

1
2
3
4

int abs2(int a) {
  int i = a >> 31;
  return ((a^i) - i);
}

除此之外，还有很多用途。

和普通的运算符一样，位运算符也可以组成复合运算符的形式。
如下：

1
2
3
4
5

&=        例：a&=b    相当于     a=a&b
|=        例：a|=b    相当于     a=a|b
>>=      例：a>>=b   相当于     a=a>>b
<<=      例：a<<=b     相当于      a=a<<b
^=        例：a^=b    相当于   a= a^b

2.5.1、只出现一次的数字

问题描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

分析

1. 0和任意数字进行异或操作结果为数字本身.
2. 两个相同的数字进行异或的结果为0.

解答

1
2
3
4
5
6
7
8
9
10

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

2.5.2、只出现一次的数字

问题描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

分析
这题和上一题的思路略有不同，这题其他数字出现了3次，那么我们如果直接使用位运算异或操作的话无法直接找到结果，就需要巧妙的运用二进制的其他特性：判断整除求余操作。即判断所有数字二进制1的总个数和0的总个数一定有一个不是三的整数倍，如果0不是三的整数倍那么就说明结果的该位二进制数字为0，同理否则为1.
在具体的操作实现上，问题中给出数组中的数据在int范围之内，那么我们就可以在实现上可以对int的32个位每个位进行依次判断该位1的个数求余3后是否为1，如果为1说明结果该位二进制为1可以将结果加上去。最终得到的值即为答案。
解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int singleNumber(int[] nums) {
        int value=0;
        for(int i=0;i<32;i++)
        {
            int sum=0;
            for(int num:nums)
            {
                if(((num>>i)&1)==1)
                {
                    sum++;
                }
            }
            if(sum%3==1)
                value+=(1<<i);
        }
        return value;
    }
}