二进制与编码江苏省句容高级中学

2011信 息 学 奥 赛 基 础 知 识（ 进 制 与 编 码 ）一 、 进 制 转 换四 种 常 用 的 数 制 及 它 们 之 间 的 相 互 转 换 ：进 制 基 数 符 号 基 数 个 数 权 进 数 规 律十 进 制 0、 1、 2、 3、 4、 5、 6、 7、 8、9 D 10 10i 逢 十 进 一二 进 制 0、 1 B 2 2i 逢 二 进 一八 进 制 0、 1、 2、 3、 4、 5、 6、 7 O 8 8i 逢 八 进 一十 六 进 制 0、 1、 2、 3、 4、 5、 6、 7、 8、9、 A、 B、 C、 D、 E、 F H 16 16i 逢 十 六 进 一二 进 制 数 、 八 进 制 数 、 十 六 进 制 数 转 换 为 十 进 制 数 的 方 法 ： 按 权 展 开 求 和 法十 进 制 数 转 换 为 二 进 制 数 、 八 进 制 数 、 十 六 进 制 数 的 方 法 ： 整 数 部 分 短 除 法 逆 向 取余 ， 小 数 部 分 正 向 取 整1 二 进 制 与 十 进 制 间 的 相 互 转 换 ：（ 1） 二 进 制 转 十 进 制 方 法 ： “ 按 权 展 开 求 和 ”例 ： （ 1011.01） 2 （ 1 23 0 22 1 21 1 20 0 2 1 1 2 2 ） 10 （ 8 0 2 1 0 0.25） 10 （ 11.25） 10规 律 ： 个 位 上 的 数 字 的 次 数 是 0， 十 位 上 的 数 字 的 次 数 是 1， ， 依 次 递 增 ， 而 十分 位 的 数 字 的 次 数 是 -1， 百 分 位 上 数 字 的 次 数 是 -2， ， 依 次 递 减 。注 意 ： 不 是 任 何 一 个 十 进 制 小 数 都 能 转 换 成 有 限 位 的 二 进 制 数 。（ 2） 十 进 制 转 二 进 制十 进 制 整 数 转 二 进 制 数 ： “ 除 以 2取 余 ， 逆 序 排 列 ” （ 短 除 反 取 余 法 ）例 ： （ 89） 10 （ 1011001） 22 892 44 12 22 02 11 02 5 12 2 12 1 00 1十 进 制 小 数 转 二 进 制 数 ： “ 乘 以 2取 整 ， 顺 序 排 列 ” （ 乘 2顺 取 整 法 ）2 八 进 制 与 二 进 制 的 转 换 ：二 进 制 数 转 换 成 八 进 制 数 ： 从 小 数 点 开 始 ， 整 数 部 分 向 左 、 小 数 部 分 向 右 ， 每 3 位 为一 组 用 一 位 八 进 制 数 的 数 字 表 示 ， 不 足 3位 的 要 用 “ 0” 补 足 3位 ， 就 得 到 一 个 八 进 制数 。八 进 制 数 转 换 成 二 进 制 数 ： 把 每 一 个 八 进 制 数 转 换 成 3位 的 二 进 制 数 ， 就 得 到 一 个 二进 制 数 。例 ： 将 八 进 制 的 37.416转 换 成 二 进 制 数 ：3 7 4 1 6011 111 100 001 110即 ： （ 37.416） 8 （ 11111.10000111） 2例 ： 将 二 进 制 的 10110.0011 转 换 成 八 进 制 ：0 1 0 1 1 0 . 0 0 1 1 0 02 6 . 1 4即 ： （ 10110.011） 2 （ 26.14） 83 十 六 进 制 与 二 进 制 的 转 换 ：二 进 制 数 转 换 成 十 六 进 制 数 ： 从 小 数 点 开 始 ， 整 数 部 分 向 左 、 小 数 部 分 向 右 ， 每 4位为 一 组 用 一 位 十 六 进 制 数 的 数 字 表 示 ， 不 足 4位 的 要 用 “ 0” 补 足 4位 ， 就 得 到 一 个 十六 进 制 数 。十 六 进 制 数 转 换 成 二 进 制 数 ： 把 每 一 个 八 进 制 数 转 换 成 4 位 的 二 进 制 数 ， 就 得 到 一 个二 进 制 数 。 例 ： 将 十 六 进 制 数 5DF.9 转 换 成 二 进 制 ：5 D F 90101 1101 1111 1001即 ： （ 5DF.9） 16 （ 10111011111.1001） 2例 ： 将 二 进 制 数 1100001.111 转 换 成 十 六 进 制 ：0110 0001 11106 1 E即 ： （ 1100001.111） 2 （ 61.E） 16注 意 ： 以 上 所 说 的 二 进 制 数 均 是 无 符 号 的 数 。 这 些 数 的 范 围 如 下 表 ：无 符 号 位 二 进 制 数位 数 数 值 范 围 十 六 进 制 范 围 表 示 法8位 二 进 制 数 0255 （ 255=28-1） 000FFH16位 二 进 制 数 065535 （ 65535=216-1） 0000H0FFFFH32位 二 进 制 数 0232-1 00000000H0FFFFFFFFHBCD 码 即 BCD代 码 。 Binary-Coded Decimal ， 简 称 BCD， 称 BCD 码 或 二 -十 进 制 代码 ， 亦 称 二 进 码 十 进 数 。 是 一 种 二 进 制 的 数 字 编 码 形 式 ， 用 二 进 制 编 码 的 十 进 制 代 码 。这 种 编 码 形 式 利 用 了 四 个 位 元 来 储 存 一 个 十 进 制 的 数 码 ， 使 二 进 制 和 十 进 制 之 间 的 转换 得 以 快 捷 的 进 行 。 这 种 编 码 技 巧 ， 最 常 用 于 会 计 系 统 的 设 计 里 ， 因 为 会 计 制 度 经 常需 要 对 很 长 的 数 字 串 作 准 确 的 计 算 。 相 对 于 一 般 的 浮 点 式 记 数 法 ， 采 用 BCD码 ， 既 可保 存 数 值 的 精 确 度 ， 又 可 免 却 使 电 脑 作 浮 点 运 算 时 所 耗 费 的 时 间 。 此 外 ， 对 于 其 他 需要 高 精 确 度 的 计 算 ， BCD编 码 亦 很 常 用 。 例 ： 3 2 1 的 BCD代 码 为 0011 0010 0001二 、 原 码 、 反 码 、 补 码计 算 机 中 参 与 运 算 的 数 有 正 负 之 分 ， 计 算 机 中 的 数 的 正 负 号 也 是 用 二 进 制 表 示 的 。用 二 进 制 数 表 示 符 号 的 数 称 为 机 器 码 。 常 用 的 机 器 码 有 原 码 、 反 码 和 补 码 。1、 原 码求 原 码 的 方 法 ： 设 X； 若 X 0， 则 符 号 位 （ 原 码 最 高 位 ） 为 0， X其 余 各 位 取 值 照 抄 ；若 X 0， 则 符 号 位 为 1， 其 余 各 位 照 抄 。【 例 1】 X=+1001001 X原 = 01001001 【 例 2】 X=-1001001 X原 = 110010012、 反 码求 反 码 的 方 法 ： 设 X； 若 X 0， 则 符 号 位 （ 原 码 最 高 位 ） 为 0， X其 余 各 位 取 值 照 抄 ；若 X 0， 则 符 号 位 为 1， 其 余 各 位 按 位 取 反 。【 例 3】 X=+1001001 X反 = 01001001 【 例 4】 X=-1001001 X反 = 101101103、 补 码求 补 码 的 方 法 ： 设 X； 若 X 0， 则 符 号 位 （ 原 码 最 高 位 ） 为 0， X其 余 各 位 取 值 照 抄 ；若 X 0， 则 符 号 位 为 1， 其 余 各 位 按 位 取 反 后 ， 最 低 位 加 1。【 例 5】 X=+1001001 X补 = 01001001 【 例 6】 X=-1001001 X补 = 101101114、 补 码 加 减 法计 算 机 中 实 际 上 只 有 加 法 ， 减 法 运 算 转 换 成 加 法 运 算 进 行 ， 乘 法 运 算 转 换 成 加 法 运算 进 行 ， 除 法 运 算 转 换 成 减 法 运 算 进 行 。 用 补 码 可 以 很 方 便 的 进 行 这 种 运 算 。1、 补 码 加 法X+Y补 = X补 + Y补【 例 7】 X=+0110011,Y=-0101001， 求 X+Y补X补 =00110011 Y补 =11010111X+Y补 = X补 + Y补 = 00110011+11010111=00001010注 ： 因 为 计 算 机 中 运 算 器 的 位 长 是 固 定 的 ， 上 述 运 算 中 产 生 的 最 高 位 进 位 将 丢 掉 ，所 以 结 果 不 是 100001010， 而 是 00001010。2、 补 码 减 法X-Y补 = X补 - Y补 = X补 + -Y补其 中 -Y补 称 为 负 补 ， 求 负 补 的 方 法 是 ： 对 补 码 的 每 一 位 （ 包 括 符 号 位 ） 求 反 ， 最后 末 位 加 “ 1” 。【 例 8】 X=+0111001,Y=+1001101， 求 X-Y补X补 =00111001 Y补 =01001101 -Y补 = 10110011X-Y补 = X补 + -Y补 = 00111001+10110011=111011005、 数 的 表 示 范 围通 过 上 面 的 学 习 ， 我 们 就 可 以 知 道 计 算 机 如 果 用 一 个 字 节 表 示 一 个 整 数 的 时 候 ，如 果 是 无 符 号 数 ， 可 以 表 示 0255共 256个 数 （ 0000000011111111） ， 如 果 是 有 符 号数 则 能 表 示 -128127共 256个 数 （ 1000000001111111） 。 如 果 两 个 字 节 表 示 一 个 整 数 ，则 共 有 65536个 数 可 以 表 示 ， 大 部 分 程 序 设 计 语 言 中 整 数 的 范 围 都 是 -3276832767的原 因 ， 可 以 看 出 这 种 整 数 类 型 是 16位 的 有 符 号 数 ， 而 且 是 补 码 表 示 的 。带 符 号 数 的 机 器 码 表 示 方 法 ， n位 范 围 是 -2n-1到 2n-1-1。下 表 列 出 128127,39,0 及 的 8 位 二 进 制 原 码 ， 反 码 和 补 码 并 将 补 码 用 十 六 进 制 表示 。 真 值 原 码 （ B） 反 码 （ B） 补 码 （ B） 补 码 （ H）+127 0 111 1111 0 111 1111 0 111 1111 7F+39 0 010 0111 0 010 0111 0 010 0111 27+0 0 000 0000 0 000 0000 0 000 0000 00-0 1 000 0000 1 111 1111 0 000 0000 00-39 1 010 0111 1 101 1000 1 101 1001 D9-127 1 111 1111 1 000 0000 1 000 0001 81-128 无 法 表 示 无 法 表 示 1 000 0000 80从 上 可 看 出 ， 真 值 +0和 -0的 补 码 表 示 是 一 致 的 ， 但 在 原 码 和 反 码 表 示 中 具 有 不 同形 式 。 8 位 补 码 机 器 数 可 以 表 示 -128， 但 不 存 在 +128 的 补 码 与 之 对 应 ， 由 此 可 知 ， 8位 二 进 制 补 码 能 表 示 数 的 范 围 是 -128 +127。 还 要 注 意 ， 不 存 在 -128的 8位 原 码 和反 码 形 式 。三 、 奇 偶 校 验计 算 机 中 数 据 在 进 行 存 储 和 传 输 过 程 中 可 能 会 发 生 错 误 。 为 了 及 时 发 现 和 纠 正 这类 错 误 ， 在 数 据 传 输 （ 存 储 ） 过 程 中 要 进 行 校 验 ， 常 用 的 校 验 方 法 就 是 奇 偶 校 验 。奇 偶 校 验 能 发 现 一 位 或 奇 数 位 错 误 ， 且 不 能 纠 正 错 误 。 一 般 以 字 节 （ 八 位 二 进 制 ） 为单 位 加 1位 奇 偶 校 验 位 。 奇 偶 校 验 分 奇 校 验 和 偶 校 验 两 种 。奇 校 验 ： 一 个 字 节 前 面 加 一 位 校 验 位 使 得 “ 1” 的 个 数 保 持 为 奇 数 ， 若 八 位 二 进 制数 中 “ 1” 的 个 数 为 偶 数 ， 则 校 验 位 为 “ 1” ； 若 八 位 二 进 制 数 中 “ 1” 的 个 数 为 奇 数 ，则 校 验 位 为 “ 0” 。【 例 1】 给 10011001 01101101加 奇 校 验 结 果 为 110011001 001101101偶 校 验 ： 一 个 字 节 前 面 加 一 位 校 验 位 使 得 “ 1” 的 个 数 保 持 为 偶 数 ， 若 八 位 二 进 制 数 中“ 1” 的 个 数 为 偶 数 ， 则 校 验 位 为 “ 0” ； 若 八 位 二 进 制 数 中 “ 1” 的 个 数 为 奇 数 ， 则 校验 位 为 “ 1” 。【 例 2】 给 10011001 01101101加 偶 校 验 结 果 为 010011001 101101101四 、 信 息 存 贮（ 一 ） 定 点 数 （ Fixed-Point Number）计 算 机 处 理 的 数 据 不 仅 有 符 号 ， 而 且 大 量 的 数 据 带 有 小 数 ， 小 数 点 不 占 有 二 进 制一 位 而 是 隐 含 在 机 器 数 里 某 个 固 定 位 置 上 （ 实 际 不 存 在 ） 。 通 常 采 取 两 种 简 单 的 约 定 ：一 种 是 约 定 所 有 机 器 数 的 小 数 的 小 数 点 位 置 隐 含 在 机 器 数 的 最 低 位 之 后 ， 叫 定 点 纯 整机 器 数 ， 简 称 定 点 整 数 。 另 一 种 约 定 所 有 机 器 数 的 小 数 点 隐 含 在 符 号 位 之 后 、 有 效 部分 最 高 位 之 前 ， 叫 定 点 纯 小 数 机 器 数 ， 简 称 定 点 小 数 。 无 论 是 定 点 整 数 ， 还 是 定 点 小数 ， 都 可 以 有 原 码 、 反 码 和 补 码 三 种 形 式 。（ 二 ） 浮 点 数 （ Floating-Point Number）计 算 机 多 数 情 况 下 采 用 作 浮 点 数 表 示 数 值 ， 它 与 科 学 计 数 法 相 似 ， 把 一 个 二 进 制数 通 过 移 动 小 数 点 位 置 表 示 成 阶 码 和 尾 数 两 部 分 ：SN E 2其 中 ： E N的 阶 码 （ Expoent） ， 是 有 符 号 的 整 数S N的 尾 数 （ Mantissa） ， 是 数 值 的 有 效 数 字 部 分 ， 一 般 规 定 取 二 进 制 定点 纯 小 数 形 式 。例 ： 1011101B=2+7*0.1011101， 101.1101B=2+3*0.1011101， 0.01011101B=2-1*0.1011101浮 点 数 的 格 式 如 下 ：E0 E1E2 En E0 E1E2 En阶 符 阶 尾 符 尾 数浮 点 数 由 阶 码 和 尾 数 两 部 分 组 成 ， 底 数 2不 出 现 ， 是 隐 含 的 。 阶 码 的 正 负 符 号 E0，在 最 前 位 ， 阶 反 映 了 数 N 小 数 点 的 位 置 ， 常 用 补 码 表 示 。 二 进 制 数 N 小 数 点 每 左 移 一位 ， 阶 增 加 1。 尾 数 是 这 点 小 数 ， 常 取 补 码 或 原 码 ， 码 制 不 一 定 与 阶 码 相 同 ， 数 N 的小 数 点 右 移 一 位 ， 在 浮 点 数 中 表 现 为 尾 数 左 移 一 位 。 尾 数 的 长 度 决 定 了 数 N的 精 度 。尾 数 符 号 叫 尾 符 ， 是 数 N的 符 号 ， 也 占 一 位 。例 ： 写 出 二 进 制 数 -101.1101B的 浮 点 数 形 式 ， 设 阶 码 取 4位 补 码 ， 尾 数 是 8位 原码 。 -101.1101=-0.1011101*2+3浮 点 形 式 为 ： 阶 码 0011 尾 数 11011101补 充 解 释 ： 阶 码 0011中 的 最 高 位 “ 0” 表 示 指 数 的 符 号 是 正 号 ， 后 面 的 “ 011” 表示 指 数 是 “ 3” ； 尾 数 11011101 的 最 高 位 “ 1” 表 明 整 个 小 数 是 负 数 ， 余 下 的 1011101是 真 正 的 尾 数 。 例 ： 计 算 机 浮 点 数 格 式 如 下 ， 写 出 x=0.0001101B的 规 格 化 形 式 ， 阶 码是 补 码 ， 尾 数 是 原 码 。x=0.0001101=0.1101*10-3 又 -3补 =-001B补 =1011补 =1101B所 以 浮 点 数 形 式 是ASCII 码 ( American Standard Code for Information Interchange)美 国 标 准 信 息交 换 代 码 ， 将 每 个 字 符 用 7位 的 二 进 制 数 来 表 示 ， 共 有 128种 状 态1 101 0 1101000 0 48 A 65 a 97汉 字 信 息 编 码1 汉 字 输 入 码 （ 外 码 ）汉 字 输 入 方 法 大 体 可 分 为 ： 区 位 码 （ 数 字 码 ） 、 音 码 、 形 码 、 音 形 码 。 区 位 码 ： 优 点 是 无 重 码 或 重 码 率 低 ， 缺 点 是 难 于 记 忆 ； 音 码 ： 优 点 是 大 多 数 人 都 易 于 掌 握 ， 但 同 音 字 多 ， 重 码 率 高 ， 影 响 输 入 的 速 度 ； 形 码 ： 根 据 汉 字 的 字 型 进 行 编 码 ， 编 码 的 规 则 较 多 ， 难 于 记 忆 ， 必 须 经 过 训 练 才 能较 好 地 掌 握 ； 重 码 率 低 ； 音 形 码 ： 将 音 码 和 形 码 结 合 起 来 ， 输 入 汉 字 ， 减 少 重 码 率 ， 提 高 汉 字 输 入 速 度 。2 汉 字 交 换 码汉 字 交 换 码 是 指 不 同 的 具 有 汉 字 处 理 功 能 的 计 算 机 系 统 之 间 在 交 换 汉 字 信 息 时 所使 用 的 代 码 标 准 。 自 国 家 标 准 GB2312 80公 布 以 来 ， 我 国 一 直 沿 用 该 标 准 所 规 定 的 国标 码 作 为 统 一 的 汉 字 信 息 交 换 码 。GB2312 80标 准 包 括 了 6763个 汉 字 ， 按 其 使 用 频 度 分 为 一 级 汉 字 3755个 和 二 级汉 字 3008个 。 一 级 汉 字 按 拼 音 排 序 ， 二 级 汉 字 按 部 首 排 序 。 此 外 ， 该 标 准 还 包 括 标 点符 号 、 数 种 西 文 字 母 、 图 形 、 数 码 等 符 号 682个 。由 于 GB2312 80 是 80年 代 制 定 的 标 准 ， 在 实 际 应 用 时 常 常 感 到 不 够 ， 所 以 ， 建议 处 理 文 字 信 息 的 产 品 采 用 新 颁 布 的 GB18030 信 息 交 换 用 汉 字 编 码 字 符 集 ， 这 个 标 准繁 、 简 字 均 处 同 一 平 台 ， 可 解 决 两 岸 三 地 间 GB码 与 BIG5码 间 的 字 码 转 换 不 便 的 问 题 。3 字 形 存 储 码字 形 存 储 码 是 指 供 计 算 机 输 出 汉 字 （ 显 示 或 打 印 ） 用 的 二 进 制 信 息 ， 也 称 字 模 。通 常 ， 采 用 的 是 数 字 化 点 阵 字 模 。 一 般 的 点 阵 规 模 有 16 16， 24 24， 32 32， 6464等 ， 每 一 个 点 在 存 储 器 中 用 一 个 二 进 制 位 （ bit） 存 储 。 例 如 ， 在 16 16的 点 阵 中 ，需 16 16bit=32 byte 的 存 储 空 间 。 在 相 同 点 阵 中 ， 不 管 其 笔 划 繁 简 ， 每 个 汉 字 所 占的 字 节 数 相 等 。为 了 节 省 存 储 空 间 ， 普 遍 采 用 了 字 形 数 据 压 缩 技 术 。 所 谓 的 矢 量 汉 字 是 指 用 矢 量方 法 将 汉 字 点 阵 字 模 进 行 压 缩 后 得 到 的 汉 字 字 形 的 数 字 化 信 息 。五 、 运 算 法 则二 进 制 的 算 术 运 算1、 加 法 运 算 规 则 ：0+0=0 0+1=1 1+0=1 1+1=102、 减 法 运 算 规 则 ：0-0=0 0-1=1（ 向 高 位 借 1） 1-0=1 1-1=03、 乘 法 运 算 规 则 ：0 0=0 0 1=0 1 0=0 1 1=1Pascal 的 运 算 符表 达 式 是 用 运 算 符 号 或 小 括 号 将 常 量 、 变 量 、 函 数 连 接 成 的 式 子 。 Pascal表 达 式中 只 有 小 括 号 。 运 算 符 也 称 为 算 符 ， 算 符 的 操 作 对 象 称 为 操 作 数 。运 算 符 按 带 操 作 数 的 个 数 分 为 两 类 ：A. 单 目 运 算 符 ： 对 一 个 操 作 数 操 作 。 -（ 负 号 ） ， +（ 正 号 ）B. 双 目 运 算 符 ： 对 两 个 操 作 数 操 作 。根 据 运 算 符 运 算 的 意 义 不 同 分 为 算 术 运 算 、 布 尔 运 算 、 逻 辑 运 算 、 关 系 运 算 。根 据 运 算 符 的 优 先 级 可 以 将 运 算 符 分 为 单 目 运 算 、 “ 乘 ” 的 关 系 运 算 、 “ 和 ” 的 关 系 运算 、 关 系 运 算 。算 术 运 算 符一 共 有 8 个 。 操 作 数 都 是 数 值 型 ， 结 果 也 是 数 值 型 。 单 目 运 算 符 有 （ ） 取 正 、（ ） 取 负 。 双 目 运 算 符 有 （ ） 加 、 （ ） 减 、 （ ） 乘 、 （ /） 除 、 （ DIV） 取 商 、 （ Mod）取 余 。1. “ /” 左 右 的 操 作 数 是 数 值 型 ， 结 果 是 实 型 数 。2. Div 左 右 的 操 作 数 是 整 型 ， 结 果 是 整 型 （ 两 数 之 商 ） 。3. Mod 左 右 的 操 作 数 是 整 型 数 ， 结 果 是 整 型 数 （ 两 数 相 除 之 余 ） 。4. 在 PASCAL只 有 上 面 8种 数 学 运 算 。 其 它 的 就 只 能 利 用 这 8 种 运 算 的 组 合 通 过语 句 来 实 现 。 如 a2（ a的 平 方 ） 可 以 化 成 a*a。 XY 可 写 成 exp(y*ln(X)关 系 运 算 符系 运 算 是 指 同 一 类 型 的 两 个 数 据 进 行 比 较 ， 结 果 是 一 个 布 尔 类 型 值 。用 小 括 号 、 、 =、 将 两 个 算 术 表 达 式 连 接 起 来 的 式 子 就 称 为 关 系 表 达 式（ 比 较 式 ） 。 如 ： 3+78,x+y,=,=,）在 同 级 运 算 中 ， 按 从 左 到 右 的 顺 序 计 算位 运 算程 序 中 的 所 有 数 在 计 算 机 内 存 中 都 是 以 二 进 制 的 形 式 储 存 的 。 位 运 算 说 穿 了 ， 就 是直 接 对 整 数 在 内 存 中 的 二 进 制 位 进 行 操 作 。 比 如 ， and 运 算 本 来 是 一 个 逻 辑 运 算 符 ，但 整 数 与 整 数 之 间 也 可 以 进 行 and 运 算 。 举 个 例 子 ， 6 的 二 进 制 是 110， 11 的 二 进制 是 1011， 那 么 6 and 11 的 结 果 就 是 2， 它 是 二 进 制 对 应 位 进 行 逻 辑 运 算 的 结 果（ 0 表 示 False， 1 表 示 True， 空 位 都 当 0 处 理 ） ：按 位 与参 与 运 算 的 量 ， 如 果 相 对 应 的 两 位 都 为 1， 则 该 位 的 结 果 值 为 1， 否 则