CODEWITHSUNDEEP
c++binaryintegertwos-complementnegative-number
Jonathan Mee
Jonathan Mee

Reputation: 38919

Conversion of Binary into a Negative Integer

Let's hypothetically say that I have a collection of bits that I want to convert into an int, but the bits may represent a negative 2's complement number, so for example:

vector<bool> foo = { true, false, false, false, false, true, false, false }

Obviously if foo.front() is set then the number is negative. What would be the best way to convert this to an int?

This question seems to lack clarity. For reference I've added my brute force solution here: https://stackoverflow.com/a/50108264/2642059 I want to accomplish this same thing but ideally with some provided functionality and not so much hackery.

Upvotes: 0

Views: 374

Answers (3)

Red.Wave
Red.Wave

Reputation: 4191

std::vector<bool> foo;
//...
long long val=0;
for(auto& bit:foo){
    val<<=1;
    val+=bit;
};

if(foo.front())//sign extension
    val+=~0ll<<foo.size();

Upvotes: 1

Jonathan Mee
Jonathan Mee

Reputation: 38919

The leading set bits for a number, including the bit that should be set for foo.front(), can be generated by doing: -(1 << size(foo) - 1). After this you need only shift in the remainder of your bits.

This for example will generate the correct number whether or not foo.front() is set:

int i = size(foo) - 1;
const auto bar = accumulate(next(cbegin(foo)), cend(foo), foo.front() ? -(1 << i) : 0, [&](const auto val, const auto it) { return val + (it << --i); });

Live Example

Upvotes: 0

Barmar
Barmar

Reputation: 780724

In two's complement notation, the negative of a number is the complement plus 1.

When foo.first() == true, convert all the remaining elements to binary digits, then invert it and add 1. Then return the negative of this.

So in your example, the remaining elements correspond to the binary number 0000000. Complement this to 1111111, which is 127. Add 1 and you get 128, and then you return -128. And indeed, the value -128 is represented as 10000000 in 8-bit two's complement.

The signed data type you use for this process needs to be at least 1 bit larger than the size of the vector, to avoid overflowing when you add 1 to "all bits set" value. So if your vector can be up to 32 elements (including the sign), you need to use int64_t.

Upvotes: 0

Related Questions