位运算

 1 &
 2 按位与
 3 如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
 4 |
 5 按位或
 6 两个相应的二进制位中只要有一个为1，该位的结果值为1
 7 ^
 8 按位异或
 9 若参加运算的两个二进制位值相同则为0，否则为1
10 ~
11 取反
12 ~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1
13 <<
14 左移
15 用来将一个数的各二进制位全部左移N位，右补0
16 >>
17 右移
18 将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数， 高位补0

技巧一：消去二进制最后一位数字1

公式： x & (x-1)

检测整数n是否为2的幂次，如果N是2的幂次，那么N&(N-1)得到结果为0，即可判断。

//检测整数n是否为2的幂次
#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n){
        int t=n&(n-1);
        cout<<t<<endl;
    }
}

View Code

计算各32位数有多少个1

//计算各32位数有多少个1
#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n){
        int sum=0,t=n;
        if(n==0)  break; 
        for(;t;t=t&(t-1)){
            sum++;
        }
        cout<<sum<<endl;
    }
}

View Code

技巧二：使用二进制进行枚举

技巧三;a^b^b=a

因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数。

#include<stdio.h>
int main()
{
    int a[7]={1,2,2,1,3,4,3};
    int ans=0;
    for(int i=0;i<7;i++){
        ans^=a[i];
    }
    printf("%d
",ans);
}

View Code

因为数是出现三次的，也就是说，对于每一个二进制位，如果只出现一次的数在该二进制位为1，那么这个二进制位在全部数字中出现次数无法被3整除。
模3运算只有三种状态：00,01,10，因此我们可以使用两个位来表示当前位%3，对于每一位，我们让Two，One表示当前位的状态，B表示输入数字的对应位，Two+和One+表示输出状态。

参考