大一计算机的自学总结：位运算的应用及位图
前言
不仅异或运算有很多骚操作，位运算本身也有很多骚操作。（尤其后几个题，太逆天了）
一、2 的幂
class Solution {
public:
bool isPowerOfTwo(int n) {
return n>0&&n==(n&-n);
}
};根据二进制表示数的原理，2的幂的二进制只有1个1，所以根据Brian算法取最右侧的1，只要n等于取完最右侧1的数，即为2的幂。
二、3 的幂
class Solution {
public:
bool isPowerOfThree(int n) {
return n>0&&1162261467%n==0;
}
};1162261467就是整型范围内3的幂的最大值，所以只要n能整除它，就说明n为3的幂。
三、数字范围按位与
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
while(left<right)
{
right-=right&(-right);
}
return right;
}
};思考与运算的性质，只要有0就是0，又想到连续的区间内，相邻两个数的最右侧1的那位必然不同，所以与运算后最右侧的1必然留不下，所以只要在大于左侧的范围内，每次减去取完最右侧1的数即可。
这么说肯定很抽象很难理解，比如right为0101001101，则right-1为0101001100，所以与运算后最右侧的1肯定留不下，所以减去1，right为0101001100，此时right-1为0101001011，所以第三位的1也留不下，所以right要减去2的平方，成为0101001000，之后若right大于left就继续循环。
四、颠倒二进制位
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
n=((n&0xaaaaaaaa)>>1)|((n&0x55555555)<<1);
n=((n&0xcccccccc)>>2)|((n&0x33333333)<<2);
n=((n&0xf0f0f0f0)>>4)|((n&0x0f0f0f0f)<<4);
n=((n&0xff00ff00)>>8)|((n&0x00ff00ff)<<8);
n=(n>>16)|(n<<16);
return n;
}
};这个和下一个题的思路太过于逆天了。
简单说，就是每次以1,2,48,16为单位进行逆序。例如，abcdefgh先以1为单位逆序成badcfehg；再以2为单位逆序成dcbahgfe；再以4为单位逆序成hgfedcba。
具体原理就是这样，实现起来就是先让abcdefgh&10101010成为a0c0e0g0，再让abcdefgh&01010101成为0b0d0f0h，之后让第一个数右移1位第二个数左移1位，最后或运算就是badcfehg。而10101010就是十六进制aa，01010101就是十六进制55。
之后递推就行。（累）
五、汉明距离
class Solution {
public:
int hammingDistance(int x, int y) {
return cntOnes(x^y);
}
int cntOnes(int n)
{
n=(n&0x55555555)+((n>>1)&0x55555555);
n=(n&0x33333333)+((n>>2)&0x33333333);
n=(n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);
n=(n&0x00ff00ff)+((n>>8)&0x00ff00ff);
n=(n&0x0000ffff)+((n>>16)&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 {
vector<int>bitset;
bool reverse;
int ones;
int zeros;
int n;
public:
Bitset(int size) {
for(int i=0;i<size;i++)
{
bitset.push_back(0);
}
reverse=false;
ones=0;
zeros=size;
n=size;
}
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 t=ones;
ones=zeros;
zeros=t;
}
bool all() {
return ones==n;
}
bool one() {
return ones>0;
}
int count() {
return ones;
}
string toString() {
string s;
for(int i=0,num;i<n;i++)
{
num=(bitset[i/32]&(1<<(i%32)))==0?0:1;
num^=(reverse?1:0);
s+=num+'0';
}
return s;
}
};重点是全局变量ones和zeros以及reverse，用来记录0和1的数量以及是否经历反转。
在加入中，若没反转过，即0表示没有，1表示有。那么若该位为0，则或运算成为1，并同步让zeros--，ones++。之后反转过的和删除思路相似。
之后反转函数只要将reverse取反，然后交换zeros和ones。
判断是否全为1、判断是否存在1和计算1的数量函数只要对ones操作即可。
转成字符串函数，按位的数量遍历，每次取出该位的数num，若经过反转，则反转num。
总结
位运算这几个例题的思路一个比一个逆天，一个比一个抽象，但用出来确实很nb。（晕）