我正在寻找最有效的方法来计算存储整数所需的最小字节数而不会丢失精度.
e.g.
int: 10 = 1 byte
int: 257 = 2 bytes;
int: 18446744073709551615 (UINT64_MAX) = 8 bytes;
谢谢
PS这是一个哈希函数,将被调用数百万次
字节大小也不必是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位val的速度差异很小(但可测量).此外,我没有使用__builtin_clzl测试解决方案,这可以比较.
Tho*_*nin 29
用这个:
int n = 0;
while (x != 0) {
x >>= 8;
n ++;
}
这假定x包含您的(正)值.
请注意,零将被声明为可编码为无字节.此外,大多数可变大小的编码需要一些长度字段或终止符来知道编码在文件或流中停止的位置(通常,当您编码整数并考虑大小时,编码对象中有多个整数).
Tro*_*nic 20
if如果您只对常见尺寸感兴趣,则只需要两个简单的s.考虑这一点(假设您实际上有无符号值):
if (val < 0x10000) {
if (val < 0x100) // 8 bit
else // 16 bit
} else {
if (val < 0x100000000L) // 32 bit
else // 64 bit
}
如果您需要测试其他尺寸,选择中间点然后进行嵌套测试将在任何情况下保持测试数量非常低.但是,在这种情况下,使测试成为递归函数可能是更好的选择,以保持代码简单.一个不错的编译器将优化掉递归调用,以便生成的代码仍然一样快.
假设一个字节是8位,为了表示整数x,你需要[log2(x)/ 8] + 1个字节,其中[x] = floor(x).
好的,我现在看到字节大小不一定是2的幂.考虑字节大小b.公式仍为[log2(x)/ b] + 1.
现在,要计算日志,要么使用查找表(速度最快的方式),要么使用二进制搜索,这对于整数来说也非常快.
您可能首先获得最高位集,这与log2(N)相同,然后获取ceil所需的字节数(log2(N)/ 8).
这里有一些用于获取最高位集的位置,这些位置是从http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious复制的,您可以单击URL以获取有关这些算法的详细信息工作.
查找具有64位IEEE float的整数的整数对数基数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;
}
从最重要的一侧(clz或bsr)找到第一个'1'位的位置的函数通常是一个简单的CPU指令(不需要弄乱log 2),所以你可以将它除以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内在的.)
通过取数字的log 2来找到位数,然后除以8得到字节数.
您可以通过以下公式找到x的log n:
log n(x)= log(x)/ log(n)
由于你需要非常快速地完成这项工作,Bit Twiddling Hacks有几种快速计算log 2(x)的方法.查找表方法似乎适合您的需求.