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; } }