CODEWITHSUNDEEP
c++bit-manipulationaddition
jav974
jav974

Reputation: 1042

c++ bitwise addition , calculates the final number of representative bits

I am currently developing an utility that handles all arithmetic operations on bitsets. The bitset can auto-resize to fit any number, so it can perform addition / subtraction / division / multiplication and modulo on very big bitsets (i've come up to load a 700Mo movie inside to treat it just as a primitive integer)

I'm facing one problem though, i need for my addition to resize my bitset to fit the exact number of bits needed after an addition, but i couldn't come up with an absolute law to know exactly how many bits would be needed to store everything, knowing only the number of bits that both numbers are handling (either its representation is positive or negative, it doesn't matter)

I have the whole code that i can share with you to point out the problem if my question is not clear enough.

Thanks in advance. jav974

Upvotes: 0

Views: 534

Answers (2)

jav974
jav974

Reputation: 1042

Finally the number of representative bits after an addition is at maximum the number of bits of the one that owns the most + 1.

Here is an explanation, using an unsigned char:

For max unsigned char :

   11111111 (255)
+  11111111 (255)
= 111111110 (510)

Naturally if max + max = (bits of max + 1) then for x and y between 0 and max the result bits is at max + 1 (very maximum)

this works the same way with signed integers.

Upvotes: 0

Tony Delroy
Tony Delroy

Reputation: 106068

but i couldn't come up with an absolute law to know exactly how many bits would be needed to store everything, knowing only the number of bits that both numbers are handling (either its representation is positive or negative, it doesn't matter)

Nor will you: there's no way given "only the number of bits that both numbers are handling".

In the case of same-signed numbers, you may need one extra bit - you can start at the most significant bit of the smaller number, and scan for 0s that would absorb the impact of a carry. For example:

1010111011101 +
..10111010101
..^ start here

As both numbers have a 1 here you need to scan left until you hit a 0 (in which case the result has the same number of digits as the larger input), or until you reach the most significant bit of the larger number (in which case there's one more digit in the result).

1001111011101 +
..10111010101
..^ start here

In this case where the longer input has a 0 at the starting location, you first need to do a right-moving scan to establish whether there'll be a carry from the right of that starting position before launching into the left-moving scan above.

When signs differ:

  • if one value has 2 or more digits less than the other, then the number of digits required in the result will be either the same or one less than the digits in the larger input
  • otherwise, you'll have to do more of the work for an addition just to work out how many digits the result needs.

This is assuming the sign bit is separate from the count of magnitude bits.

Upvotes: 2

Related Questions