The problem: Given any size non-negative number in decimal string, write a routine to return a binary string representing the same number. (General problem: conversion between decimal string and binary string. See Light Bulbs Problem for more compact routines)
sample input sample output 16 10000 3 11 12 1100 1025 10000000001 sample input 839402839393939393479320103848494943949439 sample output 10011010001011001000100000100110000100010110001111111111100100100011101111100011 111000000001010011101010101000010110111101111101001001111111
The solution: the alogrithm is very straightforward. Based on the fact:
For any positive number n, n=(n/2)x2+r, r=0 (n is even), 1(n is odd)
Therefore, in the binary representation of n, r will be the last digit. If n/2 is not zero, repeat previous step with n/2, we will get the second last digit,... so on.
The complication here, however, is that n, n/2 are both represented as decimal string.
//Author: Victor Zeng 12/22/2006
#include <string>
using namespace std;
namespace decimalstring_to_binarystring {
bool dstrremainder(string &dstr, size_t &next, int &r);
// The function decimals2binarys will generate a binary string based on the input decimal string
// sample input sample output
// "16" "10000"
// "3" "11"
// "12" "1100"
// "1025" "10000000001"
// Please note that the dstr could be as long as 100 decimal digits, so the routine should be
// generic enough to handle very long strings.
string decimals2binarys(string dec_str)
{
string s;
size_t next = 0;
int r;
while (dstrremainder(dec_str, next, r))
s.insert(s.begin(),r+'0');
return s;
}
// The function dstrremainder will return true if the input decimal string represent
// non zero number and r will be the remainder of destr/2. next will be the index of next
// first decimal digit to handle. The function will leave destr/2 in destr.
// Sample input Sample output
// dstr next r dstr next r
// "16" 0 "08" 0 0
// "08" 0 "04" 1 0
// "04" 1 "02" 1 0
// "02" 1 "01" 1 0
// "01" 1 "00" 1 1
//
bool dstrremainder(string &dstr, size_t &next, int &r)
{
if (next>=dstr.size())
return false;
while (dstr.size()>next&&dstr[next]=='0') next++;
if (next>=dstr.size())
return false;
char d;
size_t i=next;
r = 0;
while(dstr.size()>i)
{
d = r*10+(dstr[i]-'0');
r = d%2;
d = d/2;
dstr[i] = d+'0';
i++;
}
return true;
}
}