通过在网上查找，整理的：
#include <iostream>
using namespace std;
bool is_pow2(int x) //判断是否2的n次方
{
x &= x-1;
if(!x) return true;
return false;
}
void Binary(int num)//十进制转二进制
{
int a[32];
int i = 0;
while(num)
{
a[i++] = (num%2)?1:0;
num >>= 1;
}
while(--i)
{
cout<<a[i];
}
cout<<a[0]<<endl;
}
int CountNumberOfOne(int number)//计算数number的二进制中包含1的个数
{
int counts = 0;
while(number)
{
counts++;
number &= number - 1;
}
return counts;
}
int main()
{
int x;
cin>>x;
cout<<"binary of number:";
Binary(x);
cout<<endl;
cout<<"numbers of one exit:"<<CountNumberOfOne(x)<<endl;
if(is_pow2(x))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
- using std::cout;
- using std::cin;
- using std::endl;
- int main()
- {
- //利用<<做2^6
- int m=2<<5;
- cout<<"2^6="<<m<<endl;
- //利用&运算符判断数的奇偶性
- if(m&1)
- cout<<m<<"是奇数"<<endl;
- else
- cout<<m<<"是偶数"<<endl;
- //判断一个数mod2^n次的值，依旧利用位运算符
- int n=645&7; //m&(2^n-1)
- cout<<"645mod8="<<n<<endl;
- //用异或求不同数
- n=1^1^5^7^5;
- cout<<"1^1^5^7^5="<<n<<endl;
- //两个数的原地交换
- //利用异或法实现
- int a=7,b=5;a=a^b;b=a^b;a=a^b;cout<<a<<" "<<b<<endl;
- //利用加减法实现
- a=7,b=5;a=a+b;b=a-b;a=a-b;cout<<a<<" "<<b<<endl;
- return 0;
- }
对集合的表示：
大多数时候，我们可以用一个整数来表示一个包含不超过32（当然如果使用64位整型变量也可以是64个）个元素的集合——对于每一个位，如果元素为1，则表示存在当前位所对应的集合成员，如果是0，则表示这个集合成员是不存在的。
比如A=1011 就可以表示集合{0，1，3}，而上面提到的1<<x就表示集合{x}。
下面我们就能推导出一些直观的集合运算。
我们定义 ALL_BITS 为全集即各二进制位均为1的数。
集合的并 A|B
集合的交 A&B
集合的差 A& ~B
补集 ALL_BITS^A
添加特定元素bit A|=1<<bit
清除特定元素bit A^=1<<bit
取出特定元素bit A&=1<<bit
判断是否存在特定元素bit (A&1<<bit)!=0
枚举子集
当一个数的二进制表示一个集合的时候，位运算的一个巨大优点在于其可以非常轻松和高效地枚举当前集合的所有子集。
它的性质在于——如果A是B的真子集，那么可以保证枚举A子集的次数一定小于枚举B的子集的次数。这一点可以大大
提高很多压位动态规划题目的实现效率。
（1）暴力的方式
最暴力的方式莫过于枚举所有可能的集合，然后一一判断是否为当前集合的子集。
如果需要枚举的集合是N个元素的集合，那么对所有可能集合都进行一次枚举操作，花费的时间为O((2N)2)=O(4N)。
（2）高效的方式
假设全集有N个元素,那么所有可能的集合就有2N个,对于任意子集S,用N位2进制简单枚举S的所有子集,个数就有2N个,
因此如果对所有集合都进行这样一次枚举操作,那么总的时间复杂度就是O((2N)2)=O(4N)。高效的方式。
这里的技巧和低位技术的技巧是类似的——当我们取出最后一个1的时候，这个1将变成0，而比其低位的0将变成1。
与低位技术不同的是，我们并不是要提出某一位1，而是要去除某一位的1，并补上一些我们需要的1。
所以假设当前集合为SuperSet，那么枚举的代码段则为
Iterating_All_SubSet(SuperSet) {
i = SuperSet;
while (i > 0)
i = (i - 1) & SuperSet;
}
若当前为N位二进制的集合，并且对所有可行集合进行上述操作，可以证明，操作的总次数为O(3N)。
有趣的技巧
再提一些在C/C++中更加惊人的位运算技巧——它绝对可以让你在同学面前炫耀一下。
1.计算绝对值
abs( x ) {
y=x>>31 ;
return(x^y)-y;//也可写作 (x+y)^y
}
这里需要注意的是，上面的x, y 默认为32位有符号整数。
2.按位翻转
x=((x&0xaaaaaaaa)>>1)|((x&0x55555555)<<1);
x=((x&0xcccccccc)>>2)|((x&0x33333333)<<2);
x=((x&0xf0f0f0f0)>>4)|((x&0x0f0f0f0f)<<4);
x=((x&0xff00ff00)>>8)|((x&0x00ff00ff)<<8);
x=((x&0xffff0000)>>16)|((x&0x0000ffff)<<16);
如果无符号32位整数x=311=(100110111)2，那么经过上述操作后x=3967811584=(11101100100000000000000000000000)2。
这里不多作解释（其实研读这段代码是很有意思的一件事情），留给有兴趣的读者思考。
3.枚举恰好含有k个元素的集合
我们假设全集为含有N个元素为 {0,1,2,…,N-1}，那么代码段可以写成：
int s = (1 << k) - 1;
while (!(s & 1 << N)) {
// 由当前集合 s 计算下一个合法的集合
int lo = s & -s; // 求出低位的1
int lz = (s + lo) & ~s; // 求出比lo高的0中，最低位的0
s |= lz; // 将lz代表的元素加入集合s
s &= ~(lz - 1); // 将比lz位置低的元素全部清空
s |= (lz / lo / 2) - 1; // 将集合元素个数补足为k个
}
当然最后一句话也可以写成s |= (lz >> __builtin_ctz(lo << 1)) – 1来避免除法运算。