526互联

原码补码反码

发布时间 2023-09-09 14:46:25作者: Jue_Chen

二进制

题号 题型 分值
2020 第9题 单项选择 2分
2021 第3题 单项选择 2分
难易度：中等

计算机使用二进制，每一位上的数字由0和1组成。

为什么计算机选择二进制

很难在一种物质上体现十种不同的状态，即使表示出来也很容易出错。
电线的高、低电平（电压）表示两种状态非常方便，并且不容易出错。

二进制下的加减运算

二进制的加减法与十进制类似，加法时：十进制为逢十进一，二进制是逢二进一；减法时：十进制是借一当十，二进制是借一当二。

⚡快问快答 题目数量

1-1 二进制数 00100100 和 00010100 的和是( )。

A.00101000
B.01100111
C.01000100
D.00111000

1-2 在二进制下 1011001+()=1100110。

A. 1011
B. 1101
C. 1010
D. 1111

十进制和二进制下的加、减法有什么不同呢？

进位不同 逢十进一、逢二进一

借位不同 借一当十、借一当二


十进制转二进制

整数部分短除法、小数部分短乘法

二进制转十进制

每位数字乘以它的权重累加到一起。

  • 如何计算权重 二进制位权为2(数位−1)
  • 如何转换十进制 sum+=a[i]∗w

原码、反码和补码

机器数

与普通二进制数不同，最高位作为符号位，1表示负数，0表示正数，其余位数表示真值。

原码

原码就是用第一位表示符号，其余位表示值。比如如果是8位二进制：

反码

反码的表示方法是：

  • 正数的反码是其本身。
  • 负数的反码是在其原码的基础上，符号位不变，其余各个位取反。

补码

补码的表示方法是：

  • 正数的补码就是其本身。
  • 负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。（即在反码的基础上+1）

既然原码才是被人脑直接识别并用于计算表示方式，为何还会有反码和补码呢？

  • 电脑计算减法是转换成加法进行计算，且符号位参与到运算中。 但是：

  • 所以为了解决减法转换加法错误的问题，反码出现了。 但是：

  • 为了解决-0的问题，出现了补码。并且把-0的编码作为数字范围内的最小值，所以数字范围增加了1个。

  • 8位机器数能表示的数据范围： -128 ~ 127

  • 32位机器数能表示的数据范围：-2147483648 ~ 2147483647

历年真题

1-3 在二进制下，1011001+()=1100110。

A. 1011
B. 1101
C. 1010
D. 1111

1-4 二进制数 00100100 和 00010101 的和是（ ）。

A. 00101000
B. 001010100
C. 01000101
D. 00111001

1-5 二进制数 00100100 和 00010100 的和是( )。

A.00101000
B.01100111
C.01000100
D.00111000

1-6 在 8 位二进制补码中，10101011 表示的数是十进制下的( ).

A. 43
B. -85
C. -43
D. -84

1-7 二进制数 11.01 在十进制下是( ).

A. 3.25
B. 4.125
C. 6.25
D. 11.125

1-8 二进制数101.11对应的十进制数是（ ）。

A.6.5
B.5.5
C.5.75
D.5.25

1-9 十进制小数 13.375 对应的二进制数是（ ）。

A. 1101.011
B. 1011.011
C. 1101.101
D. 1010.01

1-10 一个自然数在十进制下有n位，则它在二进制下的位数与（ ）最接近。

A. 5n
B. n∗log2​ 10
C. 10∗log2​n
D. 10n ∗log2​ n

进制转换

题号	题型	分值

2020 第17题 阅读程序 13.5分
2020 第13题 单项选择 2分

不同的进制

在计算机中，除二进制外，比较常用的还有八进制和十六进制。

进制 基数 进位原则 基本符号
二进制(B) 2 逢2进1 0，1
八进制(O) 8 逢8进1 0~7
十进制(D) 10 逢10进1 0~9
十六进制(H) 16 逢16进1 0 ~ 9，A ~ F

  1. 十进制转化k进制
    （1）整数部分

短除法，除K取余，直到商是0，余数从下到上输出，即为K进制的整数部分。

例：十进制199转化成八进制

（2）小数部分

乘K取整，直到小数部分是0或达到指定精度，整数部分从上到下输出，即为K进制的小数部分。

例：十进制0.3125转化成八进制

:::info

绝大部分浮点数无法用二进制精确表示，如
0.1
:::

2.K进制转化成十进制
每一位上的数字乘以对应的位权，整数部分位权是K (数位−1)，小数部分的权分别为K −1、K −2…

例：八进制2032.12转换成十进制

(2032.12) 8​ =2×8 3 +0×8 2 +3×8 1 +2×8 0 +1×8 −1 +2×8−2=(1050.15625) 10
​

负数次幂

8 −1 =1/8=0.125
8 −2 =1/(8 2 )=0.015625

真题

1-11

