以 10 为底的整数公式的补码证明在哪里？

Question

因此，对于 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，任何人都可以提供证据来证明为什么 2^（二进制数字的长度）- 1 给出完整的 111....1111 二进制数。如果有人可以更整洁地重写这个问题，请这样做。

Answer 1

linked-to 代码效率远。 Math.pow（相对于基本的位操作）非常昂贵，而且计算 N 的位边界的循环也不必要地低效。

为什么 2^5-1 在位中总是全 1 位的序列？

因为2^x是二进制数系统的字面定义。如果方便的话，还是说小数吧：

什么是 10^1？是 10。什么是 10^2？是 100。10^3 是 1000，等等。从其中任何一个中减去 1，您分别得到 9、99 和 999：最高位（十进制为 9，但二进制为 1）。因此，x^y-1 其中 x 是基数（十进制是 'base 10'，二进制是 'base 2'），y 是任何正整数，给出该基数中的最高数字，重复 y次，如果你在那个基地打印那个数字。 2^18-1 在二进制中是 18x 1。出于同样的原因 10^18-1 给你 18x 9.

我们怎样才能更有效地Math.pow(2,n)

相同的解释：因为 2^x 字面意思是描述二进制数学，而计算机非常擅长这些，而按位运算就是二进制数学。全部为二进制：

1 是十进制的 1。 10 是十进制的 2。 101 是十进制的 5。 1010 是十进制的 10。

总的原则就是，如果你直接在末尾加一个0，就等于把这个数乘以2。回到十进制，如果我给你任何一个数，比如说12493821345，写在一张纸上纸，我要你写那个数字乘以 10（记住，十进制 = 底数 10，二进制 = 底数 2），你只需.. 在末尾加一个零。二进制也一样：末尾加0等同于乘以2。

所以，除了 Math.pow(2, n)，您可以只.. 添加 n 个零。您使用位移运算符执行的操作：“添加 5 个零”与“将位向左移动 5 个位置”相同。除了移位大大更有效。

因此，如果我想要 2^10-1，最有效的方法是：

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

因此，那应该是 int pow = (1 << n) - 1;。

如何快速从 N=5 到 `111`？

你真正想知道的是：你输入的数字中最高 1 位的位置是多少。

5 在二进制中是 101 并且所需的数字是 2（因为计算机中的计数是基于 0 的，位置 2 是您找到第 3 位的位置）如：我们需要 3 1位。换句话说，你的问题是：最高 1 位是多少。 Java 有一个方法：Integer.highestOneBit(5)。这不是 return 最高 1 位的位置，而是只有该位设置为 1 的数字。换句话说，5 是 101，而 7 是 111。对于这两个，highestOneBit returns 100 (4)。左移 1 减 1 将 5 和 7 都变成 7，这就是你想要的。

请注意这将如何执行更少的操作。另请注意，这些函数已 HIGHLY 调整。毫不夸张地说，java 性能工程师深入研究了这些，以找到在大多数处理器上运行最快的实现，同时考虑到预测流水线和 CPU 缓存的变化无常。他们倾向于把这类事情做好，所以，你应该使用他们的东西。 Java 是开源的，如果需要可以查看实现。

你能再优化一下吗？

但我们当然可以。

我真正需要做的就是先翻转所有位，然后 'unflip' 前导零。给定 5，比方说，一个字节：0000 0101，我们想要翻转所有位，但不是前导零：0000 0010 = 2，这是正确的答案。 Java 有一个 'flip all bits' 运算符（NOT 运算符，~），所以我们只需要 'flip all bits' + 'zero out all those leading bits'.

这让我们：

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

没有循环。（hOB 的实现也没有循环），没有昂贵的数学运算。所有基本的位摆弄。除了你的边缘情况，one-liner.

我们来测试一下！

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

似乎工作得很好。

Answer 2

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

在（无符号）二进制表示法中，由N个“一”位组成的数字表示

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

其中 N >= 1。

所以我们真正需要证明的是命题P(N)

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

归纳证明

基本情况，N = 1。

2^N - 1 = 2^1 - 1
        = 2 - 1
        = 1
        = 2^0

Thus `P(1)` is proven

鉴于P(N)为真，我们需要证明P(N+1)也为真；即证明 P(N) => P(N+1) where N >= 1

假设P(N)为真；即 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

但是

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

因此

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

因此P(N) => P(N+1) where N >= 1得证

从第一步，P(1)被证明

从第 2 步，P(N) => P(N+1) where N >= 1 被证明

因此，通过归纳，P(N) for all N >= 1被证明。

QED.

以 10 为底的整数公式的补码证明在哪里？

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

java

math

optimization

binary

proof

为什么 2^5-1 在位中总是全 1 位的序列？

我们怎样才能更有效地Math.pow(2,n)

如何快速从 N=5 到 `111`？

你能再优化一下吗？

以 10 为底的整数公式的补码证明在哪里？

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

java

math

optimization

binary

proof

为什么 2^5-1 在位中总是全 1 位的序列？

我们怎样才能更有效地Math.pow(2,n)

如何快速从 N=5 到 111？

你能再优化一下吗？

如何快速从 N=5 到 `111`？