[编程题]10进制 VS 2进制
- 热度指数：21505 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们称B为A的二进制逆序数。 例如对于十进制数173，它的二进制形式为10101101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数。
输入描述:
一个1000位(即10^999)以内的十进制数。
输出描述:
输入的十进制数的二进制逆序数。
示例1
输入
173
输出
181
编写一个进制转换函数，由转换过程可知，保存大数求模的数组已经是逆序的，只要删除数组开头连续的0，再用进制转换函数转换为10进制即可。代码如下：
#include<iostream>
#include<string>
#define N 4000
using namespace std;
int conversion(int d[],int data[],int n,int x,int y){
int size=0;
for(int i=0;i<n;){
int k=0;
for(int j=i;j<n;j++){
int t=(d[j]+k*x)%y;
d[j]=(d[j]+k*x)/y;
k=t;
}
data[size++]=k;
while(d[i]==0) i++;
}
return size;
}
int main(){
string s;
int d[N],data[N];
while(cin>>s){
for(int i=0;i<s.length();i++)
d[i]=s[i]-'0';
int n=conversion(d,data,s.length(),10,2);
int start;
for(start=0;data[start]==0;start++);
for(int i=start;i<n;i++)
data[i-start]=data[i];
n=conversion(data,d,n-start,2,10);
for(int i=n-1;i>=0;i--)
cout<<d[i];
cout<<endl;
}
return 0;
}
发表于 2018-01-17 23:07:49
回复(5)
// 参考 CSDN Blog : http://blog.csdn.net/sjf0115/article/details/8690581
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 4000; // 因为输入的10进制不超过1000位，则转换成2进制应该不超过4000位（2^4 = 16）
const int oldBase = 10; // 原始进制
const int newBase = 2; // 新进制
string str; // 因为输入为不超过1000位的10进制数则应该用字符串接收
/**
数组的 0 号元素均用于存储数组的长度
*/
int br[maxn] = {0}; // 存储2进制
int dr[maxn] = {0}; // 存储10进制
int drans[maxn] = {0}; // 存储10进制转2进制的过程中的商，并且存储将 2 进制转换到 10 进制的过程中 的2^n
int drres[maxn] = {0}; // 存储10进制转2进制的过程中的余数
// 将 字符串 str 存到 dr int数组中， dr[0] 记录10进制数组长度
void change()
{
memset(dr, 0, sizeof(dr));
dr[0] = 0; // 使用 dr[0] 存储数组长度
for(int i = 1; i <= str.length(); ++i)
{
dr[++dr[0]] = str[i-1]-'0';
}
}
// 将 10 进制转换成 2 进制
void solve()
{
memset(drres, 0, sizeof(drres));
int y, i, j, k;
// 模 n 取余法，（总体规律是先余为低位，后余为高位）
while(dr[0] >= 1)
{
// 只要被除数仍然 >= 1，则继续操作
y = 0;
i = 1;
drans[0] = dr[0]; // 商的长度与被除数相同（包含前导0）
while(i <= dr[0])
{
y = y * oldBase + dr[i];
drans[i++] = y / newBase;
y %= newBase;
}
drres[++drres[0]] = y; // 本轮计算得到的余数
i = 1;
// 找到下一轮商的起始位置
while((i<=drans[0]) && (drans[i] == 0)) ++i;
// 清除这一轮使用的被除数
memset(dr, 0, sizeof(dr));
// 本轮得到的商为下一轮的被除数
for(j = i; j <= drans[0]; ++j)
{
dr[++dr[0]] = drans[j];
}
// 清除本轮的商
memset(drans, 0, sizeof(drans));
}
/**
现在 drres 存储的是 str 的 2 进制的倒序，即题目中要求的二进制序列
下面将 drres 中存储的 2 进制（1~drres[0]），转换成 10 进制并存储到 dr 中
*/
memset(drans, 0, sizeof(drans));
memset(dr,0,sizeof(dr));
drans[0] = 1;
drans[1] = 1; // 2^0 = 1;
for(i = drres[0]; i >= 1; --i)
{
// 先 + ，后计算 2 ^ n
if(drres[i] == 1)
{
// dr[0] 取 dr[0] 原以及 drans[0] 取两者较大者，为了保持数据位数
dr[0] = dr[0] > drans[0] ? dr[0] : drans[0];
// 此为为 1 才加
for(k = 1; k <= drans[0]; ++k)
{
dr[k] += drans[k];
}
// 移位
for(j = 1; j <= dr[0]; ++j)
{
if(dr[j] > 9)
{
dr[j+1] += dr[j] / oldBase;
dr[j] %= oldBase;
// 最高位进位的情况
if(dr[0] == j)
{
++dr[0];
}
}
}
}
// 计算 2 ^ n
for(j = 1; j <= drans[0]; ++j)
{
drans[j] *= newBase;
}
// 移位
for(j = 1; j <= drans[0]; ++j)
{
if(drans[j] > 9)
{
drans[j+1] += drans[j] / oldBase;
drans[j] %= oldBase;
// 最高位进位的情况
if(drans[0] == j)
{
++drans[0];
}
}
}
}
}
void output()
{
for(int i = dr[0]; i > 0; --i)
{
cout << dr[i];
}
}
int main()
{
while(cin >> str)
{
change(); // 将10进制数据存储到数组中
solve(); // 将 10 进制转换成 2 进制，并将其 2 进制倒序所表示的 10 进制存储到原数组中
output(); // 输出
cout << endl;
}
return 0;
}
发表于 2016-08-04 22:56:17
回复(0)
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
string Divide(string str, int x){
int remainder=0;
for(int i=0;i<str.size();++i){
int current=remainder*10+str[i]-'0';
str[i]=current/x+'0';
remainder=current%x;
}
int pos=0;
while(str[pos]=='0'){
pos++;
}
return str.substr(pos);
}
string Multiple(string str,int x){
int carry=0;
for(int i=str.size()-1;i>=0;--i){
int current=x*(str[i]-'0')+carry;
str[i]=current%10+'0';
carry=current/10;
}
if(carry!=0){
str="1"+str;
}
return str;
}
string Add(string str,int x){
int carry=x;
for(int i=str.size()-1;i>=0;--i){
int current=(str[i]-'0')+carry;
str[i]=current%10+'0';
carry=current/10;
}
if(carry!=0){
str="1"+str;
}
return str;
}
int main(){
string str;
while(cin>>str){
vector<int>binary;
while(str.size()!=0){
int last=str[str.size()-1]-'0';
binary.push_back(last%2);
str=Divide(str,2);
}
string answer="0";
for(int i=0;i<binary.size();++i){
answer=Multiple(answer,2);
answer=Add(answer,binary[i]);
}
cout<<answer<<endl;
}
return 0;
}
发表于 2021-03-27 10:45:52
回复(0)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> myVector;
string divide(string str, int x)
{
int mode = 0;
for (int i = 0; i < str.size(); i++)
{
int current = mode * 10 + str[i] - '0';
str[i] = current / x + '0';
mode = current % x;
}
int pos = 0;
while (str[pos] == '0')
{
pos++;
}
return str.substr(pos);
}
string multiply(string str, int x)
{
int mode = 0; //进位
for (int i = str.size() - 1; i >= 0; i--)
{
int current = x * (str[i] - '0') + mode;
str[i] = current % 10 + '0';
mode = current / 10;
}
if (mode != 0)
{
str.insert(0, 1, (mode + '0'));
}
return str;
}
string add(string str, int a)
{
int mode = a;
for (int i = str.size() - 1; i >= 0; i--)
{
int current = (str[i] - '0') + mode;
str[i] = current % 10 + '0';
mode = current / 10;
}
if (mode != 0)
{
str.insert(0, 1, (mode + '0'));
}
return str;
}
int main()
{
string str, res;
while (cin >> str)
{
while (str.size())
{
int last = str[str.size() - 1] - '0';
myVector.push_back(last % 2);
str = divide(str, 2);
}
res = "0";
for (int i = 0; i < myVector.size(); i++)
{
res = multiply(res, 2);
res = add(res, myVector[i]);
}
cout << res << endl;
myVector.clear();
}
return EXIT_SUCCESS;
}
发表于 2021-02-18 15:28:41
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Ten {
public static void main(String[] args) {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String str;
StringBuffer sb = new StringBuffer();
try {
while ((str = bufferedReader.readLine())!=null){
String s = sb.append(new BigInteger(str).toString(2)).reverse().toString();
BigInteger bigInteger = new BigInteger(s, 2);
System.out.println(bigInteger);
sb.replace(0,sb.length(),"");
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
发表于 2017-11-16 13:52:29
回复(0)
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
void Division(int *num,int n)
{
int temp = 0;
for(int i = 0;i < n;i++)
{
temp = temp * 10 + num[i];
num[i] = temp / 2;
temp = temp % 2;
}
}
void Multiplication(int *mul,int n)
{
for(int i = 0;i < n;i++)
{
int temp = 0;
for(int j = 999;j >= 0;j--)
{
int m = mul[j] * 2 + temp;
mul[j] = m % 10;
temp = m / 10;
}
}
}
void Addition(int *sum,int *mul)
{
int temp = 0;
for(int i = 999;i >= 0;i--)
{
int s = sum[i] + mul[i] + temp;
sum[i] = s % 10;
temp = s / 10;
}
}
bool IsAllZero(int *num,int n)
{
for(int i = 0;i < n;i++)
{
if(num[i]) return false;
}
return true;
}
int main()
{
string str;
while(cin >> str)
{
stack<int> st;
int num[str.size()];
for(int i = 0;i < str.size();i++)
{
num[i] = str[i] - '0';
}
if(str == "0") st.push(0);
while(!IsAllZero(num, str.size()))
{
st.push(num[str.size() - 1] % 2);
Division(num,str.size());
}
int count = 0,record = 0;
int mul[1000],sum[1000];
memset(mul,0,1000 * sizeof(int));
memset(sum,0,1000 * sizeof(int));
mul[999] = 1;
while(!st.empty())
{
if(st.top())
{
Multiplication(mul,count - record);
Addition(sum,mul);
record = count;
}
st.pop();
count++;
}
int i = 0;
while(!sum[i]) i++;
for(i = i;i < 1000;i++)
cout << sum[i];
}
return 0;
}
发表于 2021-01-22 17:23:47
回复(0)
/*
*
*仍然是利用模n取余逆序的定理，只不过这里深入的利用了每次取余时的除法的处理过程，
*从而使得按照顺序进行对大整数的进制转换成为可能。
*这里为了增强代码的通用性，增加的数字字符转换函数，使得代码适用于任意进制的转换。
*/
#include<bits/stdc++.h>
using namespace std;
int CToN(char c) //字符转换为数字
{
return isalpha(c) ? c-'A'+10 : c-'0';
}
char NToC(int n) //数字转换为字符
{
return n >= 10 ? n-10+'A' : n+'0';
}
string changeMtoN(string a, int from, int to) //将m进制的数转换为n进制
{
int len = a.length(); string b = ""; //存储转换后的进制
for(int i = 0;i < len;)
{
int h = 0;
for(int j = i;j < len; j++)
{
int t = (h*from + CToN(a[j])) % to;
a[j] = NToC((h*from + CToN(a[j])) / to);
h = t;
}
b = NToC(h) + b;
while(a[i] == '0') i++;
}
return b;
}
int main()
{
ios::sync_with_stdio(false);
string a, b; int from = 10, to = 2;
while(cin >> a)
{
b = changeMtoN(a, from, to);
reverse(b.begin(), b.end());
a = changeMtoN(b, to, from);
cout << a << '\n';
}
return 0;
}
发表于 2021-01-21 00:03:08
回复(0)
#include <iostream>
#include <string>
using namespace std;
pair<string, string> strDiv_2(string &a) //字符串除2，返回<商,余数>
{
pair<string, string> out;
int yw = 0; //余数
bool flag = false;
for (int i = 0; i < a.length() ; i++)
{
int aw = a[i] - '0'; //a的第i个数字
int bcw = yw * 10 + aw; //被除数=余数*10+a的第i个数字
int sw = bcw / 2;//商
yw = bcw % 2;//余数
if (sw != 0)
flag = true; //前面的0直接忽略，直到第一个不是0的数字开始记录，如果在后面删除0会超时
if (flag == true)
out.first += char(sw + '0');
}
out.second = char(yw + '0');
return out;
}
string DtoB(string D) //十进制转二进制,返回逆序
{
string B;
pair<string, string> out;
while (1)
{
out = strDiv_2(D);
D = out.first;
B = B + out.second;
if (D == "1" || D == "0" || D == "") //D可能为空，输入是0的情况时，但是测试中没有该情况
break;
}
B = B + D;
return B;
}
pair<string, string> strDiv_10(string& a) //字符串除10，返回<商,余数>
{
pair<string, string> out;
int yw = 0; //余数
bool flag = false;
for (int i = 0; i < a.length(); i++)
{
int aw = a[i] - '0'; //a的第i个数字
int bcw = yw * 2 + aw; //被除数=余数*2+a的第i个数字
int sw = bcw / 10;//商
yw = bcw % 10;//余数
if (sw != 0)
flag = true;
if (flag == true)
out.first += char(sw + '0');
}
out.second = char(yw + '0');
return out;
}
string BtoD(string B) //二进制转十进制
{
string D;
pair<string, string> out;
while (1)
{
out = strDiv_10(B);
B = out.first;
D = out.second + D;
if (B.length() <= 1) //B可能返回""，<=很关键
break;
}
D = B + D;
return D;
}
int main()
{
string input;
while (cin >> input)
{
cout << BtoD(DtoB(input)) << endl;
}
} 需要知道一个知识点才行，按照平时二进制转十进制的思路（2的N次方相加）会超时。
【知识点】：二进制除以十取余逆序就是十进制数（和十进制转二进制的操作一致）
大佬写的很简单，我写的啰嗦了，我还是第一次用这个方法求二进制转十进制，直到把原理相通才明白。
编辑于 2020-04-12 13:18:00
回复(0)
Java
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 一个1000位(即10^999)以内的十进制数。
BigInteger i = scanner.nextBigInteger();
String s = i.toString(2);
String reverse = new StringBuilder(s).reverse().toString();
System.out.println(new BigInteger(reverse,2));
}
}
发表于 2020-03-18 17:55:30
回复(0)
#include<iostream>//大整数除法m转n进制
(1365)#include<vector>
#include<string>
using namespace std;
int main()
{
string str;
int a[4000] = { 0 };
int b[4000] = { 0 };
while (cin >> str)
{
int n = str.length();
for (int i = 0; i < n; i++)
a[i] = str[i] - '0';
int idx = 0, temp = 0, flag = 1;
while (flag)
{
for (int i = 0; i < n; i++)
{
a[i] = temp * 10 + a[i];
temp = a[i] % 2;
a[i] /= 2;
}
b[idx++] = temp;
temp = 0;
flag = 0;
for (int i = 0; i < n; i++)
if (a[i] != 0)
flag = 1;
}//此时b[]数组存储了原数的2进制的逆序
flag = 1;
int t = 0;
while (flag)//再把b转化成10 进制保存到a中去
{
for (int i = 0; i < idx; i++)
{
b[i] = temp * 2 + b[i];
temp = b[i] % 10;
b[i] /= 10;
}
a[t++] = temp;
temp = 0;
flag = 0;
for (int i = 0; i < idx; i++)
if (b[i] != 0)
flag = 1;
}
for (int i = t - 1; i >= 0; i--)//注意逆序遍历
cout << a[i];
}
return 0;
} //下面这个为带函数的，模块化，有些函数稍微改动下可以作为大整数的任意进制间的互相转化
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void getint(string& s,int n, int* a)//string类大整数转整型数据每一位用一个数组单元保存
{
for (int i = 0; i < n; i++)
a[i] = s[i] - '0';
}
int transf1(int* a, int* b, int n)//10-2的模板
{
int idx = 0, temp = 0, flag = 1;
while (flag)
{
for (int i = 0; i < n; i++)
{
a[i] = temp * 10 + a[i];
temp = a[i] % 2;
a[i] /= 2;
}
b[idx++] = temp;
temp = 0;
flag = 0;
for (int i = 0; i < n; i++)
if (a[i] != 0)
flag = 1;
}
return idx;//返回了idx为下一个2-10的n
}
int transf2(int* a, int* b, int n)
{
int idx = 0, temp = 0, flag = 1;
while (flag)
{
for (int i = 0; i < n; i++)
{
a[i] = temp * 2 + a[i];
temp = a[i] % 10;
a[i] /= 10;
}
b[idx++] = temp;
temp = 0;
flag = 0;
for (int i = 0; i < n; i++)
if (a[i] != 0)
flag = 1;
}
return idx;//最后遍历的范围
}
int main()
{
string str;
int a[4000] = {0};
int b[4000] = { 0 };
while (cin >>str)
{
int n = str.length();
getint(str,n, a);
int z=transf1(a, b, n);
int t=transf2(b, a, z);
for(int i=t-1; i >= 0; i--)
cout << a[i];
}
return 0;
}
编辑于 2020-03-04 20:07:43
回复(0)
/*
因为数字偏大，考虑用字符串进行乘除和加运算，先转换成2进制，然后再变成10进制就行，只不过是在字符串上操作
*/
#include <bits/stdc++.h>
using namespace std;
string div(string str,int x){
int carry = 0;
for(int i=0;i<str.size();i++){
int cur = str[i]-'0'+carry*10;
str[i] = cur/x + '0';
carry = cur%x;
}
int pos = 0;
while(str[pos]=='0') pos++;
return str.substr(pos);
}
string mul(string str,int x){
int carry = 0;
for(int i=str.size()-1;i>=0;i--){
int cur = (str[i]-'0')*x+carry;
str[i] = cur%10+'0';
carry = cur/10;
}
while(carry!=0){
int d = carry%10;
str = char(d+'0')+str;
carry/=10;
}
return str;
}
string add(string str,int x){
int carry = x;
for(int i=str.size()-1;i>=0;i--){
int cur = (str[i]-'0')+carry;
str[i] = cur%10+'0';
carry = cur/10;
}
while(carry!=0){
int d = carry%10;
str = char(d+'0')+str;
carry/=10;
}
return str;
}
int main(){
string str;
while(cin>>str){
vector<int> res;
while(str.size()!=0){
int last = str[str.size()-1]-'0';
res.push_back(last%2);
str = div(str,2);
}
string answer = "0";
for(int i=0;i<res.size();i++){
answer = mul(answer,2);
answer = add(answer,res[i]);
}
cout<<answer<<endl;
}
}
发表于 2020-03-03 08:17:55
回复(0)
纯c
#include <stdio.h>
#include <stdlib.h>
void sum(int a[], int b[], int n) // a = a + b
{
int c = 0;
for (int i = n - 1; i >= 0; i--)
{
int temp = a[i] + b[i] + c;
a[i] = temp % 10;
c = temp / 10;
}
return;
}
int re(int a[], int n) // a = a / 2, 返回余数re
{
int r = 0;
for (int i = 0; i < n; i++)
{
int temp = r * 10 + a[i];
a[i] = temp / 2;
r = temp % 2;
}
return r;
}
void doub(int a[], int n) // a = a * 2
{
int c = 0;
for (int i = n - 1; i >= 0; i--)
{
int temp = 2 * a[i] + c;
a[i] = temp % 10;
c = temp / 10;
}
return;
}
int is(int a[], int n) // 判断a是否等于0, 等于0返回0, 不等于0返回1
{
for (int i = n - 1; i >= 0; i--)
{
if (a[i] != 0)
{
return 1;
}
}
return 0;
}
void reverse_binary(int a[], int b[], int n) // 将a转换成二进制倒序后再转换成十进制b
{
int *s = (int*)malloc(sizeof(int) * 4 * n); // 用于存放转换后的二进制数
int top = -1;
while (is(a, n) == 1) // 将a整除2直至a等于0
{
s[++top] = re(a, n); // 余数入栈s
}
int *e2 = (int*)malloc(sizeof(int)*(n + 1)); // 用于存放2的n次方
for (int i = 0; i < n + 1; i++) // 将b和e2初始化为0
{
b[i] = 0;
e2[i] = 0;
}
for (int i = top; i >= 0; i--) // b = binary[1]*2的0次方 + binary[2]*2的1次方 + binary[3]*2的2次方 +...
{
if (i == top)
{
e2[n] = 1; // 第一次循环，e2 = 2的0次方
}
else
{
doub(e2, n + 1); // 接下来的每一次循环，e2都乘以2，即e2 = 2的k-1次方，其中k为当前循环次数
}
if (s[i] == 1)
{
sum(b, e2, n + 1); // binary[k]等于1时，b = b + 2的k-1次方，binary[k]等于0就没必要进行这一步
}
}
}
int main()
{
char str[1000];
while (scanf("%s", str) != EOF)
{
int n = 0;
while (str[n] != '\0')
{
n++;
}
int *a = (int*)malloc(sizeof(int)*n);
for (int i = 0; i < n; i++)
{
a[i] = str[i] - '0';
}
int *b = (int*)malloc(sizeof(int)*(n + 1));
reverse_binary(a, b, n);
int first;
for (first = 0; first < n && b[first] == 0; first++);
for (int i = first; i < n + 1; i++)
{
printf("%d", b[i]);
}
printf("\n");
}
return 0;
}
编辑于 2020-02-25 21:33:33
回复(0)
#include<bits/stdc++.h>
void convert(int x,int y,char a[4001],char b[4001]){//任意x进制数a[i]转换为y进制数b[j]
int j;
for(j=0;strlen(a)!=0;j++){
int yu=0,mark=0,temp,offset=0;//yu为临时余数，mark=0说明忽略除数中为零的最高位，offset为除数数组下标
for(int i=0;i<strlen(a);i++){
if(a[i]>='0'&&a[i]<='9')
temp=a[i]-'0'+yu*x;//判断是否十进制以内数
else if(a[i]>='a'&& a[i]<='z')
temp=a[i]-'a'+10+yu*x;//判断是否超过十进制
if(temp/y!=0) mark=1;
if(mark==1)
if(temp/y<10) a[offset++]=temp/y+'0';
else a[offset++]=temp/y-10+'a';//恢复对应的字符值
yu=temp%y;
}
if(yu<10) b[j]=yu+'0';
else b[j]=yu-10+'a';//确保十进制以上的数正确存储
a[offset]='\0';
}
b[j]='\0';
}//转换结果倒序存放
int main(){
char a[4001],b[4001];
while(gets(a)){
convert(10,2,a,b);//十进制数转换为二进制逆序
convert(2,10,b,a);//二进制逆序再转换为十进制逆序
for(int i=strlen(a)-1;i>=0;i--)
printf("%c",a[i]);//结果倒序输出
printf("\n");
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
}
}
发表于 2019-03-16 15:24:23
回复(0)
//纯C
#include<stdio.h>
#include<string.h>int cnt,b[10000];//b[]存结果，cnt为数组b的实际长度
void transfer(int a[],int len,int from,int to)
{
int i,p,carry,temp;
p=0;
cnt=0;
while(p<len)
{
carry=0;
for(i=p;i<len;i++)
{
temp=(carry*from+a[i])%to;//进位
a[i]=(carry*from+a[i])/to;//本位
if(a[i]==0 && p==i) p=i+1;//p始终指向a[]数组中第一个不为0的数
carry=temp;
}
b[cnt++]=carry;
}
return ;
}
int main()
{
int i;
char s[1001];
int a[10000];
while(~scanf("%s",s))
{
int len=strlen(s);
for(i=0;i<len;i++) a[i]=s[i]-'0';//将字符串存在数组a[]里面
transfer(a,len,10,2);//将a[]数组从十进制转化为二进制， 结果逆序保存在b[]中
for(i=0;i<cnt;i++) a[i]=b[i];
transfer(a,cnt,2,10); //将a[]数组从二进制转化为十进制，结果逆序保存在b[]中
for(i=cnt-1;i>=0;i--) printf("%d",b[i]);
printf("\n");
}
return 0;
}
编辑于 2019-03-06 10:25:04
回复(0)
//用了两次进制转换，先10进制转2进制得到bin数组，再把bin数组转成10进制
//核心部分是两个for循环，可以将任意M进制转成N进制，理解了这个，基本所有的进制转换都问题不大了
#include <iostream>
using namespace std;
#include <vector>
#include<string>
#include<stack>
void solve(string &s) {
vector<int> org(s.size()), bin;
for (int i = 0; i<s.size(); org[i] = s[i] - '0',i++);
int M = 10, N = 2;
for (int i = 0; i<org.size(); (org[i] == 0 ? i++ : 0)) {
int carry = 0;
for (int j = i; j<org.size(); j++) {
org[j] = (org[j] + carry*M);
carry = org[j] % N;
org[j] /= N;
}
bin.push_back(carry);
}
stack<char> res;
M = 2, N = 10;
for (int i = 0; i<bin.size(); (bin[i] == 0 ? i++ : 0)) {
int carry = 0;
for (int j = i; j<bin.size(); j++) {
bin[j] = (bin[j] + carry*M);
carry = bin[j] % N;
bin[j] /= N;
}
res.push(carry + '0');
}
while (res.top() == '0')
{
res.pop();
}
while (res.size() > 0)
{
cout << res.top();
res.pop();
}
cout << endl;
}
int main() {
string s;
while (cin >> s) {
solve(s);
}
}
发表于 2017-07-10 16:35:08
回复(1)
#include <stdio.h>
#include <string.h>
#define MAX 0xffffffff
struct big_int{
unsigned int digit[112];
int size;
};
char str[1000];
int main(){
struct big_int A,B;
unsigned long long tmp,carry;
unsigned int tag,flag;
int i,j;
while(gets(str)){
for(memset(&A, 0, 113*4),memset(&B, 0, 113*4),carry = 0, tmp = 0,i = 0; i <= strlen(str)-1;i++){
for(carry = str[i]-'0',j = 0; j <= A.size;j++){
tmp = A.digit[j]+carry;
carry = (tmp>>32)&MAX;
A.digit[j] = tmp&MAX;
if(!carry)break;
}
if(carry)A.digit[++A.size]=carry;
if(i == strlen(str)-1)break;
for(carry = 0,j = 0; j <= A.size; A.digit[j++] = tmp&MAX){
tmp = A.digit[j]*(long long)10+carry;
carry = (tmp>>32)&MAX;
}
if(carry)A.digit[++A.size]=carry;
} //二进制存储
for(flag=0,i = 0; i <= A.size;i++,flag=0){
if(i==A.size)for(flag = tag = 0x80000000;tag;flag = (tag>>=1))if(A.digit[A.size]&tag)break;
for(tag = 0x00000001;tag!=(flag<<1);tag<<=1){
if(A.digit[i]&tag){
for(carry = 1,j = 0; j <= B.size;j++){
tmp = (B.digit[j]+carry)%1000000000;
carry = (B.digit[j]+carry)/1000000000;
B.digit[j] = tmp&0xffffffff;
if(!carry)break;
}
if(carry)B.digit[++B.size]=carry;
}
if(i == A.size && tag == flag)break;
for(carry = 0,j = 0; j <= B.size; B.digit[j++] = tmp&0xffffffff){
tmp = (B.digit[j]*2+carry)%1000000000;
carry = (B.digit[j]*2+carry)/1000000000;
}
if(carry)B.digit[++B.size]=carry;
}
} //转换成10进制方便输出
for(printf("%d",B.digit[B.size]),i = B.size-1;i>=0;printf("%09d",B.digit[i--]));
printf("\n");
}
return 0;
}
编辑于 2017-03-13 21:25:24
回复(0)
思想：用字符串存储输入数据，为了得到其二进制结果，每次将每一位除以二（从高位至低位），由于二进制数可能非常大，故不能用整型保存二进制，需要两个数组，一个保存2的高次幂，一个保存最终结果；
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
void change(int a[]){ //将数组调整成每个位只有个位数，即按照个、十、百、千...
int f=0; //标志位，用于进位
for(int i=0;i<2000;i++){ //遍历数组
int b=a[i]+f; //低位进位f，f+原有数据等于该位置数据
a[i]=b%10; //调整为单个位数，通过除以10取余
f=b/10; //如果该位大于10，不管多大，除以十进位
}
}
int main(){
string s,t;
cin>>s;
while(s!=string(s.length(),'0')){ //将字符串除以二得到二进制数
int f=0; //每一位余数，高位除不尽将其加到低位
for(int i=0;i<s.length();i++){ //遍历字符串
int a=s[i]-'0'+f*10;
int b=a/2;
f=a%2;
s[i]=b+'0'; //调整字符串为除以2后的结果
}
char c=f+'0'; //一次循环相当于除以2，则将余数拼接到二进制结果中
t.append(1,c); //拼接到二进制字符串中
}
/**
*思想：
*得到二进制结果后，将二进制结果转换为十进制，
*转换方式即对应位乘以2的对应次幂，
*由于数据较大，需要用数组存储，把数组看为对应的十进制数，
*则每次加法即对应位相加，结果大于十需要进位。
*
*/
int temp[2000]={0};temp[0]=1; //2的幂，用数组存储，起始值为1；
int r[2000]={0}; //保存结果的数组
for(int i=t.length()-1;i>=0;i--){ //低位开始，每一个二进制都要计算
for(int j=0;j<2000;j++){
r[j]=r[j]+temp[j]*(t[i]-'0'); //将原有结果与2的对应次幂相加
}
for(int j=0;j<2000;j++) //每次计算完后，即乘以2，幂加一，为下一次相加做准备
temp[j]=temp[j]*2;
change(r); //调整为每位数为单个数
change(temp);
}
/**
*r数组保存结果，个位数在第一位，往后逐渐升高，个、十、百、千...
* 找到最高位，从最高位开始输出
*
*/
int loc=0;//找到最后一个数字位置，即最高位
for(int i=2000-1;i>=0;i--){
if(r[i]>0){
loc=i;
break;
}
}
for(int i=loc;i>=0;i--) //输出结果
cout<<r[i];
}
编辑于 2019-03-05 20:11:32
回复(1)
我不生产代码，我只是代码的搬运工😂
#include "stdio.h"
#include "string.h"
void convert(int m, char* original, int n, char* conversion){
int len = strlen(original),i,j,carry,k = 0;
for(i = 0; i < len;){//i是最高位，从最高位开始将每一位除以2，将余数传递给下一位
carry = 0;
for(j = i; j < len; j++){ //这一块，数字和字符的处理没搞清楚，
//其中carry是参与运算的，应该作为数字
//而original[j]则是保存当前的运算结果，应该是字符型的
original[j] = original[j] - '0' + carry*m;
carry = (original[j]) % n ;
original[j] = (original[j]) / n + '0';
}
conversion[k++] =(char) (carry + '0');
while(original[i] == '0')i++; //这一句是简直是精髓，在大进制转小进制时，
//当前的最高位orignal[i]可能无法循环一次就变成0
//小进制转大进制最高位可能一次循环就
//使得高几级位变成0
}
conversion[k] = '\0';
}
int main(){
char dec[1001],bin[4000];
int i,j;
char temp;
while(scanf("%s",dec) != EOF){
convert(10,dec,2,bin);
convert(2,bin,10,dec);
for(j = strlen(dec)-1,i=0;i<j;){//将字符串反序
temp = dec[i];
dec[i++] = dec[j];
dec[j--] = temp;
}
printf("%s",dec);
}
return 0;
}
发表于 2019-06-24 09:47:38
回复(0)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <iostream>
#include <ctype.h>
#include <string.h>
#include <set>
#include <stack>
#include<functional>
using namespace std;
#define MaxSize 1001
string conversion(int m, string a, int n){
int l = a.size(),k=0;
string b;
for (int i = 0; i < l;){
k = 0;
for (int j = i; j <l; j++)//12345 / 2 变成 06172 那么下次跳过了数字为0的下标，从6开始 ,但是下标总是以n结束
{
int t = (k*m + a[j] - '0') % n; //每次之和一位以及上一次的余数有关，向下传递一个余数
a[j] = (k*m + a[j] - '0') / n+'0';
k = t;
}
b += char(k + '0');
while (a[i]=='0') i++;//跳过这一次产生的高位的0
}
return b;
}
int main()
{
string a,b,c;
while (cin >> a){
b = conversion(10, a, 2);
a = conversion(2, b, 10);
reverse(a.begin(), a.end());
cout << a << endl;
}
}
发表于 2018-01-19 19:04:51
回复(7)
问题信息
难度：
103条回答
350收藏
17255浏览
通过挑战的用户
查看代码-
2023-02-28 23:13:17
-
2023-02-27 23:58:28
-
2023-02-22 13:31:43 -
2023-02-18 01:52:08 -
2023-02-13 15:48:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
