位域 (Bit field)
2018-12-04 07:12:04来源:博客园 阅读 ()
最近开始看编程之美这本书,里面有一道关于中国象棋将帅位置的简单问题,如下图所示,写一个程序输出将、帅的合法位置。
分析与解法
问题的本身并不复杂,只要把所有A、B 互相排斥的条件列举出来就可以完成本题的要 求。由于本题要求只能使用一个变量,所以必须首先想清楚在写代码的时候,有哪些信息需 要存储,并且尽量高效率地存储信息。稍微思考一下,可以知道这个程序的大体框架是:
遍历A的位置
遍历B的位置
判断A、B的位置组合是否满足要求
如果满足,则输出
因此,需要存储的是A、B 的位置信息,并且每次循环都要更新。为了能够进行判断, 首先需要创建一个逻辑的坐标系统,以便检测 A 何时会面对 B。这里我们想到的方法是用 1~9的数字,按照行优先的顺序来表示每个格点的位置。这样,只需要用 模余运算就可以得到当前的列号,从而判断A、B 是否互斥。
若题目要求只用一个变量,但是我们却要存储 A 和 B 两个子的位置信息,该怎么办呢?
可以先把已知变量类型列举一下,然后做些分析。
对于bool类型,估计没有办法做任何扩展了,因为它只能表示true和false 两个值;而 byte 或者 int 类型,它们能够表达的信息则更多。事实上,对本题来说,每个子都只需要 9 个数字就可以表达它的全部位置。
一个8位的byte类型能够表达28=256个值,所以用它来表示A、B的位置信息绰绰有余, 因此可以把这个字节的变量(设为b)分成两部分。用前面的4 bit表示A的位置,用后面的 4 bit表示B的位置,那么4个bit可以表示16个数,这已经足够了。
那么:如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出呢?
大家容易想到的是对那个变量进行各种位运算,最后输出结果。
但是其实C语言中还提供了一种存在于结构体中叫做位域的类型,因此程序就变得简单多了。关于位域更多的用法规则,详见:C位域
#include <stdio.h> struct bf{ unsigned char a:4; unsigned char b:4; }i; /*定义位域结构*/ int main() { for(i.a = 1; i.a <= 9; i.a++) { for(i.b = 1; i.b <= 9; i.b++) { if(i.a % 3 != i.b %3) printf("A = %d, B = %d\n", i.a, i.b); } } return 0; }
另一巧妙解法:
int main() { unsigned char i = 81; while(i--) { if(i/9%3 != i%9%3) printf("A = %d, B = %d\n", i/9+1, i%9+1); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- AGC006C Rabbit Exercise 2020-05-21
- bit(比特)与Byte(字节)的区别与关系 2019-11-06
- 体验Code::Blocks下的Windows GUI编程(32 bit and 64 bit) 2019-10-08
- 高...高精度!!! 2019-08-16
- leetcode 136 Single Number bit Option 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash