计算存储十进制数所需的位

Question

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

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

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

例如，在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。

Answer 1

存储n整数(例如，0到n-1(所需的二进制位数的公式为：

log_e(n(/log_e2(

然后四舍五入。

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

对于0到n，请在上式中使用n+1(存在n+1整数(。

在您的计算器上，log_e可能只是标记为log或ln(自然对数(。

Answer 2

以b为基数的n数字可以表示的最大数字是bⁿ-1。因此，可以用N二进制数字表示的最大数字是2^N-1。我们需要最小的整数N，这样：

2^N-1≥b^N-1
⇒2^N≥b^N

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

log₂2^N≥log₂b^N
⇒N≥log₂b^N
⇒N≥log b^N/log 2

由于我们想要满足最后一个关系的最小整数N，所以要找到N、找到log b^N/log 2并取上限。

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

对于n=3：

N=？3/log₁₀2？=10

对于n=4：

N=？4/log₁₀2？=14

对于n=6：

N=？6/log₁₀2？=20

一般来说，对于n十进制数字：

N=？N/log₁₀2？

Answer 3

好的，用这种方式来概括表示一个数字需要多少位的技术。你有R个符号作为一个表示，你想知道有多少比特，求解这个方程R=2^n或log2(R(=n。其中n是比特数，R是表示的符号数。

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

Answer 4

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

1. 3位数字

我对这个问题的看法是：

• 我们需要存储的3位数的最大数目是多少？回答：999
• 存储这个数字所需的最小位数是多少

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

2^n = 999
nlog2 = log999
n ~ 10

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

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

希望这能有所帮助！

Answer 5

简单的答案是：

int nBits = ceil(log2(N));

这只是因为pow(2，nBits(略大于N。

Answer 6

继续将数字除以2，直到得到商0。

Answer 7

最简单的答案是将所需的值转换为二进制，并查看该值需要多少位。然而，问题是一个由X位组成的十进制数需要多少位。在这种情况下，您似乎必须选择具有X位数字的最高值，然后将该数字转换为二进制。

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

要将值转换为二进制值，请重复除以2，直到得到商0(所有余数都是0或1(。然后颠倒余数的顺序，得到二进制数。

Exampe:13到二进制。

• 13/2=6 r1
• 6/2=3 r0
• 3/2=1 r1
• 1/2=0 r1
• =1101((8*1(+(4*1(+

希望这能帮上忙。

让其所需的n位，然后是2^n=(基数(^位，然后取n的日志和计数号

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

拿一个你只想要三位数的箱子(你的箱子是1(。我们看到的要求是，

2^n-1>=999

将日志应用于两侧，

log(2^n-1(>=log(999(

log(2^n(-log(1(>=log(999(

n=9.964(近似值(。

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

这里有很多答案，但我将添加我的方法，因为我是在处理同一问题时发现这篇文章的。

从我们所知道的开始，是从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

那么，现在我们如何计算模式呢？

请记住，log base 2(n(=log base 10(n(/log base 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)

这个有效！

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

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

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

如上所述，荒诞派的简短(完美而精彩(答案是：

N=？N/log₁₀2？

更快的答案可能是：

N<(n×3402(»10+1

"»"代表向右的逐位移位，这是2的幂的除法，向下取整。

这个公式只需要整数运算，可以产生很好的结果，最多可以达到相当高的位数(超过1000，错误为0或+1(。它可以用于在解析器中分配缓冲区，因为错误总是正的。

解释：
首先将除法转化为乘法：

N=N/log₁₀2=N×(1/log₁₀2(

让我们乘以2的幂，然后选择一个整数上界：

n×(1/log₁₀2(×2¹⁰=n×3401654…<n×3402

然后除以2¹⁰：

n/log_{102<(n×3402(/2¹⁰
N<(n×3402(/2¹⁰}

最后用移位代替除法，加1取整。

n/log_{102<(n×3402(»10+1}

使用2的更高幂，可以轻松获得更好的精度。对于2¹⁶或2³²，您只需要丢弃较低的字节。但是你需要更大的整数。2⁸可能是嵌入计算的一个很好的近似值。