穷人时代如何节约内存-位运算.ppt

第15章穷人时代如何节约内存 位运算 伟大的比尔盖茨在DOS时代曾经有过这样的说法 640K的内存对一般人来说已经足够 可现在的电脑内存动辄就是1G 2G 且不评判上述那句话的正误 但从日新月异的硬件发展来看 我们就能猜出二三十年前的程序员是如何在内存使用上精打细算的 与之相比 现代程序员好像少了很多烦恼 内存似乎永远用不完 但内存再大 也要精打细算 本章从位运算的角度看一下如何合理节约内存的使用 15 1什么是位运算 从开始到现在 本书经常出现的一个词是内存单元 即1B 我们说char型占1个内存单元 1B 而short型占2个内存单元 2B 1B被当成整体来看 但不要忘记有下面的等式成立 1B 8bits1个字节有8个位 每个位有0 1两个取值 从这个角度上说 1个字节所能包含的意义似乎比预想的要大的多 15 1 1开灯关灯 举例来说 房间里有8盏灯 为了控制每盏灯的亮灭 可以声明8个Byte变量 变量为0代表灯灭 变量非0代表灯亮 这完全行得通 而且看起来很有效率 能否换种角度思考 能不能只有1个字节的8个位来控制8盏灯 该位为0代表灯灭 该位为1代表灯亮 答案是 可以 比较两种方法 发现使用位操作的方式有效节省了内存 如所示 15 1 2改变状态 假设某个时刻 灯1和灯2亮 而其他灯都灭 此时控制字为11000000 想变换下状态 让灯1和灯3亮 其他灯灭 目标控制字为10100000 只要赋值给该单元即可 问题又来了 如果原来不知道哪几盏灯亮哪几盏灯灭 现在还是想让第3盏灯亮起来 赋值操作看来是行不通了 要如何做呢 在这个背景下 位运算的概念被提出 即能否只改变控制第3盏灯的那一位的状态 本章的剩余章节将结合开灯关灯这一场景讲述位运算的内容 总体来说 C语言中的位运算符有以下两类 位逻辑运算符 位 与 位 异或 位 或 位 取反 移位运算符 右移 15 2位逻辑运算符 读者现在对逻辑运算已经不陌生了 位逻辑运算的原理与普通逻辑运算基本一致 不同在于普通的逻辑运算以变量为单位 而位逻辑运算以位 bit 为单位 先从最简单的位取反运算说起 15 2 1位取反操作 假设不知道哪几盏灯亮着哪几盏灯灭着 但想进行一个操作 让亮着的灯灭掉 让灭着的灯亮起来 这时就要用到位取反操作 位取反的操作符为 如果A为10101010 那么 A返回的结果为01010101 即每位都取反 0变成1 1变成0 需要注意的是 位取反运算并不改变操作数的值 假设字节A控制着8盏灯的亮灭 那么下述操作可实现预想的功能 A A 重申 位取反运算并不改变操作数的值 是赋值运算改变了A的值 15 2 2位与运算 位与运算的操作符为 将对两个操作数的每一位进行与运算 位 与 运算的准则如下 1 1 11 0 00 1 00 0 0不知道哪几盏灯亮着哪几盏灯灭着 想让第3盏灯灭掉 使用位与就能实现 想想看 要如何来做呢 只要在当前状态的基础上位与 11011111 即可 和1位与并不会改变原来位的状态 而和0位与 无论原来是0还是1 都会变成0 灯灭 15 2 3位或运算 位或运算的操作符为 将对两个操作数的每一位进行或运算 位 或 运算的准则如下 1 1 11 0 10 1 10 0 0不知道哪几盏灯亮着哪几盏灯灭着 想让第3盏灯亮起来 使用位或就能实现 只要在当前状态的基础上位或 00100000 即可 和0位或并不会改变原来位的状态 而和1位或 无论原来是0还是1 都会变成1 灯亮 15 2 4位异或 位或运算的操作符为 将对两个操作数的每一位进行异或运算 通俗地讲 如果位 异或 运算的两个位相同 同为0或同为1 结果为0 若两个位不同 一个为0 另一个为1 结果为1 对应的准则为 1 1 01 0 10 1 10 0 0位 反 位 与 位 或 和位 异或 运算符不关心操作数的符号 只是按操作数所在字节的0 1序列进行比对 符号位会被当成普通的0或1进行处理 15 2 5实例分析 演示了位取反 位与 位或和位异或几种运算符的用法 15 3移位运算 顾名思义 移位运算就是将某个量中的bits向左或向右移动 该量的值也会相应发生变化 在开灯关灯这个场景中 移位运算的一个重要应用是实现流水灯效果 即按从1到8或从8到1的顺序每次只亮一个灯 15 3 1基本形式 移位运算表达式的基本形式为 A n 右移 A称为操作数 其必须为数字型变量或数字型常量 此处的数字型包括整型 浮点型和char型 A中存储的0 1序列向左或右移动n位 移动后的值作为整个表达式的输出 执行移位运算并不改变操作数A的值 15 3 2移位举例 通过一个简单的例子来看一下移位运算的相关用法 见示例 代码 移位运算示例BitShift include 使用printf要包含的头文件 includevoidmain void 主函数 shortczs 19889 声明操作数czs 初始化 shortls 0 rs 0 声明两个结果变量 保存左移右移的结果 rs czs 4 左移操作 ls czs 4 右移操作 printf 19889左移4位结果是 d n ls 输出ls printf 19889右移4位结果是 d rs 输出rs getch 等待 按任意键继续 输出结果为 19889左移4位结果是 945619889右移4位结果是1243 15 4小结 尽管内存资源已不如早期程序设计时那么紧张 但位运算在很多方面有着独到的应用 位运算主要分为位逻辑运算和移位运算两大类 位逻辑运算主要有位取反