CODEWITHSUNDEEP
c++bit-manipulationbitwise-operatorsbitset
vvnraman
vvnraman

Reputation: 1343

Is there a trivial way to get the 2's complement of an std::bitset<N>

I was using std::bitset<N> in my program and needed to find the least significant set bit and did the trivial calculation as below :

int num = 5;
int res = num & (-num);

After which the least significant bit of num is set in res and rest all are 0's. This works as -5 is represented in 2's complement notation.

But I found std::bitset<N> doesn't have any operator overload for unary operator - which would have given me the 2's complement for the underlying bits. Is there a trivial way to implement the 2's complement with std::bitset<N> ? I could always use operator ~ to flip the bits and loop over them doing the sum and carry starting from LSB to MSB, but I was looking for a solution which would avoid that.

Upvotes: 5

Views: 2271

Answers (3)

Thesane
Thesane

Reputation: 1398

this should do it unless I am missing something

std::bitset<N> twos_comp = std::bitset<N>((~input).to_ulong() + 1);

Upvotes: 1

Zeta
Zeta

Reputation: 105876

std::bitset doesn't provide any complement methods. Since you would have to calculate the complement yourself with operator~ and an additional loop, simply skip operator~() and search for the LSB directly:

template <int N>
size_t least_significant_bit(const std::bitset<N> &bt){
    for(size_t i = 0; i < bt.size(); ++i){
        if(bt.test(i))
            return i;
    }
}

I guess it can't get more trivial than that ;).

Note that the result of least_significant_bit isn't specified if there's no bit at all. One could return N or change the loop in order to test bt.test(N) which would throw an exception, but after all it doesn't really make sense to look for a LSB in a nulled bitset.

Further note, you can use std::bitset<N>::operator[] instead of std::bitset<N>::test if you're not interested in boundary checks.

Upvotes: 2

Andreas Grapentin
Andreas Grapentin

Reputation: 5796

a quite convenient method for doing two's complement is finding the least significant 0 in your bitset, setting that to 1 and setting all less significant bits to 0.

pseudocode: (assuming that set[0] is the least significant bit, if not, turn it around)

int i = 0;
while (i < set.length && set[i])
  {
     set[i] = 0;
     ++i;
  }

if (i < set.length)
  set[i] = 1;

Upvotes: 0

Related Questions