Converting many bits to Base 10

Question

I am building a class in C++ which can be used to store arbitrarily large integers. I am storing them as binary in a vector. I need to be able to print this vector in base 10 so it is easier for a human to understand. I know that I could convert it to an int and then output that int. However, my numbers will be much larger than any primitive types. How can I convert this directly to a string.

Here is my code so far. I am new to C++ so if you have any other suggestions that would be great too. I need help filling in the string toBaseTenString() function.

class BinaryInt { private: bool lastDataUser = true; vector<bool> * data; BinaryInt(vector<bool> * pointer) { data = pointer; } public: BinaryInt(int n) { data = new vector<bool>(); while(n > 0) { data->push_back(n % 2); n = n >> 1; } } BinaryInt(const BinaryInt & from) { from.lastDataUser = false; this->data = from.data; } ~BinaryInt() { if(lastDataUser) delete data; } string toBinaryString(); string toBaseTenString(); static BinaryInt add(BinaryInt a, BinaryInt b); static BinaryInt mult(BinaryInt a, BinaryInt b); }; BinaryInt BinaryInt::add(BinaryInt a, BinaryInt b) { int aSize = a.data->size(); int bSize = b.data->size(); int newDataSize = max(aSize, bSize); vector<bool> * newData = new vector<bool>(newDataSize); bool carry = 0; for(int i = 0; i < newDataSize; i++) { int sum = (i < aSize ? a.data->at(i) : 0) + (i < bSize ? b.data->at(i) : 0) + carry; (*newData)[i] = sum % 2; carry = sum >> 1; } if(carry) newData->push_back(carry); return BinaryInt(newData); } string BinaryInt::toBinaryString() { stringstream ss; for(int i = data->size() - 1; i >= 0; i--) { ss << (*data)[i]; } return ss.str(); } string BinaryInt::toBaseTenString() { //Not sure how to do this }

You don't want to use std::vector<bool> here, and you don't want a pointer to a vector. Something like std::vector<unsigned> data;, plus an additional flag for the sign, would be the simplest. — James Kanze
– James Kanze, Commented Oct 14, 2013 at 16:08
And for the conversion, you'll need to implement / and % (preferably with int as well as with BinaryInt). — James Kanze
– James Kanze, Commented Oct 14, 2013 at 16:11
Why don't I want to use a pointer? If I'm storing so much data shouldn't it go on the stack. I also think using the point makes copying my class much more efficient since I don't have to copy over the data. — chasep255
– chasep255, Commented Oct 14, 2013 at 18:11
The size of vector<bool> isn't particularly large, regardless of how many elements it contains. And for something like BinaryInt, you need value semantics. — James Kanze
– James Kanze, Commented Oct 15, 2013 at 8:12

pineconesundae · Accepted Answer · 2013-10-16 14:16:54Z

I know you said in your OP that "my numbers will be much larger than any primitive types", but just hear me out on this.

In the past, I've used std::bitset to work with binary representations of numbers and converting back and forth from various other representations. std::bitset is basically a fancy std::vector with some added functionality. You can read more about it here if it sounds interesting, but here's some small stupid example code to show you how it could work:

std::bitset<8> myByte; myByte |= 1; // mByte = 00000001 myByte <<= 4; // mByte = 00010000 myByte |= 1; // mByte = 00010001 std::cout << myByte.to_string() << '\n'; // Outputs '00010001' std::cout << myByte.to_ullong() << '\n'; // Outputs '17'

You can access the bitset by standard array notation as well. By the way, that second conversion I showed (to_ullong) converts to an unsigned long long, which I believe has a max value of 18,446,744,073,709,551,615. If you need larger values than that, good luck!

PaperBirdMaster · Accepted Answer · 2013-10-14 16:02:59Z

Just iterate (backwards) your vector<bool> and accumulate the corresponding value when the iterator is true:

int base10(const std::vector<bool> &value) { int result = 0; int bit = 1; for (vb::const_reverse_iterator b = value.rbegin(), e = value.rend(); b != e; ++b, bit <<= 1) result += (*b ? bit : 0); return result; }

Live demo.

Beware! this code is only a guide, you will need to take care of int overflowing if the value is pretty big.

Hope it helps.

That would work, however, I will be dealing with millions of bits. I need to skip the converting to and int and go directly to a string.

Collectives™ on Stack Overflow

Converting many bits to Base 10

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related