分门别类刷算法，坚持，进步！

刷题路线参考： https://github.com/chefyuan/algorithm-base

大家好，我是刷题困难户老三，这一节我们来刷几道很有意思的求次数问题，它们都有同一类非常巧妙的解法。

这种解法是什么呢？往下看吧！

基础知识

在开始之前，我们最好先了解一些位运算的基础知识。

原反补码

先简单说一下，原码、反码、补码。

一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

比如，十进制中的数 +3 ，假如计算机字长为8位，转换成二进制就是00000011。如果是 -3 ，就是 10000011 。

• 原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:

[+1]原 = 0000 0001

[-1]原 = 1000 0001

• 反码

正数的反码是其本身

负数的反码是在其原码的基础上, 符号位不变，其余各个位取反。

[+1] = [00000001]原 = [00000001]反

[-1] = [10000001]原 = [11111110]反

• 补码

正数的补码就是其本身

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补

[-1] = [10000001]原 = [11111110]反 = [11111111]补

补码是人脑认识里不太直观的一种表示方式，之所以发明补码，是为了让机器以一种一致的方式来处理加法运算。

更多知识建议阅读《j计算机组成原理》。

与或非异或运算

在处理整型数值时，位运算符可以直接对组成整型数值的各个位进行操作。这些位运算符在位模式下工作。位运算符包括：&、|、~、^

• 与（&）

对应位都为1，结果为1，否则结果为0

int a=129;
int b=128;
System.out.println("a与b的结果："+(a&b));
# 输出
a与b的结果：128

计算过程如下:

10000001 &
10000000 =
10000000

• 或（|）

对应位只要有一个为1，结果是1，否则就为0

int a=129;
int b=128;
System.out.println("a或b的结果："+(a|b));
# 输出
a或b的结果是：129

计算过程如下:

10000001 |
10000000 =
10000001

• 非（~）

位为0，结果是1；位为1，结果是0

 int a = 8;
System.out.println("非a的结果："+(~a));
# 输出
非a的结果：-9

计算过程如下

        //8转换为二进制
        1000
        // 补符号位
        01000
        // 取反
        10111 (补码)
        // 转源码除符号位取反+1
        11001

• 异或（^）

对应位相同，结果是0，否则结果是1

1111 ^
0010 =
1101

移位运算

移位运算见名知意，是数字二进位的移动，我们这里只讨论int型的移位运算。

• << 左移运算符

数值的补码全部左移若干位，符号位和高位丢弃，低位补 0。

• >> 右移运算符

数值的补码全部右移若干位，符号位不变。

假如int是8位二进制，两个例子如下：

10的补码为0000 1010，左移一位变成20（0001 0100），右移一位变成5（0000 0101）

5的补码为0000 0101，左移一位变成10（0000 1010），右移一位变成2（0000 0010）

求次数问题

LeetCode136. 只出现一次的数字

☕ 题目：136. 只出现一次的数字 (https://leetcode-cn.com/problems/single-number/)

❓ 难度：简单