logo标签列表

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

decimalunsignedunsigned-integer
28

考虑无符号整数表示。为了存储一个包含以下数字的十进制数，需要多少位：

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

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

实际上，无符号整数的范围是0到2^n-1，其中n为位数。 - rghome
@rghome 这个属性有名字吗？我觉得它很棒。 - Marwan
@Marwan，我不太确定你指的是哪个属性，但也许“指数”是你要找的词。 - rghome
我正在谈论的是“无符号整数的范围是n位时0到2^n - 1”。这里需要的比特数是log_2，这只是巧合吗？ - Marwan
也许我有点疯狂，算了吧。 - Marwan
13个回答
0

假设需要 n 位，则 2^n=(base)^digit，然后取对数并计算 n 的数量。

0

如上所述，ad absurdum 给出的简短（完美和出色）答案是：

N = ⌈n / log10 2⌉

一个更快的答案可能是：

N < ( n × 3402 ) » 10 + 1

"»" 表示向右位移，即除以 2 的幂，向下取整。

这个公式只需要整数运算，并且在相当高的数字范围内产生良好的结果（超过 1000 位，误差为 0 或 +1）。它可以用于在解析器中分配缓冲区，因为误差始终为正数。

说明：
首先将除法转化为乘法：

N = n / log10 2 = n × ( 1/log10 2 )

让我们乘以 2 的幂并选择一个整数上限：

n × ( 1/log10 2 ) × 210 = n × 3 401,654… < n × 3402

然后除以 210 :

n / log10 2 < ( n × 3402 ) / 210
N < ( n × 3402 ) / 210

最后用移位替换除法并加 1 进行四舍五入。

n/log10 2 < ( n × 3402 ) » 10 + 1

您可以使用更高的 2 的幂次方来获得更好的精度。使用 216 或 232 只需丢弃较低的字节即可。但是需要更大的整数字长。对于嵌入式计算，28 可能是一个很好的近似值。

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

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

记住：log2(n) = log10(n) / log10(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的幂次方数字。这些值在应用ceiling时不会改变，因此您知道需要添加1以获取最小位字段长度。

为了考虑特殊情况，请将输入加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)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接