Where is the proof for complement of base 10 integer formula?

So,for https://leetcode.com/problems/complement-of-base-10-integer/discuss/879910/Java-100-faster-solution-trick-to-find-2(digits-of-N)-1-greater-(11111)-and-subtract-N-from-it can anyone provide the proof to why 2^(length of binary digits) - 1 gives the full 111....1111 binary number full of ones. If anyone can rewrite this question neater please do.

> Can anyone provide the proof to why 2^(length of binary digits) - 1 gives the full 111....1111 binary number full of ones.

In (unsigned) binary notation, the number consisting of N "one" digits means

2^0 + 2^1 + 2^2 + .... + 2^(N-1)

where N >= 1.

So what we actually need to prove is Proposition P(N)

2^N - 1 = 2^0 + 2^1 + 2^2 + .... + 2^(N-1) where N >= 1.

Proof by induction

1. Base case, N = 1.

   2^N - 1 = 2^1 - 1
           = 2 - 1
           = 1
           = 2^0
   
   Thus `P(1)` is proven
   

2. Given that P(N) is true, we need to show that P(N+1) is also true; i.e. prove that P(N) => P(N+1) where N >= 1

   Assume P(N) is true; i.e 2^N - 1 = 2^0 + 2^1 + 2^2 + .... + 2^(N-1)

   (2^N - 1) * 2     = 2 * (2^0 + 2^1 + 2^2 + .... + 2^(N-1))
                     = 2 * 2^0 + 2 * 2^1 + 2 * 2^2 + 2 * 2^(N-1)
                     = 2^1 + 2^2 + 2^3 + ... + 2^N
   
   (2^N - 1) * 2 + 1 = 1   + (2^N - 1) * 2
                     = 2^0 + (2^N - 1) * 2
                     = 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^N
   

   but

   (2^N - 1) * 2 + 1 = 2 * 2^N - 2 * 1 + 1
                     = 2^(N+1) - 2 + 1
                     = 2^(N+1) - 1
   

   and therefore

   2^(N+1) - 1       = 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^N
   

   Thus P(N) => P(N+1) where N >= 1 is proven

3. From step 1, P(1) is proven

   From step 2, P(N) => P(N+1) where N >= 1 is proven

   Therefore, by induction, P(N) for all N >= 1 is proven.

QED.

The linked-to code is far from efficient. Math.pow is (relative to basic bit manipulation) incredulously expensive, and a loop to figure out the bit bound of N is also unneccessarily inefficient.

Why is 2^5-1 always, in bits, a sequence of all-1 bits?

Because 2^x is the literal definition of the binary number system. If it's more convenient for you, let's talk decimal:

What's 10^1? It's 10. What's 10^2? It's 100. 10^3 is 1000, etcetera. Subtract 1 from any of these and you get, respectively, 9, 99, and 999: The highest digit (which in decimal is 9, but in binary it is 1). So, x^y-1 where x is a base (decimal is 'base 10', binary is 'base 2') and y is any positive integer gives you the highest digit in that base, repeated y times, if you print that number in that base. 2^18-1 in binary is 18x 1. For the same reason 10^18-1 gives you 18x 9.

How can we do Math.pow(2,n) more efficiently

Same explanation: Because 2^x is literally describing binary math and computers are really good at those, and bitwise ops are binary math. All in binary:

1 is, well, decimal 1.
10 is decimal 2.
101 is decimal 5.
1010 is decimal 10.

The general principle is, if you just shove a 0 on the end, it's the same as multiplying the number by 2. Going back to decimal, if I give you any number, let's say 12493821345, written on a piece of paper, and I Ask you to write that number multiplied by 10 (remember, decimal = base 10, binary = base 2), you just.. add a zero on the end. Same for binary: Adding a 0 at the end is the same as multiplying by 2.

So, instead of Math.pow(2, n), you can just.. add n zeroes. Which you do with the bit shift operator: "add 5 zeroes" is the same as "shift the bits 5 positions to the left". Except bit shift is vastly more efficient.

Thus, if I want 2^10-1, the efficient way to do that is:

int n = 10;
int y = (1 << n) -1;
// y is now 1023, which is indeed 2^10 -1.

thus, that should have been int pow = (1 << n) - 1;.

How do you get from N=5 to 111 quickly?

What you're really getting at with this question is: What is the position of the highest 1 bit in your input number.

5 in binary is 101 and the desired number is 2 (because counting in computers is 0 based, position 2 is where you find the 3rd bit) as in: We need 3 1 bits. In other words, your question is: What's the highest 1 bit. Java has a method for that: Integer.highestOneBit(5). This doesn't return the position of the highest 1 bit, but that number where only that bit is set to 1. In other words, 5 is 101, and 7 is 111. For both of these, highestOneBit returns 100 (4). shift that left by 1 and subtract 1 and you turn both 5 and 7 into 7, which is what you want.

Note how this will perform far fewer operations. Note also that these functions are HIGHLY tuned. Quite literally java performance engineers delved real deep on these to find the implementation that runs fastest on most processors taking into account the vagaries of predictive pipelining and CPU caches. They tend to get this sort of thing right, so, you should use their stuff. Java is open source, you can check out the implementation if you want.

Can you optimize even more?

But of course we can.

All I really need to do is to first just flip all the bits, but then 'unflip' the leading zeroes. Given 5 in, say, a byte: 0000 0101, we want to flip all bits, but not the leading zeroes: 0000 0010 = 2 which is the right answer. Java has a 'flip all bits' operator (the NOT operator, ~), so all we need is 'flip all bits' + 'zero out all those leading bits'.

That gets us to:

public static int complement(int n) {
if (n == 0) return 1; // apparently an edge case; I'd say it's 0.
return ~n & ((Integer.highestOneBit(n) << 1) - 1);
}

No loops. (the impl of hOB also has no loops), no pricey Math operations. All basic bit twiddling. Other than your edge case, a one-liner.

Let's test it!

complement(5) --> 101 -> 010 -> 2
complement(7) --> 111 -> 000 -> 0
complement(8) --> 1000 -> 0111 -> 7

seems to be working great.