信息学奥赛初赛天天练-15-阅读程序-深入解析二进制原码、反码、补码，位运算技巧，以及lowbit的神奇应用

更多资源请关注纽扣编程微信公众号

1 2021 CSP-J 阅读程序1

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填×；除特 殊说明外，判断题 1.5 分，选择题 3 分）

源码

#include<stdio.h>
using namespace std;int n;
int a[1000];int f(int x)//计算二进制1中1的个数
{int ret = 0;/*2 对应二进制 10 ，包含1个110&1=0 ret累加1次退出循环3对应二进制101，包含2个1101 & 100=100100&011=0 ret累加2次退出循环*/for(;x;x&=x-1) ret++;return ret;
}
/*lowbit 是将 x 转化成二进制数之后，只保留最低位（从右往左数，第一位）的1及其后面的0，截断前面的内容，然后再转成10进制数lowbit(8)=8//8对应二进制为：1000 取最右边的1及后面3个0lowbit(12)=4//12对应二进制位：1100 取最右边的1及后面3个0lowbit(5)=1//5对应二进制为 101 取最右边1及其后面的0*/
int g(int x)
{return x & -x;
}int main()
{scanf("%d",&n);for (int i=0;i<n;i++) scanf("%d",&a[i]);for(int i=0;i<n;i++)printf("%d ",f(a[i])+g(a[i]));printf("\n");return 0;
}

判断题

1 输入的n等于1001时，程序不会发生下标越界( F )

2 输入的a[i]必须全为正整数，否则程序将陷入死循环( F )

3 当输入为“5 2 11 9 16 10” 时，输出“3 4 3 17 5” ( F )

4 当输入为“1 511998 ”时，输出为"18" （ T ）

5 将原码中g函数的定义(13 -16行) 移到main函数的后面，程序可以正常编译运行( F )

单选题

6 当输入为"2 -65536 2147483647"时，输出为 ( B )

A. “65532 33”

B. “65552 32”

C. “65535 34”

D. “65554 33”

2 相关知识点

for 循环语句

重复执行一段代码，直到满足指定条件为止，使用三个表达式控制循环的初始化、退出条件和自变量更新，这3个表达式可以同时出现也可以部分出现

for (初始化表达式; 退出条件; 自变量更新) {// 循环体代码
}

示例代码

#include<bits/stdc++.h>
using namespace std;
/*for循环语句练习 
*/
int main(){//初始化表达式; 退出条件; 自变量更新 同时出现 for(int i=0;i<5;i++){cout<<i<<" ";}cout<<endl;//初始化表达式 提前定义 int i=0; for(;i<5;i++){cout<<i<<" ";}cout<<endl;//初始化表达式 提前定义  退出条件在循环题 i=0; for(;;i++){if(i>=5) break; cout<<i<<" ";}cout<<endl;//初始化表达式 提前定义  退出条件在循环题 自变量在循环体 i=0; for(;;){if(i>=5) break; cout<<i<<" ";i++;}return 0;
}

原码、反码和补码

1) 机器数

一个数在计算机中的二进制表示形式，叫做这个数的机器数。机器数是带符号的，在计算机用机器数的最高位存放符号，正数为0，负数为1

4  对应二进制 0000 0100
-4 对应二进制 1000 0100

2) 机器数真值

机器数第一位为符号位，所以机器数的形式值不等于真正的数值。所以，将带符号位的机器数对应的真正数值称为机器数的真值

0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1

3) 原码

原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值

+2 的原码 0000 0010
-2 的原码 1000 0010

4) 反码

正数的反码是其本身

负数的反码是对原码进行符号位不变，其余各个位取反

+2 的原码 0000 0010   反码 0000 0010
-2 的原码 1000 0010   反码 1111 1101

5) 补码

正数的补码就是其本身

负数的反码是对反码+1

+2 的原码 0000 0010   反码 0000 0010  补码  0000 0010
-2 的原码 1000 0010   反码 1111 1101  补码  1111 1110

位运算

1) 取反运算(~)

是转换2进制后，每1位取反，0变1，1变0

示例代码

//按位取反 ~
#include<bits/stdc++.h>
using namespace std;int main(){/*正数的原码，反码，补码都是相同4 对应二进制 0000 0100 按位取反1111 1011 计算机是以补码形式存在，需要转换成原码-1变成反码1111 1010按位取反变成原码1000 0101 第1位是符号位，所以结果是-5 */ int a=4;int b=~a;//转二进制补码后按位取反后再转成原码 cout<<b; //结果是-5 return 0;
}

2) 左移(<<)、右移(>>)

左移

左移1位,所有位都左移，末尾补0

右移

右移1位,所有位都右移，首尾补0

示例代码

//左移 <<  右移 >>
#include<bits/stdc++.h>
using namespace std;int main(){int a=3;/*3 对应二进制 0000 0011 左移1位,所有位都左移，末尾补00000 0110此时对应二进制转十进制为6 */int b=3<<1; cout<<"b的值为:"<<b<<endl;//所以b的值为6 int c=8;/*8 对应二进制 0000 1000 右移1位,所有位都右移，首尾补00000 0100此时对应二进制转十进制为4 */int d=c>>1;cout<<"d的值为:"<<d;//所以d的值为4return 0;
}

