subtracting two values of unknown bitsize

I'm trying to subtract two values from each other using twos compliment. I have a problem with the overflowing bit. Since my container hold an unlimited bit sized integer, I don't know if the top bit of the result is really from the result or just the overflow. How would I get rid of the overflow without using - (I can't just do 1 << bits - 1 since that would involve using the container, which has no working operator- yet)

0b1111011111 - 0b111010000 -> 0b1111011111 + 0b000110000 -> 1000001111

vs (normally)

0b00000101 - 0b000000001 -> 0b00000101 + 0b11111111 -> 0开发者_StackOverflowb100000100 -> 0b00000100

If you calculate a - b you must somehow "arrange" the word - as you have to make for the 2 compliment a negation with the bitwidth of m=max(bitwidth(a), bitwidth(b)).

To get rid of the of overflow you just do mask = negate(1 << m), and apply the mask with bitwise and. (Or you could just check that bit and treat it accordingly).

Your problem is that you are subtracting the 9-bit 111010000 from the 10-bit 1111011111. The two's complement of 111010000 is ...11111000110000, where the dots are trying to show that you have to pad to the left with as many 1 bits as you need. Here, you need 10 bits, so the two's complement of 111010000 is not 000110000 but 1000110000.

So you want to calculate 1111011111 + 1000110000 = 11000001111, which you just truncate to 10 bits to get the correct answer 1000001111.