Categories
Coding Java Math Regulars

Find one’s complement of a decimal number.

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);
}

By Nirupam Biswas

I am not the one who goes out a lot, but likes to know about the outside a lot. Likes to make friends, well have lots of them, fortunately. Loves programming, well ‘am still learning.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.