这里写目录标题
- 位运算(均是拷贝运算,不会影响原数据,这点要注意)
- &、|、^
- 位运算特性+细节
- 知识补充
- 对于n-1的理解
- 异或来实现数字交换
- 找到只出现一次的数据,其余数据出现偶数次
- >> 、<<
- 二进制中相邻的位的特点
- 一级目录
- 二级目录
- 二级目录
- 二级目录
- 一级目录
- 二级目录
- 二级目录
- 二级目录
- 一级目录
- 二级目录
- 二级目录
- 二级目录
- 一级目录
- 二级目录
- 二级目录
- 二级目录
位运算(均是拷贝运算,不会影响原数据,这点要注意)
&、|、^
位运算特性+细节
首先,我们尝试不使用递归来解决这道题,他让我们判断是一个数是否为2的次幂。
尝试往位运算方面靠,位运算是通过二进制来解决问题的,而二进制就是2的次幂的表示,且,二进制从低位向高位,依次是2的012345…次方,所以,我们可以知道二进制表示为10000的数,(即第一位是1,后面全是0的数)是2的次幂数
所以,初步的认知已经建立了。之后寻找位运算的特性,如果一个数是1000的话,那么0111 + 1 就是 1000,而1000与0111做位与运算,可以得到0000,所以可以通过该性质找到10000特点的数
注意点1:小于等于0的数,可以直接排除
注意点2:进行位运算时,要在做完位运算之后,加一层括号,因为位运算的优先级低于==
知识补充
2的偶数次幂mod3等于1,例如4、16等,mod3 等于 1
而2的奇数次幂,就是2的偶数次幂再乘2,此时如8、32,mod3等于2
所以在求4的次幂时,因为2的偶次幂,一定是4的次幂,所以,我们在找到2的次幂数的基础上,再找到那些是2的偶次幂的数,那些数mod3==1
对于n-1的理解
对于一个二进制 n = 10000010000101010,n - 1 = 10000010000101000,n - 1会将一个数的二进制表达最右边的1变为0,而其他不变,利用该特点可以得到1的个数
或者使用lowbit,见算法一栏“数据结构与算法”(lowbit的时间复杂度更低)
异或来实现数字交换
首先,a = a ^ b,此后我们可以将一个a看成是变化之后的a,而如果a^b,则是原数据a、b
b = a ^ b,此时a是变化之后的a,将其拆开:a ^ b ^ b,此时a是变化之前的a,所以,就等于a ^ 0,最终等于原来的a
而到此时,a除了在第一行做出了改变,其他地方均无改变,所以,还是第一行的结论:可以将一个a看成是变化之后的a,而如果a^b,则是原数据a、b
所以,a = a ^ b,a是第一行代码执行后变化的a,b是原来的a,所以,将a拆开(得到原来的a 和 b)并且将b换成原来的a:a ^ b ^ a,再使用交换律,得到a ^ a ^ b,最后等于原来的b
找到只出现一次的数据,其余数据出现偶数次
首先定义res = 0;
之后将res与数组中的每个数进行异或运算
用到的知识点:
1、0^a = a
2、b^b = 0;
>> 、<<
二进制中相邻的位的特点
判断相邻位数是否交替为0、1
也就是相邻的位数上不能是相同的,即不能是00或者11,
而00对应于十进制是0,11对应于十进制是3
所以,如果 n&3 == 3,则表示当前n的右边两位是11
如果n&3 = = 0,则表示当前n的右边是00,(注意,此处还是&3,即00&11结果为00。逻辑上,他还有个等价式是00&00结果为11,也就是n&0 = = 3,但是如果&0的话,可能转为二进制就变成&一位0,而&3的话,铁定在二进制是&两位,所以,&0会导致某些数据点报错)
每次判断完之后,将n>>1右移一位,并覆盖到n,注意每次右移一位,如果右移两位,可能会出现0110,这样的数据,会出错
注意点1:&运算一次进行多位二进制判断时,尽量避免&0,尽可能找其等效式