织梦手机网站建设,网站建设制作设计开发,韶关住房和城乡建设局网站,只做恐怖片的网站前言
不仅异或运算有很多骚操作#xff0c;位运算本身也有很多骚操作。#xff08;尤其后几个题#xff0c;太逆天了#xff09;
一、2 的幂
class Solution {
public:bool isPowerOfTwo(int n) {return n0n(n-n);}
}; 根据二进制表示数的原理#…前言
不仅异或运算有很多骚操作位运算本身也有很多骚操作。尤其后几个题太逆天了
一、2 的幂
class Solution {
public:bool isPowerOfTwo(int n) {return n0n(n-n);}
}; 根据二进制表示数的原理2的幂的二进制只有1个1所以根据Brian算法取最右侧的1只要n等于取完最右侧1的数即为2的幂。
二、3 的幂
class Solution {
public:bool isPowerOfThree(int n) {return n01162261467%n0;}
}; 1162261467就是整型范围内3的幂的最大值所以只要n能整除它就说明n为3的幂。
三、数字范围按位与
class Solution {
public:int rangeBitwiseAnd(int left, int right) {while(leftright){right-right(-right);}return right;}
}; 思考与运算的性质只要有0就是0又想到连续的区间内相邻两个数的最右侧1的那位必然不同所以与运算后最右侧的1必然留不下所以只要在大于左侧的范围内每次减去取完最右侧1的数即可。
这么说肯定很抽象很难理解比如right为0101001101则right-1为0101001100所以与运算后最右侧的1肯定留不下所以减去1right为0101001100此时right-1为0101001011所以第三位的1也留不下所以right要减去2的平方成为0101001000之后若right大于left就继续循环。
四、颠倒二进制位
class Solution {
public:uint32_t reverseBits(uint32_t n) {n((n0xaaaaaaaa)1)|((n0x55555555)1);n((n0xcccccccc)2)|((n0x33333333)2);n((n0xf0f0f0f0)4)|((n0x0f0f0f0f)4);n((n0xff00ff00)8)|((n0x00ff00ff)8);n(n16)|(n16);return n;}
}; 这个和下一个题的思路太过于逆天了。
简单说就是每次以1,2,48,16为单位进行逆序。例如abcdefgh先以1为单位逆序成badcfehg再以2为单位逆序成dcbahgfe再以4为单位逆序成hgfedcba。
具体原理就是这样实现起来就是先让abcdefgh10101010成为a0c0e0g0再让abcdefgh01010101成为0b0d0f0h之后让第一个数右移1位第二个数左移1位最后或运算就是badcfehg。而10101010就是十六进制aa01010101就是十六进制55。
之后递推就行。累
五、汉明距离
class Solution {
public:int hammingDistance(int x, int y) {return cntOnes(x^y);}int cntOnes(int n){n(n0x55555555)((n1)0x55555555);n(n0x33333333)((n2)0x33333333);n(n0x0f0f0f0f)((n4)0x0f0f0f0f);n(n0x00ff00ff)((n8)0x00ff00ff);n(n0x0000ffff)((n16)0x0000ffff);return n;}
}; 这个的思路和上一个题差不多。
比如11111001先保留奇数位的信息01010101得到01010001再获取偶数位的信息让11111001右移1位后01010101,得到01010100最后让两数相加得到10100101表示从左到右前两位中有两个1往后两位2个之后1个最后两位1个1。
之后以此类推。
六、位图
1.原理
一般来说如果要记录出现过的数字我们一般会向数组中输入这个数表示这个数出现过。但这样的话每个数字都会占用一个int的内存。所以为了进一步节省内存就可以使用位图。位图就是在一个位置上通过这个数32位的二进制用0和1分别表示出现与否用位数0~31表示数字0~31。这样的话一个int的位置就可以表示32个数字。
2.实现——设计位集
class Bitset {vectorintbitset;bool reverse;int ones;int zeros;int n;public:Bitset(int size) {for(int i0;isize;i){bitset.push_back(0);}reversefalse;ones0;zerossize;nsize;}void fix(int idx) {if(!reverse){if((bitset[idx/32](1(idx%32)))0){zeros--;ones;bitset[idx/32]|(1(idx%32));}}else{if((bitset[idx/32](1(idx%32)))!0){zeros--;ones;bitset[idx/32]^(1(idx%32));}}}void unfix(int idx) {if(!reverse){if((bitset[idx/32](1(idx%32)))!0){zeros;ones--;bitset[idx/32]^(1(idx%32));}}else{if((bitset[idx/32](1(idx%32)))0){zeros;ones--;bitset[idx/32]|(1(idx%32));}}}void flip() {reverse!reverse;int tones;oneszeros;zerost;}bool all() {return onesn;}bool one() {return ones0;}int count() {return ones;}string toString() {string s;for(int i0,num;in;i){num(bitset[i/32](1(i%32)))0?0:1;num^(reverse?1:0);snum0;}return s;}
}; 重点是全局变量ones和zeros以及reverse用来记录0和1的数量以及是否经历反转。
在加入中若没反转过即0表示没有1表示有。那么若该位为0则或运算成为1并同步让zeros--ones。之后反转过的和删除思路相似。
之后反转函数只要将reverse取反然后交换zeros和ones。
判断是否全为1、判断是否存在1和计算1的数量函数只要对ones操作即可。
转成字符串函数按位的数量遍历每次取出该位的数num若经过反转则反转num。
总结
位运算这几个例题的思路一个比一个逆天一个比一个抽象但用出来确实很nb。晕
END
