编码 0 到 31(含)范围内的整数需要多少位?

How many bits are necessary to encode an integer in the range of 0 to 31 (inclusive)?

有人可以解释一下如何解决这样的问题吗?

在二进制中,最好想到一列1和0。 每列代表 2 的某个幂。你从右往左读,最右边总是2^0次方,后面是2^1,等等等等

当 2 ^ 0 设置为 0 时,您得到的值为 0。 当 2^0 设置为 1 时,您得到的值为 1(任何提高到零次方的都是 1。)

将二进制 1 或 0 视为打开或关闭。 您根据各自的输出对 "ons" 求和。 每列或 0/1 值代表一个位。

000000 = 0
000001 = 1
000010 = 2
000011 = 3
000100 = 4
000101 = 5
000110 = 6
000111 = 7

等等。由于 2^5 = 32,因此第 6 列而不是第 5 列中需要有 1。因为我们从第零次指数开始。

100000 = 32, so 6 bits, but it was only inclusive of 31, so we have to go down one value.
011111 = 31, so 5 bits, are absolutely necessary for representing the number 31.

你需要 5 位。每个位可以有两个值之一,5位的组合数是2^5。您可以通过考虑基本情况来证明 2^n 是 n 位组合的数量:

1 位 = 两个可能的选择 = 2^1

然后是归纳步骤。

如果我们有N位,那么我们可以把它分成1位加n-1位。如果公式为真,则最后 n-1 位有 2^(n-1) 种组合,对于这些组合中的每一种,第一位可以位于两个位置之一。因此,对于 N 位,有 2*(2^(n-1)) 种组合,等于 2^(n-1+1) 等于 2^n。

这是归纳法证明。第一步很简单 (n=1),然后第二步告诉我们,如果 n=1 成立,那么 n=2 成立,然后是 n=3,然后是 n=4,等等

"Bits" 是 "binary digits"。这意味着(根据定义)它们是 base-2 数字系统中的数字。因此,与您习惯的以 10 为基数的系统(每列中有数字 0-9)不同,您只能为每列获得两个值(0 或 1)。

10 进制系统中的每一列都对应于 10 的幂——例如,123 是 1 x 10^2 + 2 * 10^1 + 3 * 10^0。

二进制以 2 为基数,而不是 10 0 是十进制的 19。

现在,要计算出您需要多少位(即数字)来表示给定的数字范围,您可以从一位开始并不断添加另一位,直到您有足够的空间。例如,0-1 将适合单个位; 50 至少需要 6 位,因为 1 只够 0-1,2 位只够 0-3,3 位只够 0-7,等等,直到你得到 5 位只够0-31,但 6 已经足够了。

每增加一位,那么多位可以表示的可能数字的数量就会增加一倍(就像添加另一个以 10 为底的数字可以表示十倍的数字一样)。 0位可以代表0个数。 1位可以表示2个数(0-1)。 2位可以表示2*2个数。 3位可以表示2*2*2 = 2^3个数。 4位可以表示2^4个数。等等。

唯一需要考虑的棘手问题是可表示数字的数量与这些表示对应的实际范围之间的区别。例如,如果您有 4 位,则有 2^4 种不同的位组合(0000 到 1111)。但是如果你认为 0000 代表零,那么你可以放入四位的最大数字是 15(不是 16,因为即使有十六种不同的可能表示,范围 [0-15] 包含十六个不同的数字(计算它们!)因此 16 本身就是第 17 个数字,因此需要 5 位来表示)。

我希望这能澄清事情!