3) 按位与 (&)

运算规则，按位与的2个位同时为1时，结果为1，否则为0

示例代码

#include<bits/stdc++.h>
using namespace std;int main(){int a=5;int b=6;/*5对应的二进制为0000 0101 6对应的二进制为0000 0110所以 5 & 60000 0101& 0000 0110-------------0000 0100转对应10进制为4 */ int c=a&b;cout<<"c的值为:"<<c; //输出c的值为4 return 0;
}

4) 按位或 (|)

运算规则，按位或的2个位其中有1个为1，结果为1，否则为0

示例代码

#include<bits/stdc++.h>
using namespace std;int main(){int a=5;int b=6;/*5对应的二进制为0000 0101 6对应的二进制为0000 0110所以 5 & 60000 0101| 0000 0110-------------0000 0111转对应111进制为7 */ int c=a|b;cout<<"c的值为:"<<c; //输出c的值为7   return 0;
}

5) lowbit

lowbit(x)是将 x 转化成二进制数之后，只保留最低位（从右往左数，第一位）的1及其后面的0，截断前面的内容，然后再转成10进制数
例如

lowbit(8)=8//8对应二进制为：1000 取最右边的1及后面3个0
lowbit(12)=4//12对应二进制位：1100 取最右边的1及后面3个0
lowbit(5)=1//5对应二进制为 101 取最右边1及其后面的0

示例代码

#include<bits/stdc++.h>
using namespace std;int g(int x){return x & -x;
}int main(){int n=1;/*1的补码0000 0001-1的原码1000 0001-1的反码1111 1110-1的补码1111 11111 & -10000 0001&1111 1111-----------0000 0001  */ cout<<"g(1)的值是: "<<g(n)<<endl;//输出1n=3;/*3的补码0000 0011-1的原码1000 0011-1的反码1111 1100-1的补码1111 11011 & -10000 0001&1111 1101-----------0000 0001  */ cout<<"g(3)的值是: "<<g(n)<<endl;//输出1 n=8;/*3的补码0000 1000-1的原码1000 1000-1的反码1111 0111-1的补码1111 10001 & -10000 1000&1111 1000-----------0000 1000  */ cout<<"g(8)的值是: "<<g(n)<<endl;//输出8 return 0;
}

6) x&=x-1

x&=x-1 去除二进制补码最后1个1

示例代码

#include<bits/stdc++.h>
using namespace std;
/*去除二进制补码最后一个1正数 9对应补码 0000 1001 8对应补码 0000 1000 x&=x-1;0000 1001 
& 0000 1000 
-------------0000 1000
结果为10进制的8负数-9原码  1000 1001反码  1111 0110补码  1111 0111x-1 -9-1=-10原码  1000 1010反码  1111 0101补码  1111 0110x&=x-1;1111 0111
& 1111 0110 
-------------1111 0110 比-9的补码 1111 0111少了末尾的1补码 1111 0110  对应反码 1111 0101 对应原码 1000 1010 对应十进制-10 
*/ 
int main(){int x=9;//去除二进制补码最后1个1 x&=x-1;cout<<x<<endl;//输出 8 x=-9;//去除二进制补码最后1个1 x&=x-1;cout<<x<<endl;//输出 -10 return 0;
}

3 思路分析

判断题

1 输入的n等于1001时，程序不会发生下标越界( F )

分析

a[1000]的下标范围为a[0] - a[999]，所以a[1000]会导致越界

2 输入的a[i]必须全为正整数，否则程序将陷入死循环( F )

分析

负数不会进入死循环，负数计算机补码表示

例如 -3

在8位二进制中

原码 1000 0011

反码 1111 1100

补码 1111 1101

对应32位补码是

11111111111111111111111111111101

是31个1

3 当输入为“5 2 11 9 16 10” 时，输出“3 4 3 17 5” ( F )

分析

根据函数作用逐一输入上面5个数计算

输入数据后逐个计算，输出为3 4 3 17 4

f(2)+g(2)=1+2=3

f(2)+g(2)=3+1=4

f(2)+g(2)=2+1=3

f(2)+g(2)=1+16=17

f(2)+g(2)=2+2=4

4 当输入为“1 511998 ”时，输出为"18" （ T ）

分析

511998 对应二进制 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0

f(2)+g(2)=16+2=18

5 将原码中g函数的定义(14 -16行) 移到main函数的后面，程序可以正常编译运行( F )

分析

main函数调用的函数必须在main函数前面定义，否则编译会出错

单选题

6 当输入为"2 -65536 2147483647"时，输出为 ( B )

A. “65532 33”

B. “65552 32”

C. “65535 34”

D. “65554 33”

分析

-65536

原码

00000000000000010000000000000000

反码

11111111111111101111111111111111

补码

11111111111111110000000000000000

所以f(-65536)+g(-65536)=16+65536=65552

2147483647 是2^32-1,31个1，最高位是符号位

正数的原码，反码，补码都相同

01111111111111111111111111111111

f(2147483647)+g(2147483647)=31 + 1=32