1 	#include <iostream>
2 	using namespace std;
3 
4 	long long n, ans;
5 	int k, len;
6 	long long d[1000000];
7 
8 	int main() {
9 	  cin >> n >> k;
10	  d[0] = 0;
11	  len= 1;
12	  ans = 0;
13	  for (long long i = 0; i <n; ++i) {
14		++d[0];
15		for (int j = 0; j + 1<len; ++j) {
16		  if (d[j] == k) {
17			d[j] = 0;
18			d[j + 1] += 1;
19			++ans;
20		  }
21		}
22		if (d[len - 1] == k) {
23		  d[len - 1] = 0;
24		  d[len] =1;
25		  ++len;
26		  ++ans;
27		}
28	  }
29	  cout << ans << endl;
30	  return 0;
31	}

假设输入的n 是不超过2 62 的正整数，k都是不超过 10000 的正整数，完成下面的判断题和单选题：

•判断题
1）若 k=1，则输出 ans 时，len=n。（ ）
2）若k>1，则输出ans 时，len —定小于n。（ ）
3）若k>1，则输出ans 时，klen —定大于n。（ ）

•单选题
4）若输入的n 等于：10 15 ，输入的k 为 1，则输出等于（ ）。
A. 1
B. (1030 −1015 )/2
C. (1030 +1015 )/2
D. 10^15

5）若输入的n 等于205,891,132,094,649（即 3 30 ），输入的k 为 3，则输出等于（ ）。
A. 3 30
B.(330 −1)/2
C. 330 −1
D. (330 +1)/2

6）若输入的n 等于100,010,002,000,090，输入的k 为 10，则输出等于（ ）。
A. 11,112,222,444,543
B. 11,122,222,444,453
C. 11,122,222,444,543
D. 11,112,222,444,453

1-12 八进制数 32.1 对应的十进制数是（ ）。

A 24.125
B 24.250
C 26.125
D 26.250

1-13 二进制数101.11对应的十进制数是（ ）。

A.6.5
B.5.5
C.5.75
D.5.25

1-14 下列四个不同进制的数中，与其它三项数值上不相等的是

A.(269) 16

B. (617) 10

C.(1151) 8

D. (1001101011) 2

位运算

近3年初赛考察：

题号 题型 分值
2021 第16题第3、4、5、6小题 阅读程序 7.5分
2021 第17题 阅读程序 14分
2022 第16题第3、4、5小题 阅读程序 4.5分

作用于整数类型的运算对象，对二进制数位进行运算。

位与：& 当且仅当两个运算对象都为1时，该位为1

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

eg: 255 & 128 = 128

位或：| 当且仅当两个运算对象都为0时，该位为0

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

eg: 255 | 128 = 255

位取反：~ 将1置为0，将0置为1

~ 1 = 0
0 = 1

eg: ~ 128 = 127

位异或：^ 当且仅当两个运算对象中只一个为1时，该位为1

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
eg: 255 ^ 128 = 127

左移： <<

将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

左边二进制位丢弃不包括1时, 左移1位相当于乘以2。

eg: 3 << 2 = 12 (1100)

右移： >>

将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃.

右移1位相当于除以2（整数除法）。

eg: 7 >> 1 变成 3，也就是111 >> 1 变成了 11。

真题

1-15

18^ 125 ^125 =（）
A 127
B 143
C 18
D 125

位运算的性质

x ^ x = 0 : 自己与自己做异或一定为0

x ^ 0 = x : 一个数与0做异或还是它本身

位运算的应用：

::: info
位运算的应用较多，写法种类也有多种。下面的应用，建议大家只是在本地都要运行一遍，加深记忆。

此外考场上难免会有不知道的位运算应用，这个时候，手算，对比，找规律，就是最好的方式。
:::

  • 取末位(x & 1) 可用来判断奇数、偶数

  • 操作x的第j位（从右向左数，最右边是第0位）

x | (1 << j)  //将 x 的第 j 位设置为1

x & ~(1 << j) //将 x 的第 j 位设置为0

x ^ (1 << j)  //将 x 的第 j 位取反

(x >> j) & 1  //取 x 的第 j 位

  • 交换两个数: a ^= b ^= a ^= b;

  • lowbit 运算

int lowbit(int x) {
  // 计算 x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;  // CSP中考过lowbit另一种写法 x&(x^(x-1))
}

真题

1-16

01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07     unsigned short x, y;
08     cin >> x >> y;
09     x = (x | x << 2) & 0x33;
10     x = (x | x << 1) & 0x55;
11     y = (y | y << 2) & 0x33;
12     y = (y | y << 1) & 0x55;
13     unsigned short z = x | y << 1;
14     cout << z << endl;
15     return 0;
16 }

假设输入的 x、y 均是不超过 15 的自然数，完成下面的判断题和单选题：

判断题
16.删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ）
17.将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）
18.程序总是输出一个整数“0”。（ ）
19. 当输入为“2 2”时，输出为“10”。（ ）
20. 当输入为“2 2”时，输出为“59”。（ ）

单选题
21.当输入为“13 8”时，输出为（ ）。
A. “0”
B. “209”
C. “197”
D. “226”

1-17 一个字长为8位的整数的补码是11111001，则它的原码是( ).

A. 00000111
B. 01111001
C. 11111001
D. 10000111

