Decimal to binary without arrays and binary-operators (like "&")

Question

I have to do a task for the university to write a program that converts a decimal number into binary. As I am only in a preliminary course of computer science, there were no arrays or bitwise operators (like '&') introduced yet. The program needs to be written using basic operators (+,-,*,%) and (if-else,for) only. My approach is the following, but I always get the inverted value. So instead of 1100, 0011.

#include <iostream>
int main()
{
   int n,a;
   std::cin >> n;
   
   for (int i=n; n>0; --i) {
       
     a = n%2;
     std::cout << a;
     n = n/2;
   
   }

   return 0;
}

is there a way to solve this problem?

Answer 1

If you know that you're getting the right output only backwards, think about what you can do to fix that issue. Just reverse the bits. Here's a way to do that using only basic features.

#include <iostream>
int main()
{
   int n,a;
   int bitCount = 0;
   std::string reversedBits;
   std::cin >> n;
   
   for (int i=n; n>0; --i) {
     a = n % 2;
     reversedBits += a + '0';
     ++bitCount;
     n = n / 2;
   }

   for (int i = bitCount - 1; i >= 0; --i) {
       std::cout << reversedBits[i];
   }

   return 0;
}

That's not to say that this is the best way to do this. It would be a good exercise for you to figure out a few ways to solve this problem.

Answer 2

Your current code checks for presence of the binary value from LSB to MSB, and prints in that order. One way to approach the issue would be to instead check from MSB to LSB.

#include <iostream>
int main(){
  int n, a=1;
  std::cin >> n;

  while(2*a <= n)
    a *= 2;                                                                                                               
  while(a > 0){
    if (n >= a){
      std::cout << 1;
      n -= a;
    } else {
      std::cout << 0;
    }
    a /= 2;
  }
  std::cout << std::endl;
  return 0;
}

This isn't a great way to do this, and I recommend improving it or finding alternatives as an exercise.

Answer 3

I am going propose a very simple solution that is purely arithmetic in nature and doesn't involve any of the bit level hacks you can otherwise use to solve this nor arrays that haven't been covered in your class. As you've observed your approach gives you the binary number in reverse. Instead of printing the digits you get directly, use an integer to hold the calculated digits in the right order by placing the computed digit in the correct position.

Consider this snippet:

#include <iostream>

int main()
{
   int n,a;
   int result = 0;
   int position = 1;

   std::cin >> n;
   
   for (int i=n; n>0; --i) {
     a = n%2;
     n = n/2;
     
     result += position * a;
     position *= 10;
   }
   
   std::cout << result << std::endl;    
   return 0;
}

Tracing out your example of input 12:

1. First iteration: a is zero, so Result = 0, position is updated to 10 from 1
2. Second iteration: a is zero again, so Result = 0, position is updated to 100 from 10
3. Third iteration: a is non zero, so Result is now 100 (position * 1), position is updated to 1000 from 100
4. Fourth iteration: a is non zero, Result becomes 100 + 1000 = 1100, position is updated to 10000 from 1000

Answer 4

Here I provide a recursive solution.

I also used argv to allow multiple inputs on command line, and each input can be either decimal-text or hex-text.

I use stringstream, rather than cin. Note, they both inherit the same stream input operations.

#include <iostream>
using std::cout, std::cerr, std::endl, std::hex, std::dec;

#include <string>
using std::string;

#include <sstream>
using std::stringstream, std::istringstream;

#include <cstdint>


//  typical output    vvvvv      v   v   v   v   v
//  n:   7340032   0x700000   11100000000000000000000

//  commands -- both the same input value
//  ./dumy899d 7340032
//  ./dumy899d 0x700000
//
//  which can be mixed in the same argv list:
//  ./dumy899d  7340032  0x700000



// recursion max depth: bit width of n (32 on my system)
void to_binary_R (string& retVal, int n)
{
  if (0 == n)  return;        // recursion termination clause
  to_binary_R (retVal, n/2);  // (n / 2) shifts all bits of n to right 

  // n is on the stack and will be unchanged when the PC returns,
  // thus, during 'decurse':
  int a = (n % 2)   +  '0';  // do computation, a is 0x30 or 0x31
  //  int (0 or 1)    0x30 -- char is auto promoted to int

  retVal += static_cast<char>(a);  // append-to-retVal
  //        no-code-cast: 30, 31 become chars '0', '1' with cast
}

