位运算

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
|	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

与运算的用途

• 清零
• 取一个数的指定位：比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。
• 判断奇偶：只要根据最末位是0还是1来决定

NC101 缺失数字

描述

从 0,1,2,…,n 这 n+1 个数中选择 n 个数，选择出的数字依然保持有序，找出这 n 个数中缺失的那个数，要求 O(n) 或 O(log(n)) 并尽可能小。

解法：位运算

来自评论区：题解 | #缺失数字#_牛客博客 (nowcoder.net)

核心思想：

位运算的基于以下几个公式：

x ^ x = 0

x ^ 0 =x

x ^ y ^ z = x ^ z ^ y

既同一个数与自身异或为0，任何数与0异或为自身，异或运算满足交换律。

为求得题中缺失数字，可以令数组中全部数字异或，再与0-n中所有数字异或。

既数组异或结果。

num = 0 ^ 1 ^ … ^ (k-1) ^ (k+1) ^ … ^ n

0-n 异或结果

xor = num ^ sum

= (0^1^ … ^ (k-1) ^ (k+1) ^ … ^ n) ^ (0 ^ 1 … ^ (k-1)^k^(k+1)^…^n)

上式中，出现两次的，根据异或都变为0，出现一次的即为缺失数字。

class Solution:
    def solve(self , a ):
        # write code here
        n = len(a)
        sum_ = 0
        num_ = 0
        
        for i in range(n):
            sum_ ^=(i+1)
            num_ ^= a[i]
        return sum_ ^ num_
            

java:

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 找缺失数字
     * @param a int整型一维数组 给定的数字串
     * @return int整型
     */
    public int solve (int[] a) {
        // write code here
        int sum = 0,num = 0;
        for(int i=0; i < a.length;i++){
            sum ^= (i+1);
            num ^= a[i];
        }
        return num^sum;
    }
}