【笔记】进制与位运算
ccr39
·
·
个人记录
一、进制
（1）概念
几进制指的是几进一，日常生活中常常使用十进制，在计算机语言中，2进制最常见。
同时，还有8进制，16进制等进制。
（2）进制的表示：
①二进制：用前缀0b表示；或用后缀B表示，如：01101001B。
②八进制：用前缀0o表示，如0o76；或用后缀O表示，如：257O。
③十进制：用前缀0d表示,或用后缀D表示。
④十六进制：用前缀0x表示,或用后缀D表示。
在表示9以上的数时使用用A、B、C、D、E、F。
（3）进制的转换
①n进制转10进制
思路：将第a位数字乘以n^{a-1},再作和。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int n,b;
string a;
int main()
{
cin>>n>>a;
int l=a.size();
for(int i=1;i<=l;i++)
{
if (a[l-i]>='0'&&a[l-i-1]<='9')
a[l-i]-='0';
if ( a[l-i]>='A' && a[l-i]<='F' )
{
a[l-i]-='A';
a[l-i]+=10;
}
b+=a[l-i]*pow(n,i-1);
}
cout<<b;
return 0;
}
也可以用函数实现，用到函数strtol()。
用法strtol(字符串(char[]型),NULL，n）
代码
#include<bits/stdc++.h>
using namespace std;
int n;
char a[1000];
int main()
{
cin>>n>>a;
cout<<strtol(a,NULL,n);
return 0;
}
②10进制转n进制
思路：模n取余法，将十进制数向n取余，记录余数，知道十进制数为零，反向书写余数，即为n进制数。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int n,b,i,ans[10000];
int main()
{
cin>>n>>b;
while(b>0)
{
ans[i++]=b%n;
b/=n;
}
for ( int q=i-1 ; q>=0 ; q-- )
if(ans[q]>=10&&ans[q]<16 )
cout<<char(ans[q]+55);
else cout<<ans[q];
return 0;
}
③二进制转十六进制。
思路：一个有趣的性质
1位十六进制数码对应 4 位数的二进制数码。
所以将十六进制和二进制之间相互转换时并不需要以 10 进制为中间跳板，直接进行翻译即可。
例如二进制数 1010110111 经过分组可以变为 0010 1011 0111，直接查表（或者口算）可以翻译为 2B7。
反过来也是一样的。
④n进制转m进制
思路:先将n进制转10进制，再将10进制转m进制。
代码:
#include<bits/stdc++.h>
using namespace std;
string a;
int c[10000000],d,e,f,g,sum,ans;
int main()
{
scanf("%d",&d);
cin>>a;
scanf("%d",&f);
for(int x=0;x<a.size();x++){
if(a[x]<'A'){
e=pow(d,a.size()-x-1);
e*=(a[x]-'0');
sum+=e;
}
else{
e=pow(d,a.size()-1-x);
e*=(a[x]-'A'+10);
sum+=e;
}
}
while(sum>0){
c[g++]=sum%f;
sum/=f;
}
for(int x=g-1;x>=0;x--){
if(c[x]>=10)printf("%c",c[x]+'A'-10);
else printf("%d",c[x]);
}
return 0;
}
⑤浮点数的进制转换
思路：先转换整形,再将浮点数部分乘n取整。
（4）二进制的深入探究
在二进制中一个 0 或 1 的数码被称为一位。一个内存地址对应的 8 位，被称为一字节，也就是 1 Byte。
一个 int 类型或 float 类型的变量占用 32 位空间。
而一个 char 的变量占用 8 位。
有些变量类型也有无符号数，例如 unsigned int 类型。
这个类型占用和 int 类型一样，为 32 位，但是以放弃存储正负符号为代价，可以储存比 int 多一倍的整数值（0 到2^{32}−1，接近4.3×10^9 ）。
计算机中还有其他的表示数据大小的单位，比如 1 KB 是2^10=1024 字节（大约一千），1 MB 是 2^{20} 字节（大约一百万）， 1 GB 是 2^{30} 字节。
在带符号整数的情况下，-57 如何被表示成负数呢？在计算机中又是如何计算 66-57 呢?
我们用 8 位的 signed char 类型来举例
57 用二进制表示为 0011 1001（补足 8 位）。
如何表示一个负数？
可以占用最高位的一位来表示正负，0 表示非负，1 表示负数。
然后再经过一下方法处理
①用除了第一位的数字表示这个负数的绝对值，第一位变成 1。这样的话 -57 表示为 1011 1001。
这种表示方式称为原码。不过计算机不使用这种方式来表示负数。
②将这个负数的绝对值的数全部取反，由 1 变为 0，0 变为 1。这样的话 -57 表示为 1100 0110。这种表示方式成为反码。
使用反码有一个问题，对于0，既可以表示为0000 0000也可以表示为1111 1111，所以也不常用。
③先计算这个负数的反码，然后加 1。这样的话 -57 表示为 1100 0111。这是计算机使用的表示负数的方法，被称为补码。这种表达方式下，零只有 1 个，而1111 1111则代表 -1。
二、位运算
（1）定义
直接对整数在内存中的二进制位进行按位操作。
（2）运算符
位运算包括与、或、非、异或等操作。
①与运算:A∧B（在C语言写作"A\&B"）A与B全为真时，得数为真。（即： 1\&1=1 ; 1\&0=0 ; 0\&0=0）
②或运算:A∨B(在C语言写作"A|B"）A或B中有一个为真是，得数为真。（即：1|1=1 ; 1|0=1 ; 0|0=0）
③非运算：￢A(在C语言写作"~A"）进行取反操作。（即：~1=0 ; ~0=1）
④异或运算：A⊕B（在C语言写作"A^B"）只有当两个值一假一真时，得数为真，等效于 " ( A \& ~ B ) | ( ~ A \& B ) "
（即：除1^0得数位1外，得数均为零）
性质1：任何数与 0 异或即为本身。
性质2：任何偶数个相同的数异或后结果为 0。
性质3：任何数异或偶数次另一个数结果不变。
⑤左移：A<<B将A的二进制向左移B位，空位用 0 补齐。
⑥右移：A>>B将A的二进制向右移B位，非正数位删去。