26

这是一个我一直坚持的家庭作业问题。

考虑无符号整数表示。存储包含以下内容的十进制数需要多少位:

i) 3 digits ii) 4 digits iii) 6 digits iv) n digits

我知道无符号整数的范围是 0 到 2^n,但我不知道表示数字所需的位数如何取决于它。请帮帮我。

提前致谢。

4

12 回答 12

32

好吧,您只需要计算每种情况的范围并找到高于该范围的 2 的最低幂。

例如,在 i) 中,3 个十进制数字 -> 10^3 = 1000 个可能的数字,因此您必须找到高于 1000 的 2 的最小幂,在本例中为 2^10 = 1024(10 位)。

编辑:基本上你需要用你所拥有的位数找到可能的数字的数量,然后找到哪个位数(在另一个基数中,在这种情况下为基数 2,二进制)至少与一个可能的数字相同十进制。

要计算给定位数的可能性数量:possibilities=base^ndigits

所以,如果你有 3 位十进制数字(以 10 为底),你就有10^3=1000可能。然后你必须找到一些二进制数字(位,以 2 为底),这样可能性的数量至少为 1000,在这种情况下是2^10=1024(9 位是不够的,因为2^9=512它小于 1000)。

如果你概括这一点,你有:2^nbits=possibilities <=> nbits=log2(possibilities)

应用于 i) 给出:log2(1000)=9.97并且由于位数必须是整数,因此您必须将其四舍五入到 10。

于 2011-08-22T15:52:55.597 回答
18

存储n 个整数(例如0n - 1 )所需的二进制位数的公式为:

日志e (n) / 日志e (2)

并四舍五入。

例如,对于值 -128 到 127(有符号字节)或 0 到 255(无符号字节),整数的数量为 256,因此n为 256,从上述公式中得出 8。

对于0n,在上面的公式中使用n + 1(有n + 1 个整数)。

在您的计算器上,log e可能只是标记为logln(自然对数)。

于 2016-11-22T16:21:25.100 回答
9

以b为底的n位数字可以表示的最大数是b n - 1。因此,可以用N个二进制数字表示的最大数是2 N - 1。我们需要最小的整数N使得:

2 N - 1 ≥ b n - 1
⇒ 2 N ≥ b n

取最后一个表达式两边的以 2 为底的对数给出:

log 2 2 N ≥ log 2 b n
⇒ N ≥ log 2 b n
⇒ N ≥ log b n / log 2

因为我们想要满足最后一个关系的最小整数N ,所以要找到N,找到log b n / log 2并取上限。

在最后一个表达式中,对数的任何底都可以,只要两个底相同。这里很方便,因为我们对b = 10的情况感兴趣,使用以 10 为底的对数,利用log 10 10 n == n

对于n = 3

N = ⌈3 / log 10 2⌉ = 10

对于n = 4

N = ⌈4 / log 10 2⌉ = 14

对于n = 6

N = ⌈6 / log 10 2⌉ = 20

通常,对于n 个十进制数字:

N = ⌈n / log 10 2⌉</p>

于 2017-07-19T21:18:48.070 回答
3

可以通过这种方式来概括您需要多少位来表示一个数字的技术。你有 R 个符号来表示,你想知道有多少位,求解这个方程 R=2^n 或 log2(R)=n。其中 n 是位数,R 是表示的符号数。

对于十进制数系统 R=9,所以我们解决 9=2^n,答案是每个十进制数字 3.17 位。因此,3 位数字需要 9.51 位或 10 位。1000 位数字需要 3170 位

于 2012-07-20T20:32:49.900 回答
1

假设问题是询问您存储所需的最小位数是多少

  1. 3位数字

我对这个问题的处理方法是:

  • 我们需要存储的最大 3 位数字是多少?答:999
  • 我存储这个数字所需的最少位数是多少?

这个问题可以通过递归地将 999 除以 2 来解决。然而,使用数学的力量来帮助我们更简单。本质上,我们正在为以下等式求解 n:

2^n = 999
nlog2 = log999
n ~ 10

您需要 10 位来存储 3 位数字。

使用类似的方法来解决其他子问题!

希望这可以帮助!