1-18 为了统计一个非负整数的二进制形式中 1 的个数，代码如下：

int CountBit(int x)
{
	int ret = 0;
	while (x)
	{
		ret++;
		___________;
	}
	return ret;
}

要填入的语句是（ ）。

A. x >>= 1
B. x &= x - 1
C. x |= x >> 1
D. x <<= 1

1-19 二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是( ).

A. 01 0010 1000 1011
B. 01 0010 1001 0011
C. 01 0010 1000 0001
D. 01 0010 1000 0011

2 逻辑运算

（1）与运算

在数学符号中，我们常用『∧』来表示， 类似于集合中的交集， 在 C++语言中， 与运算我们用“&&”
或者 “ and ” 来表示。一般两个逻辑表达式，我们都用小括号括起来，这是比较良好的代码习惯。
x 能被 3 整除， 且能被 5 整除 (x%3 == 0) && (x%5 == 0)
语文成绩高于 90，数学高于 95 (yw>90) && (sx>95)
运算规则：很显然， 与运算中， 只有所以条件都为真时， 整个条件才为真，只要出现某个条件为假，
整个条件就是假。

（2）或运算

在数学符号中， 我们常用『∨』来表示， 类似于集合中的并集， 在 C++语言中， 或运算我们用“||”
或者 “ or ” 来表示。
乘坐公车，身高低于 1.2m 或年龄高于 60 岁的免票 (h<1.2) || (y>60)
语文超过 95 或数学超过 98 的获单科奖 (yw>95) || (sx>98)
运算规则：很显然，或运算中，只要有一个条件为真时， 整个条件就为真， 只有全部条件都为假，
整个条件才是假。

（3）非运算

非运算，在数学符号中， 我们常用『﹁』来表示，类似于集合中的补集，在 C++语言中，非运算我
们用 “!” 来表示。
a == 0 // a 等于 0
!(a==0) // 非运算，相当于 (a<0) || (a>0) 也可以写成 a != 0
b > 2 // b 大于 2
!(b>2) // 非运算，相当于 b<= 2
运算规则：很显然，非运算中，真条件的非运算是假，假条件的非运算是真。

（4）异或运算

异或相对上面几个，使用的相对较少，它是一个很奇怪的运算，它一般用在两个条件之间，运算的 规则是两个条件相同，即同样为真或同样为假，那它的结果就是假；而如果两个条件不同，即一真一假 时， 它的结果就为真。异或比较常用在『博弈论』里面。异或运算， 在数学符号中，我们常用『⊕』来表
示，在 C++语言中， 与运算我们用 “^” 或者 “ xor ” 来表示。

【逻辑运算练习】

1-20、

【2010 提高（同 2010 普及）】以下逻辑表达式的值恒为真的是（） 。
A． PV（﹁PΛQ） V(﹁PΛ﹁Q)
B．QV（﹁PΛQ） V（PΛ﹁Q）
C． PVQV（PΛ﹁Q） V（﹁PΛQ）
D． PV﹁QV（PΛ﹁Q） V(﹁PΛ﹁Q)

1-21

2、【2008 提高（多选）】若 A=True，B=False，C=True，D=False，以下逻辑运算表达式真的有( )。
A．（AΛB） V（C Λ D V ﹁A） B． （（﹁AΛB） VC） Λ﹁B
C．（BVC VD） VDΛA D．A Λ（DV﹁C） Λ B

1-22

3、【2008 普及】设 A=true，B=false ，C=true ，D=false，以下逻辑运算表达式值为真的是( )。
A. (AΛB)V(CΛDV﹁A) B. ((﹁AΛB)VC)Λ﹁D
C. (BVC VD)ΛDΛA D. AΛ(DV﹁C)ΛB

1-23

4、【2007 普及】设 A=B=True，C=D=False，—下逻辑运算表达式值为假的有( )。
A．(﹁AΛB)V(CΛDVA) B．﹁(((AΛB)VC)ΛD)
C．AΛ(BVC VD)VD D．(AΛ(DVC))ΛB

1-24

5、【2006 提高（多选） 】设 A=B=D=true，C=E=false，以下为真的有（ ）。
A. (AΛB)V(CΛD)VE
B. (((AΛB)VC)ΛDΛE)
C. AΛ(B VC VD VE) D. (AΛ(BVC))ΛDΛE

1-25

  1. 设全集 E={1,2,3,4,5}，集合 A={1,4}，B={2,5}，集合 C={2,4}，则集合（AnB） U~C 为( )
    A.空集 B. {1} C. {3,5} D.

1-26

  1. 设全集 I={a,b,c,d,e,f,g,h}，集合 BUA= {a,b,c,d,e,f}，CnA= {c,d,e} ，~BnA={a,d}，那么集合 CnBnA
    为( )
    A.{c,e} B. {d,e} C. {e} D.

1-27

  1. 在 C++中，表达式 21^2 的值是( )
    A.441 B. 42 C. 23 D.24

1-28

  1. 在 C++中，表达式 23 | 2^5 的值是( )
    A. 23 B. 1 C. 32 D. 18