算法--⼆进制⼆进制枚举
#⼀ ⼆进制操作
算数位运算：
1、与（&）:
对于指定的两个数A=60(0011 1100)
B=13(0000 1101)
执⾏⼀下操作 A&B=12(0000 1100)
就是对⼆进制每⼀位进⾏了⼀次与操作，同为1，结果 为1，否则为0。
2、或（|）:
对于指定的两个数A=60(0011 1100)
B=13(0000 1101)
执⾏⼀下操作 A|B=61(0011 1101)
就是对⼆进制每⼀位进⾏了⼀次或操作，同为0，结果为0，否则为1
3、⾮ 按位取反（~）:
对于指定的⼀个数A=60(0011 1100)
执⾏以下操作 ~A=195(1100 0011)
就是对⼆进制每⼀位进⾏了⼀次取反操作，若⼆进制数位0，则变成1，否则变成0.
4、异或运算
异或，英⽂为exclusive OR，缩写成xor
异或（xor）是⼀个数学运算符。它应⽤于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为：a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
异或也叫半加运算，其运算法则相当于不带进位的⼆进制加法：⼆进制下⽤1表⽰真，0表⽰假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位。
对于异或⼀个⾮常重要的性质，对于⼀个值异或同⼀个值两次，则结果还是原值。
在c/c++中异或⽤^符号表⽰；
例如：
对于指定的两个数 A=60(0011 1100)
B=13(0000 1101)
执⾏⼀下操作 A^B=49(0011 0001)
就是对⼆进制每⼀位进⾏了⼀次异或操作，即⾮进位加法。
例如：
（1）给出⼀个奇数n，（1 <= n <= 10000001）
给定⼀个具有n个数字的数组：a [1]，a [2] a [3] … a [n]。它们是正数。
n / 2个数字出现两次，只有⼀个数字出现⼀次。
现在，您应该告诉我仅出现⼀次的号码。
有⼏个测试案例以EOF结尾。
第⼀⾏是整数n。
然后第⼆⾏有n个整数a [1]，a [2] … a [n]。
对于每种情况，输出仅出现⼀次的数字。
样本输⼊
7
3 2 7 2 1 7 3
1
7
11
1 1
2 2
3 3
4 4
5 5 9
样本输出
1
7
9
代码如下：
int main()
{
int a,b,ans,n,i;
while(scanf("%d",&n)!=-1)
{
ans=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a);
ans=ans^a;
}
printf("%d\n",ans);
}
return0;
}`
之后再看这个：
⼆进制移位操作符：
移位操作有两种左移与右移：
1、左移<<
例如：A=5（0101）
如果向左移动⼀位即A<<1结果为1010，⼗进制的10。⼆进制中的左移就是乘⼆操作，在c/c++中左移运算速度⽐乘⼆速度要快。
2、右移>>
例如：A=5（0101）
如果向右移动⼀位即A>>1结果为0010，⼗进制的2。⼆进制中的左移就是除⼆操作（舍去⼩数）。
于是⼀种被称为⼆进制枚举的算法出世了：
n n
⼆进制枚举利⽤的是⼆进制下n位长度的数有2个,⼀个有n个元素的集合⼦集个数也为2个，所以可以利⽤⼆进制的1,0和集合中的元素联系起来他可以实现组合也可以实现容斥
对⼀个⼆进制来说1代表取这个元素0代表不取这个元素,1和0所在的位置代表元素的位置，这样的思想在有时候给题⽬有了很⼤的⽅便举个例⼦如集合{a,b,c,d,e}
当⼆进制00000就代表什么都不取, 10000代表取a，01000代表取b，11000代 表取a,b如此
所以我们需要枚举的数量就是00000到11111，也就是0到1<<n位，<<；代表左移操作
例如：
给出长度为n的数组，求能否从中选出若⼲个，使他们的和为K.如果可以，输出:Yes，否则输出No
输⼊：
第⼀⾏：输⼊N,K，为数组的长度和需要判断的和(2<=N<=20,1<=K<=10^9)
第⼆⾏：N个值，表⽰数组中元素的值(1<=a[i]<=10^6)
输出：
输出Yes或No
样例输⼊：
5 13
2 4 6 8 10
样例输出：
No
数学二进制的算法
代码如下：
int a[10000]，f;
long long sum,i,j,n,k;
int main()
{
sum=0;
while(scanf("%d%lld",&n,&k)!=-1)
{
f=0;
for(i=0; i<n; i++)scanf("%d",&a[i]);
for(i=0; i<(1<<n); i++)//将所有可能性⼀⼀枚举。
{
sum=0;//这⼀步很重要。
for(j=0; j<n; j++)
if(i&(1<<j))//如果括号⾥为真值(不为0)即从数组选取⼀定数量的数相加；可以将所有情况列举；                    sum=sum+a[j];
if(sum==k)//判断是否符合条件。
{
printf("Yes\n");
f=1;//标记。
break;//到之后⽴即退出。
}
}
if(f==0)
printf("No\n");
}
return0;
}
觉得有⽤就点个赞叭。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。