// i sometimes prefer to return a string 
//    (this can enable reducing cout-pollution)

string to_binary(int n) 
{
  string s; s.reserve(64); // declare & reserve space
  to_binary_R(s, n);       // fill
  return s;
}    

// forward declartions
// returns true when user input has '0x' 
bool hexUI(const string& s);

void usage(); 


int main(int argc, char* argv[])
{
  if (argc < 2) { usage(); return -1; }

  for (int indx = 1; indx < argc; ++indx)
  {
    char* arg = argv[indx];  // instead of std::cin >> n;

    stringstream ss(arg);

    int nOrig = 0;

    if (hexUI(arg)) { ss >> hex >> nOrig; } 
    else            { ss >> dec >> nOrig; } 

    if (!ss.good() && !ss.eof()) // when not good state that is not
    {                            // caused by eof()
      // notify user:
      cerr << "\n\n ERR: ss is not good() (and not eof) "
           << "Maybe a hex parameter prefix is missing '0x'?\n" 
           << endl;
      return -2;
    }

    cout << "\n  n:   " << dec << nOrig
         << "   0x"     << hex << nOrig
         << "   "       << to_binary(nOrig)
         << endl;

  } // for (int indx = 1; indx < argc; ++indx)

  return 0;
} // int main()


// returns true when user input specifies hex with '0x' prefix
bool hexUI(const string& s) { return (s.find("0x") != string::npos); }

void usage()
{
  cerr << "\n  err:  expecting 1 or more command line arguments, each argument is "
       << "\n        either decimal-text or hex-text (marked with '0x' prefix) "
       << "\n        values are displayed in decimal, binary, and hex"
       << endl;

  cout << "\n  The following info might be different on your system:"
       << "\n  My development system: Linux 20.04, using g++ v9.3.0";

  cout << "\n             sizeof(int) : "
       << sizeof(int) << " bytes    "         // 4  bytes
       << (sizeof(int) * 8) << " bits";       // 32 bits

  cout << "\n        sizeof(long int) : "
       << sizeof(long int) << " bytes    "    // 8 bytes
       << (sizeof(long int) * 8) << " bits";  // 64 bits

  // consider specifying the size, such as
  cout << "\n         sizeof(int64_t) : "
       << sizeof(int64_t) << " bytes    "     // 8 bytes
       << (sizeof(int64_t) * 8) << " bits"    // 64 bits
       << endl;
}

Answer 5

is there a way to solve this problem?

I thought of another apprach, with three steps.

string toHex_ToBin(int n, bool slz)
{
  // STEP 1: create hex encoding using stringstream and hex
  stringstream ss;
  ss << hex << n;

  string s = ss.str();

  // STEP 2: use these hex chars to append corresponding binary codes
  //         to empty return string
  string m_s; 
  for (uint i = 0; i < s.size(); ++i)
  {
    switch (toupper(s[i]))
    {
    case '0': { m_s += "0000"; break; }
    case '1': { m_s += "0001"; break; }
    case '2': { m_s += "0010"; break; }
    case '3': { m_s += "0011"; break; }
    case '4': { m_s += "0100"; break; }
    case '5': { m_s += "0101"; break; }
    case '6': { m_s += "0110"; break; }
    case '7': { m_s += "0111"; break; }
    case '8': { m_s += "1000"; break; }
    case '9': { m_s += "1001"; break; }
    case 'A': { m_s += "1010"; break; }
    case 'B': { m_s += "1011"; break; }
    case 'C': { m_s += "1100"; break; }
    case 'D': { m_s += "1101"; break; }
    case 'E': { m_s += "1110"; break; }
    case 'F': { m_s += "1111"; break; }
    // default: assert(0); break; 
    }  
    // I leave this question to the reader, "would a 
    // vector<string> hex2bin = {"0000", "0001", .. "1111"};
    // simplify this effort? "
  } // for loop

  // STEP 3 - if requested by user (via bool slz)
  if(slz) // suppress leading zero's
  {
    size_t pos = m_s.find('1'); // find left most one
    if (pos != std::string::npos)
      m_s.erase(0, pos);
  }
  return m_s;
}