One’s complement of a binary number (1001_{2}) is (0110_{2}). That is, we simply flip the bits. This is easy to do in binary. However, if the number is in base 10, then do we do that. Convert that to base 2 then flip the bits and change it back to base 2? Maybe, but if the number is stored in native data types (like int) then we can simply use bitwise not to invert the bits, without any conversion.
In my case it wasn’t so simple. I had a really big number, which had to be stored in BigDecimal. Converting to base 2, back and forth too is very costly. So the efficient algo for that is…
(x’) is the one’s complement of (x) and it has (b) bits, or we are interested in only (b) bits of it.
$$ \begin{align} &x + x’ = 2^{b+1} – 1 \tag{all ones for all b bits} \ &\Rightarrow x’ = 2^{b+1} – 1 – x \ \end{align} $$
So, the equivalent Java code for the above is…
public static BigDecimal onesComplement(BigDecimal n, int totalBits) {
return new BigDecimal(2).pow(totalBits + 1).subtract(BigDecimal.ONE).subtract(n);
}
