如何确定一个整数需要多少字节？

Question

我正在寻找最有效的方法来计算存储整数所需的最小字节数，同时不会失去精度。

e.g.

int: 10 = 1 byte
int: 257 = 2 bytes;
int: 18446744073709551615 (UINT64_MAX) = 8 bytes;

谢谢

顺便说一句，这是为了一个会被调用成百万次的哈希函数

字节大小也不必是2的幂次方

最快的解决方案似乎是基于tronics的答案：

    int bytes;
    if (hash <= UINT32_MAX) 
    {
        if (hash < 16777216U)
        {
            if (hash <= UINT16_MAX)
            {
                if (hash <= UINT8_MAX) bytes = 1;
                else bytes = 2;
            }
            else bytes = 3;
        }
        else bytes = 4;
    } 
    else if (hash <= UINT64_MAX) 
    {
        if (hash < 72057594000000000ULL) 
        {
            if (hash < 281474976710656ULL) 
            {
                if (hash < 1099511627776ULL) bytes = 5;
                else bytes = 6;
            }
            else bytes = 7;
        }
        else bytes = 8;
    }

与Thomas Pornin的答案相比，主要使用56位值的速度差异微小（但可测量）。我还没有测试使用__builtin_clzl的解决方案，这可能是可比较的。

- user75832

---

我认为__builtin_clzll会给你更好的性能，因为它最终只需要大约3个汇编指令而没有任何分支。即使在添加了对零的检查后，你最终也只有大约10个指令。 - D.Shawley

我测试了超过10次，每次都进行了1000万次调用__builtin_clzll函数，平均而言比普通方法慢了0.006秒。虽然差别很小，但由于它依赖于编译器，所以我认为Tronics的答案仍然是最好的。 - user75832

这个问题所引发的回答非常丰富多样，令人惊喜。 - Richard Szalay

Answer 1

请使用以下代码：

int n = 0;
while (x != 0) {
    x >>= 8;
    n ++;
}

假设x包含您的（正）值。

请注意，零将被声明为根本没有任何字节可编码。此外，大多数变长编码需要某些长度字段或终止符才能确定文件或流中编码何时停止（通常，在编码整数并关注大小时，编码对象中有多个整数）。

- Thomas Pornin

---

即使这可能不是最快的解决方案（但对于小值来说非常快），但简单的解决方案会得到+1（因此总体上可能是最快的解决方案）。 - Tronic

@Tronic：这个解决方案是否比你的二分搜索更快，取决于输入数据的模式。我认为需要一个非常特定的设置才能展示出实际可测量的性能差异。我的代码具有自动处理“较长类型”的轻微优势（例如，在开发具有128位类型的新C编译器时无需更改任何内容）。 - Thomas Pornin

如果您想让0返回1个字节，可以使用int n = 0; do { x >>= 8; n++; } while(x);。 - Chris Lutz

Answer 2

如果您只对常见的大小感兴趣，那么只需要两个简单的if语句。考虑以下代码（假设您实际上具有无符号值）：

if (val < 0x10000) {
    if (val < 0x100) // 8 bit
    else // 16 bit
} else {
    if (val < 0x100000000L) // 32 bit
    else // 64 bit
}

如果需要测试其他大小，选择一个中间点然后进行嵌套测试将在任何情况下都可以保持测试的数量非常低。但是，在这种情况下，将测试作为递归函数可能是更好的选择，以保持代码简单。一个不错的编译器将优化递归调用，使得结果代码仍然像原来一样快速。

- Tronic

---

但是如果我们有256位的整数呢？！ ;) - Earlz

如果考虑到分支预测错误的惩罚，它将不会运行得很快。 - ZelluX

这个方法可能不如使用日志那么美观，但它可以更快地完成工作。 - Spencer Ruport

如果他需要任意数量的字节，那么这并不是非常有用的。 - Peter Alexander

不错。二叉树搜索在这个解决方案中会很好用 :) - Russell

Answer 3

你可以先获取最高位设置，这与log2（N）相同，然后通过ceil（log2（N）/8）获取所需的字节数。

下面是一些用于获取最高位设置位置的位操作技巧，这些技巧摘自http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious，你可以点击URL了解这些算法的详细工作原理。

使用64位IEEE浮点数查找整数的对数基数2

int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

使用查找表查找整数的对数（以2为底）

static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

在O(lg(N))次操作内找到一个N位整数的以2为底的对数

unsigned int v;  // 32-bit value to find the log2 of 
const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
const unsigned int S[] = {1, 2, 4, 8, 16};
int i;

register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
  if (v & b[i])
  {
    v >>= S[i];
    r |= S[i];
  } 
}


// OR (IF YOUR CPU BRANCHES SLOWLY):

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);


// OR (IF YOU KNOW v IS A POWER OF 2):

unsigned int v;  // 32-bit value to find the log2 of 
static const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 
                                 0xFF00FF00, 0xFFFF0000};
register unsigned int r = (v & b[0]) != 0;
for (i = 4; i > 0; i--) // unroll for speed...
{
  r |= ((v & b[i]) != 0) << i;
}

