二进制在编程中的应用

合肥一六八中学高一（25）班吕有为王子逸韦浩昱郑晴川周振宇庄振昊二进制在编程中的应用摘要：二进制算法是一种十分实用的方法，在许多方面都有重要的应用。在编程中灵活运用二进制，利用二进制的一些重要性质，会起到意想不到的效果。关键词：二进制；动态规划；树状数组；多重背包；线段树正文部分二进制（binary）在数学和数字电路中指以2为基数的记数系统，以2为基数代表系统是二进位制的。数字电子电路中，逻辑门的实现直接应用了二进制，因此现代的计算机和依赖计算机的设备里都用到二进制。在具体编程中，二进制也有重要的作用。第一部分“0”与“1”既可以表示逻辑，也可以表示“有”或“无”。在动态规划状态压缩算法中，巧妙地用二进制递推。一、题目：X行Y列的棋盘，还有很多完全相同的马（你可以认为有无数个）。现在在棋盘上摆上马（或者不摆），求任何马无法攻击另一匹马的方案总数。关键代码：for(registerinti=3;i=x;++i){for(registerintj=0;j(1y);++j){for(registerintk=0;k(1y);++k){if(at_bt(k)&j||at_bt(j)&k)continue;for(registerints=0;s(1y);++s){if(at_bt(s)&k||at_bt(k)&s||at_3(s,k)&j||at_3(j,k)&s)continue;dp[i][j][k]+=dp[i-1][k][s];dp[i][j][k]%=mod;}}}}在此题中，巧妙地运用整数的二进制表示某行每个位置马的有无，从而轻松递推出最后结果。第二部分二进制每一位数字都表示2的n次方，则每一个数k都可以表示成个数的和k2log题目:有N种物品和一个容量是V的背包，第i种物品最多有si件，每件体积是vi，价值是wi，求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大.输出最大价值。代码：cinnm;for(registerinti=0;in;i++){intvv,ww,s;cinvvwws;for(registerinti=1;i=s;i*=2)//二进制优化v[k]=vv*i,w[k++]=ww*i,s-=i;if(s0)v[k]=vv*s,w[k++]=ww*s;}for(registerinti=0;ik;i++)//01背包for(registerintj=m;j=v[i];j--)dp[j]=max(dp[j],dp[j-v[i]]+w[i]);在多重背包问题中，将每一个数的n倍表示成几个数之和，保证合理性的同时亦大幅提升了速度。第三部分“1”本身是一个数字，表示“一个”，将其当作储存数据的空间，通过一定的结构联系起来，可以起到重要的作用。题目：已知一个数列，你需要进行下面两种操作：1、将某一个数加上x2、求出某区间每一个数的和代码：#definelowbit(a)((a)&-(a))voidupdate(intx,inty,intn){for(inti=x;i=n;i+=lowbit(i))c[i]+=y;}intgetsum(intx){intans=0;for(inti=x;i;i-=lowbit(i))ans+=c[i];returnans;}这是树状数组的解法，相对方便，而用途更为广泛的解法是用线段树。inlinellrs(llx){returnx1|1;}voidscan(){cinnm;for(lli=1;i=n;i++)scanf(%lld,&a[i]);}inlinevoidpush_up(llp){ans[p]=ans[ls(p)]+ans[rs(p)];}voidbuild(llp,lll,llr){tag[p]=0;if(l==r){ans[p]=a[l];return;}llmid=(l+r)1;build(ls(p),l,mid);build(rs(p),mid+1,r);push_up(p);}inlinevoidf(llp,lll,llr,llk){tag[p]=tag[p]+k;ans[p]=ans[p]+k*(r-l+1);}inlinevoidpush_down(llp,lll,llr){llmid=(l+r)1;f(ls(p),l,mid,tag[p]);f(rs(p),mid+1,r,tag[p]);tag[p]=0;}inlinevoidupdate(llnl,llnr,lll,llr,llp,llk){if(nl=l&&r=nr){ans[p]+=k*(r-l+1);tag[p]+=k;return;}push_down(p,l,r);llmid=(l+r)1;if(nl=mid)update(nl,nr,l,mid,ls(p),k);if(nrmid)update(nl,nr,mid+1,r,rs(p),k);push_up(p);}llquery(llq_x,llq_y,lll,llr,llp){llres=0;if(q_x=l&&r=q_y)returnans[p];llmid=(l+r)1;push_down(p,l,r);if(q_x=mid)res+=query(q_x,q_y,l,mid,ls(p));if(q_ymid)res+=query(q_x,q_y,mid+1,r,rs(p));returnres;}intmain(){lla1,b,c,d,e,f;scan();build(1,1,n);while(m--){scanf(%lld,&a1);switch(a1){case1:{scanf(%lld%lld%lld,&b,&c,&d);update(b,c,1,n,1,d);break;}case2:{scanf(%lld%lld,&e,&f);printf(%lld\n,query(e,f,1,n,1));break;}}}return0;}对于每一个子节点而言，都表示整个序列中的一段子区间；对于每个叶子节点而言，都表示序列中的单个元素信息；子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是他的每一个子节点信息的整合。线段树就是分块思想的树化，或者说是对于信息处理的二进制化——用于达到O(logn)级别的处理速度，log以2为底。（其实以几为底都只不过是个常数，可忽略)。而分块的思想，则是可以用一句话总结为：通过将整个序列分为有穷个小块，对于要查询的一段区间，总是可以整合成k个所分块与m个单个元素的信息的并(0=k,m=n)。但普通的分块不能高效率地解决很多问题，所以作为log级别的数据结构，线段树应运而生。结语：二进制算法是一种十分实用的方法，在许多方面都有重要的应用。在编程中灵活运用二进制，可以起到非凡的作用。非常感谢您的观看