算法学习专栏——进制转换类型题目
位运算
按位与（&）
计算方式：
有0出0，全1出1
例如：
4&5改为二进制
4 –> 0000 0100
5 –> 0000 0101
0000 0100 <–4
因此4&5=4
按位或（|）
计算方式：
有1出1，全0出0
例如：
4&5改为二进制
4 –> 0000 0100
5 –> 0000 0101
0000 0101 <–5
因此4|5=5
按位异或（^）
计算方式:
相同为0，不同为1
例如：
4&5改为二进制
4 –> 0000 0100
5 –> 0000 0101
0000 0001 <–1
因此4^5=1
用途：交换变量
1 | |
取反（~）
计算方式:
二进制中的1变0，0变1
位运算符（>> 和 <<）
计算方式：
将一个数的二进制位全部左移（右移）若干位
左移：高位溢出不用，低位补0
右移：低位溢出不用，高位正数补0，负数补1
左移一位相当于乘2，2^n^相当于左移n位，右移同理
例子：
a = 10 = （1010）2
a = a << 2 =（1000）2
一、数的进制转换（—）（简单-）
大家好，我是小刘，现在我正在学习计算机的基础知识：进制转换，但是现在有个问题，我发现学校交给我们进制转换仅仅是2、8、10、16进制之间的转换，现在我想设计一段代码，可以实现任何进制数对任何进制数之间的转换。
注意：字母这里可能为大小写字母，不需要考虑大小写问题，比如Ab23。
输入格式
输入一个字符串 X，X的进制为Y，需要转化为的进制为Z。
输出格式
输出转换为Z进制的数X的格式。
数据范围
$$
1 <= X.length() <= 5\
2<=Y<=36\
2<=Z<=36
$$
输入样例1：
1 | |
输出样例1：
1 | |
输入样例2：
1 | |
输出样例2：
1 | |
思路
思路
可以选择先将这个数转换为10进制，再将其转换为对应进制，这个思路是最常见最简单的一套思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < algorithm>
#include < vector>
using namespace std;
string x;
int y,z;
int k = 1;
long long ans;
vector C;
int main()
{
cin >> x >> y >> z;
for (int i = x.size() - 1; i >= 0; i--)
{
if (x[i] >= 'A' && x[i] <= 'Z') ans += (x[i] - 'A' + 10) * k;
if (x[i] >= 'a' && x[i] <= 'z') ans += (x[i] - 'a' + 10) * k;
else ans += (x[i] - '0') * k;
k *= y;
}
// 下面这种写法也可以
//for (int i = x.size() - 1; i >= 0; i--)
//{
// x[i] = tolower(x[i]); // 这个函数的作用是将字母转换为小写字母，比如'A'变为'a',
// if (x[i] >= 'a' && x[i] <= 'z') ans += (x[i] - 'a' + 10) * k;
// else ans += (x[i] - '0') * k;
// k *= y;
//}
while (ans){
C.push_back(ans % z);
ans /= z;
}
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
return 0;
}
二、数的进制转换（二）（简单）
编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。
这里有 62 个不同数位 **{0−9,A−Z,a−z}{0−9}**。
输入格式
第一行输入一个整数，代表接下来的行数。
接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。
输入进制和输出进制都在 22 到 6262 的范围之内。
（在十进制下）A=10，B=11，…，Z=35，a=36，b=37，…，z=61 (0−9 仍然表示 0−9)。
输出格式
对于每一组进制转换，程序的输出都由三行构成。
第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。
第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。
第三行为空白行。
同一行内数字用空格隔开。
输入样例：
1 | |
输出样例：
1 | |
思路
和上一道题目思路几乎一致
代码
答案（请自己先思考一下再参考）
#include
#include < algorithm>
#include < cstring>
using namespace std;
const int Max = 1100;
#define fir(a,b,c) for (int a = b;a <= c;a++)
int t[Max],A[Max],n,m,i,len,k;
char str1[Max], str2[Max];
void solve()
{
k=0;
len = strlen(str1);
for(i=len; i >= 0; i--)
t[len - i - 1] = str1[i] -(str1[i]<58 ? 48: str1[i]<97 ? 55: 61);//开始转换成为十进制
while(len)
{
//这个写法大家
for(i = len; i >= 1; i--)
{
t[i - 1] +=t[i] % m * n;//开始计算,首先*n,为n进制,然后转移到m进制
t[i] /= m;//当前数已经处理完了
}
A[k++] = t[0] % m;//直接加到答案数组中
t[0] /= m;//当前数已经处理完了
while(len > 0&& !t[len - 1]) //处理0的情况
len--;
}
str2[k] =NULL;//第k位,我们不需要,直接抛去,利用NULL这个特殊的字符串结束符,具体可以自行百度.
fir(i,0,k - 1)//这里使用这个写法就是让大家熟悉一下，之后使用这个方法可以简化代码
str2[k - 1 - i] = A[i]+(A[i] < 10 ? 48: A[i] < 36 ? 55:61);//三目运算符,这段代码的意思是,
// 找这个数字对应的字母
}
int main()
{
int t;
scanf("%d\n",&t);
while(t--)
{
scanf("%d %d %s\n",&n,&m,str1);
solve();
printf("%d %s\n%d %s\n\n",n,str1,m,str2);
}
return 0;
}
三、数列（简单）
给定一个正整数 k，把所有 k 的方幂及所有有限个互不相等的 k 的方幂之和构成一个递增的序列，例如，当 k=3 时，这个序列是：
1，3，4，9，10，12，13，…
该序列实际上就是：3^0^，3^1^，3^0^+3^1^，3^2^，3^0^+3^2^，3^1^+3^2^，3^0^+3^1^+3^2^……
请你求出这个序列的第 N 项的值（N 用 10 进制数表示，从 1 开始）。
例如，对于 k=3，N=100正确答案应该是 981。
输入格式
输入文件只有 11 行，为 22 个正整数，用一个空格隔开：k,N,。
输出格式
输出文件为计算结果，是一个正整数（在所有的测试数据中，结果均不超过 2.1×1092.1×109）。（整数前不要有空格和其他符号）。
数据范围
$$
3≤k≤15\
10≤N≤1000
$$
输入样例：
1 | |
输出样例：
1 | |
思路
思路
这道题目实质上就是一个扩展思维类型题目，大家可以仔细观察一下题目给出的一串数列，然后再结合二进制来看一下就不难看出就是一个从1~n的二进制数的排列罢了，比如说：对于数字9而言对应二进制位1001,那么我们对应数列的项就是3^0 + 3^3。
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cmath>
using namespace std;
typedef long long LL;
int k, n;
LL ans;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> k >> n;
for (int i = 0; i < 15;i ++) {
if ((n >> i) & 1) {
ans += pow(k, i);
}
}
cout << ans;
return 0;
}