- ZelluX

---

Ceil(Log256(N))更简单。 - IamIC

Ciel(log2(N + 1) / 8) 更加准确。插入256：你想要得到>1，而不是1。 - Mad Physicist

我在开头提到了对数方法。然而，从性能角度来看，计算log()比位运算要复杂得多。 - ZelluX

Answer 4

从最高位开始查找第一个'1'位的函数（clz或bsr）通常是一条简单的CPU指令（无需操作log₂），因此您可以将其除以8以获取所需字节数。在gcc中，有__builtin_clz来完成这项任务：

#include <limits.h>
int bytes_needed(unsigned long long x) {
   int bits_needed = sizeof(x)*CHAR_BIT - __builtin_clzll(x);
   if (bits_needed == 0)
      return 1;
   else
      return (bits_needed + 7) / 8;
}

（在 MSVC 中，您可以使用 _BitScanReverse 内置函数。）

- kennytm

---

如果可用C++20，则第一行可以替换为：int bits_needed = std::bit_width(x); - randag

Answer 5

假设一个字节是8位，为了表示一个整数x，你需要[log2(x) / 8] + 1个字节，其中[x] = floor(x)。

好的，我现在明白字节大小不一定是2的幂。考虑字节大小b。公式仍然是[log2(x) / b] + 1。

现在，要计算对数，可以使用查找表（速度最快的方法）或使用二分查找，对于整数也非常快速。

- IVlad

---

是的，但与其他方法相比，计算对数将会非常缓慢。 - SLaks

log2是一个浮点函数，因此容易受到令人讨厌的舍入误差的影响。此外，我估计这个解决方案比我的慢得多（但我没有进行基准测试，所以请谨慎对待）。 - Tronic

没错，你不应该按照这个实现。这只是公式，你可能想通过二分查找和位运算或者某种查找表来计算对数。Tronic：没错，像你发布的那样做会更快，但需要更多条件。 - IVlad

你正在寻找Ceil(Log256(n))。 - IamIC

@SLaks 是的，但现代CPU对于对数运算非常快，并且这只是一行没有分支的小代码。它可以被内联，使其更快。 - IamIC

Answer 6

通过取对数₂并将其除以8，以获取字节数，从而找到位数。

您可以使用以下公式找到x的log_n:

log_n(x) = log(x) / log(n)

更新:

由于您需要快速完成此操作，Bit Twiddling Hacks提供了几种快速计算log₂(x)的方法。 查找表法似乎适合您的需求。

- Bill the Lizard

Answer 7

这会给你字节数。虽然不是最高效的方法，但除非你在编程一个由红细胞内含能量驱动的纳米机器人，否则这并不重要。

int count = 0;
while (numbertotest > 0)
{
  numbertotest >>= 8;
  count++;
}

- Ben Collins

Answer 8

如果你需要用于数组大小的代码，你可以编写一些小的模板元编程代码来在编译时计算它：

template<unsigned long long N> struct NBytes
{ static const size_t value = NBytes<N/256>::value+1; };
template<> struct NBytes<0> 
{ static const size_t value = 0; };

int main()
{
    std::cout << "short = " << NBytes<SHRT_MAX>::value << " bytes\n";
    std::cout << "int = " << NBytes<INT_MAX>::value << " bytes\n";
    std::cout << "long long = " << NBytes<ULLONG_MAX>::value << " bytes\n";
    std::cout << "10 = " << NBytes<10>::value << " bytes\n";
    std::cout << "257 = " << NBytes<257>::value << " bytes\n";
    return 0;
}

输出：

short = 2 bytes
int = 4 bytes
long long = 8 bytes
10 = 1 bytes
257 = 2 bytes

注意：我知道这并不是回答原问题，但它回答了一个相关的问题，当人们访问这个页面时会搜索到它。

- Matt Price

---

很遗憾，这不能在编译时完成，但是这是一个有趣的解决方案。谢谢。 - user75832

Answer 9

您需要将256不断提升到连续的幂，直到结果大于您的值。

例如：（在C#中测试）

long long limit = 1;
int byteCount;

for (byteCount = 1; byteCount < 8; byteCount++) {
    limit *= 256;
    if (limit > value)
        break;
}

如果您只希望字节大小是二的幂次方（如果您不希望 65,537 返回 3），请将 byteCount++ 替换为 byteCount *= 2。

- SLaks

---

@Mitch：log 不是简单的算术运算，他需要最佳性能。 - SLaks

以2为底的对数在二进制处理器上非常简单和快速；许多处理器都有直接计算它的指令，例如x86上的BSR。几乎所有的C编译器也都有这个操作的内置函数。唯一令人困惑的是它们都有不同的名称。有几个答案可以充分解决这个问题并提供一个好的解决方案，但这些基于循环的解决方案会让我这种注重性能的人感到头痛。与其他情况不同的是，在直观的代码和优化的代码之间可能存在可读性的争议，而ceil(log2(val) / 8)则非常明显。 - Cody Gray

Answer 10

需要占用 (log2(N) / 8) + 1 个字节的空间。

- Mitch Wheat