于 2015-06-10T08:25:59.337 回答
0

让它所需的 n 位然后 2^n=(base)^digit 然后取日志并计数。对于 n

于 2014-01-24T15:33:52.860 回答
0

继续将数字除以 2,直到商为 0。

于 2011-08-22T16:27:00.533 回答
0

对于 n 位数的二进制数,它可以保存的最大十进制值将是

2^n - 1,2^n 是可以使用这些数字生成的总排列。

以您只需要三位数的情况为例,即您的情况1。我们看到要求是,

2^n - 1 >= 999

将日志应用到两侧,

日志(2^n - 1) >= 日志(999)

对数(2^n)-对数(1)>=对数(999)

n = 9.964(大约)。

取 n 的 ceil 值,因为 9.964 不能是有效的位数,我们得到 n = 10。

于 2015-02-20T09:20:03.397 回答
0

最简单的答案是将所需的值转换为二进制,然后查看该值需要多少位。但是,该问题询问十进制 X 位数有多少位。在这种情况下,您似乎必须选择 X 位的最大值,然后将该数字转换为二进制。

作为一个基本示例,假设我们想要存储一个以 10 为基数的 1 位数字,并且想知道需要多少位。最大的 1 位以十为基数是 9,所以我们需要将其转换为二进制。这产生 1001,总共有 4 位。同样的示例也可以应用于两位数(最大值为 99,转换为 1100011)。要求解 n 个数字,您可能需要求解其他数字并搜索模式。

要将值转换为二进制,请反复除以 2,直到商为 0(所有余数均为 0 或 1)。然后,您反转余数的顺序以获得二进制数。

示例:13 到二进制。

  • 13/2 = 6 转1
  • 6/2 = 3 r 0
  • 3/2 = 1 r 1
  • 1/2 = 0 r 1
  • = 1101 ((8*1) + (4*1) + (2*0) + (1*1))

希望这会有所帮助。

于 2011-08-22T17:23:37.050 回答
0

这里有很多答案,但我会添加我的方法,因为我在解决同样的问题时发现了这篇文章。

从我们这里所知道的开始是从 0 到 16 的数字。

Number           encoded in bits         minimum number of bits to encode
0                000000                  1
1                000001                  1
2                000010                  2
3                000011                  2
4                000100                  3
5                000101                  3
6                000110                  3
7                000111                  3
8                001000                  4
9                001001                  4
10               001010                  4
11               001011                  4
12               001100                  4
13               001101                  4
14               001110                  4
15               001111                  4
16               010000                  5

查看休息时间,它显示了这张表

number <=       number of bits
1               0
3               2
7               3
15              4

那么,现在我们如何计算模式呢?

请记住,以 2 为底的对数 (n) = 以 10 为底的对数 (n) / 以 10 为底的对数 (2)

number    logb10 (n)   logb2 (n)   ceil[logb2(n)] 
1         0            0           0           (special case)
3         0.477        1.58        2
7         0.845        2.807       3  
8         0.903        3           3           (special case)
15        1.176        3.91        4
16        1.204        4           4           (special case)
31        1.491        4.95        5
63        1.799        5.98        6

现在所需的结果与第一个表匹配。请注意,某些值也是特殊情况。0 和任何 2 的幂数。当您应用上限时,这些值不会改变,因此您知道需要加 1 才能获得最小位字段长度。

为了考虑特殊情况,在输入中添加一个。在 python 中实现的结果代码是:

from math import log
from math import ceil
def min_num_bits_to_encode_number(a_number):
    a_number=a_number+1  # adjust by 1 for special cases

    # log of zero is undefined
    if 0==a_number:
        return 0
    num_bits = int(ceil(log(a_number,2)))  # logbase2 is available
    return (num_bits)
于 2017-05-24T13:03:13.590 回答
0

简短的回答是:

int nBits = ceil(log2(N));

这仅仅是因为pow(2, nBits)略大于 N。

于 2019-09-14T14:49:33.163 回答
0

这个有效!

floor(loge(n) / loge(2)) + 1

要包含负数,您可以添加一个额外的位来指定符号。

floor(loge(abs(n)) / loge(2)) + 2
于 2018-10-13T12:05:13.727 回答