二进制数据处理.ppt
《二进制数据处理.ppt》由会员分享,可在线阅读,更多相关《二进制数据处理.ppt(9页珍藏版)》请在三一文库上搜索。
1、二进制数据处理,福州大学2013级计算机类一班 031302126 杨锦洲 2014.09.08,问题描述,给定一个正整数 N,找出另一个正整数 M,使得 N 和 M 转化为二进制时,它们所出现的“1”的个数一致,且 M 必须比 N 大。输出一个满足条件的最小的 M。 例如 78,转换成二进制为 1001110,这个二进制数中有 4 个“1”。而 83(1010011)和86(1010110)都满足二进制中“1”的个数与 78 一样,且值都比 78 大。但显然 83 是最小的那个,输出它。,问题分析,N:给定的正整数;M要找到的数。 对M的要求: 一、“1”的个数与N相同; 二、大于N; 三、
2、所有符合条件的数中的最小值。,问题解决,针对问题一:将N转换为二进制存储在数组中 考虑到问题二和三,这里采用逆序存储(低 位在前,高位在后)。 针对问题二、三:将“1”往高位移位。 例如:N:100101(正常二进制数)101001(数组中) 将数组中第一个“1”向后移一位就可以得到 M的逆序二进制数。,核心代码,for(i=0;n!=0;i+) ti=n%2; n=n/2; ,用数组t17存储N的逆序二进制数。 (N=100000217=131072) 78(1001110) (t17数组中),for(j=0;ji;j+)if(tj=1) for(k=j+1;k+)if(tk=0)break
3、; break; ,找到最低位的1以及与其最近但比它高位的0 t1、t4 (j=1,k=4),标号 t,(数组所有元素皆已初始化为0),核心代码,m=tk-1; tk-1=tk; tk=m;,高位的0降位,if(k-j1) for(ints=0;s(k+1)/2;s+,j+) m=ts;ts=tj;tj=m;,判断0降位之后比0低位的1是否需要降位 通过数组元素的交换完成降位,for(k=i;k=0;k-)sum+=tk*pow(2,k);,二进制转十进制,算法的优缺点分析和改进,算法优缺点分析: 优点:只需要通过简单的移位;思路简明清 晰; 缺点:需要多考虑细节;程序实现上稍微复 杂,总结 整个算法的时间主要花费在几个循环结构上,特别 是当数值较大的时候。因为时间复杂度较难计算, 便没有进行统计。 这里有个细节:当遇到低位全为0高位全为1的情况 如:11111100000(11位)时由于数组t17所有元 素初始值为0,此时j=5、k=11,只要将t10与t11 交换,并将低位的0(t0t4)与高位的1(t5 t9)交换就得到10000011111。,Thank you!,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二进制 数据处理
链接地址:https://www.31doc.com/p-2578563.html