정수에 필요한 바이트 수를 결정하는 방법은?
정수를 저장하는 데 필요한 최소 바이트 수를 정확도를 잃지 않고 계산할 수 있는 가장 효율적인 방법을 찾고 있습니다.
e.g.
int: 10 = 1 byte
int: 257 = 2 bytes;
int: 18446744073709551615 (UINT64_MAX) = 8 bytes;
감사해요.
추신: 이것은 수백만 번 호출될 해시 함수를 위한 것입니다.
또한 바이트 크기가 2의 거듭제곱일 필요는 없습니다.
가장 빠른 해결책은 다음과 같습니다.
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;
}
대부분 56비트 밸브를 사용한 속도 차이는 Thomas Pornin의 답변과 비교했을 때 미미했습니다(그러나 측정 가능했습니다.또한 비교 가능한 __builtin_clzl을 사용하여 솔루션을 테스트하지 않았습니다.
사용 방법:
int n = 0;
while (x != 0) {
x >>= 8;
n ++;
}
이는 다음과 같이 가정합니다.x사용자의 (양의) 값을 포함합니다.
0은 바이트가 전혀 없는 것으로 인코딩 가능한 것으로 선언됩니다.또한 대부분의 가변 크기 인코딩은 파일이나 스트림에서 인코딩이 멈추는 위치를 알기 위해 길이 필드나 터미네이터가 필요합니다(보통 정수를 인코딩하고 크기를 고려할 때 인코딩된 개체에 두 개 이상의 정수가 있습니다).
간단한 두 가지만 있으면 됩니다.if일반적인 크기에만 관심이 있는 경우.(실제로 서명되지 않은 값이 있다고 가정할 경우) 다음을 고려합니다.
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] + [x] = floor(x)인 1바이트가 필요합니다.
알겠습니다, 바이트 크기가 반드시 2의 거듭제곱이 아닌 것 같네요.바이트 크기 b를 고려합니다.공식은 여전히 [log2(x) / b] + 1입니다.
이제 로그를 계산하려면 룩업 테이블(속도별 최선의 방법)을 사용하거나 정수에 대해서도 매우 빠른 이진 검색을 사용합니다.
가장 중요한 면에서 첫 번째 '1' 비트의 위치를 찾는 기능 (clz아니면bsr)는 일반적으로 간단한 CPU 명령이므로(로그를2 건드릴 필요가 없으므로, 필요한 바이트 수를 얻으려면 이를 8로 나눌 수 있습니다.gcc에서는 다음과 같은 작업을 수행합니다.
#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에서는 intinsic을 사용합니다.)
먼저 log2(N)과 동일한 가장 높은 비트 세트를 얻은 다음 cheel(log2(N))에서 필요한 바이트를 얻을 수 있습니다.
다음은 http://graphics.stanford.edu/ ~seander/bithacks.html#IntegerLogObious에서 복사한 가장 높은 비트 집합의 위치를 얻기 위한 몇 가지 비트 해킹이며, 이러한 알고리즘의 작동 방식에 대한 자세한 내용은 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;
}
숫자의 로그를2 취하여 비트 수를 구한 후 8로 나누어 바이트 수를 구합니다.
x의 로그는n 다음과 같은 공식으로 구할 수 있습니다.
log(x) = log(x) / log(n)
업데이트:
이것을 정말 빨리 해야 하기 때문에, 비트 트위들링 핵스는 로그2(x)를 빠르게 계산할 수 있는 몇 가지 방법이 있습니다.룩업 테이블 접근법이 당신의 요구에 맞을 것 같습니다.
이렇게 하면 바이트 수가 나옵니다.그것이 엄밀하게 가장 효율적인 것은 아니지만, 적혈구에 포함된 에너지로 작동하는 나노봇을 프로그래밍하지 않는 한, 그것은 문제가 되지 않을 것입니다.
int count = 0;
while (numbertotest > 0)
{
numbertotest >>= 8;
count++;
}
배열 크기에 필요한 경우 컴파일 시 템플릿 메타 프로그래밍 코드를 작성하여 파악할 수 있습니다.
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
참고: 이것이 원래 질문에 대답하는 것이 아니라는 것을 알고 있지만, 이 페이지에 착륙할 때 사람들이 검색할 관련 질문에 대답합니다.
바닥((log2(N)) / 8) + 1) 바이트
로그 함수가 정확히 필요합니다.
nb_bytes = floor(log(x)/log(256))+1 만약 log2를 사용한다면, log2(256) == 8이므로
바닥(log2(x)/8)+1
결과값이 자신의 값보다 커질 때까지 256개의 거듭제곱값을 올려야 합니다.
예: (C#에서 테스트됨)
long long limit = 1;
int byteCount;
for (byteCount = 1; byteCount < 8; byteCount++) {
limit *= 256;
if (limit > value)
break;
}
바이트 크기만 2의 거듭제곱(65,537이 3을 반환하지 않으려면)으로 바꾸기byteCount++와 함께byteCount *= 2.
이것은 간단한 공식을 휴대용으로 구현한 것이라고 생각합니다.
#include <limits.h>
#include <math.h>
#include <stdio.h>
int main(void) {
int i;
unsigned int values[] = {10, 257, 67898, 140000, INT_MAX, INT_MIN};
for ( i = 0; i < sizeof(values)/sizeof(values[0]); ++i) {
printf("%d needs %.0f bytes\n",
values[i],
1.0 + floor(log(values[i]) / (M_LN2 * CHAR_BIT))
);
}
return 0;
}
출력:
10개 필요 1바이트257 2바이트 필요67898은 3바이트가 필요합니다.1,40000은 3바이트가 필요합니다.2147483647 4바이트 필요-2147483648 4바이트 필요
속도의 부족과 부동 소수점 라이브러리를 연결할 필요성 여부 및 정도는 필요에 따라 달라집니다.
나는 이 질문이 이런 유형의 답을 요구하지 않았다는 것을 알고 있지만, 가장 적은 수의 문자를 사용하여 해결책을 찾는 사람들의 경우, 이것은 길이 변수의 선언을 포함하여 17자 또는 25자의 길이 변수에 할당합니다.
//Assuming v is the value that is being counted...
int l=0;
for(;v>>l*8;l++);
이것은 점프, 가지 등이 포함되지 않은 솔루션을 만드는 SoapBox의 아이디어에 기반을 두고 있습니다.불행하게도 그의 해결책은 정확하지 않았습니다.저는 스피릿을 채택했고 여기 32비트 버전이 있습니다. 64비트 체크는 원한다면 쉽게 적용할 수 있습니다.
함수는 지정된 정수를 저장하는 데 필요한 바이트 수를 반환합니다.
unsigned short getBytesNeeded(unsigned int value)
{
unsigned short c = 0; // 0 => size 1
c |= !!(value & 0xFF00); // 1 => size 2
c |= (!!(value & 0xFF0000)) << 1; // 2 => size 3
c |= (!!(value & 0xFF000000)) << 2; // 4 => size 4
static const int size_table[] = { 1, 2, 3, 3, 4, 4, 4, 4 };
return size_table[c];
}
각각 8번씩 int 8비트를 오른쪽으로 이동하고 아직도 있는지 확인합니다.1비트가 남습니다.중지하기 전에 이동하는 횟수는 필요한 바이트 수입니다.
간단히 말해, 필요한 최소 바이트 수는ceil(min_bits/8),어디에min_bits인덱스 입니다.(i+1)가장 높은 비트의
이를 위한 다양한 방법이 있습니다.
옵션 1번.
int numBytes = 0;
do {
numBytes++;
} while (i >>= 8);
return (numBytes);
위의 예에서 는 테스트하려는 숫자이며, 일반적으로 프로세서, 정수 크기에 상관없이 사용할 수 있습니다.
하지만, 그것은 가장 빠르지 않을 수도 있습니다.또는 일련의 if 문을 시도해 볼 수 있습니다.
32비트 정수의 경우
if ((upper = (value >> 16)) == 0) {
/* Bit in lower 16 bits may be set. */
if ((high = (value >> 8)) == 0) {
return (1);
}
return (2);
}
/* Bit in upper 16 bits is set */
if ((high = (upper >> 8)) == 0) {
return (3);
}
return (4);
64비트 정수의 경우 if 문의 다른 수준이 필요합니다.
이 루틴의 속도가 당신이 말하는 것처럼 중요하다면, 함수 호출로 원한다면 어셈블러에서 이 작업을 수행하는 것이 가치가 있을 수 있습니다.이를 통해 스택 프레임을 생성하거나 파괴하는 것을 방지할 수 있으며, 중요한 경우 몇 번의 추가 클럭 주기를 절약할 수 있습니다.
조금 기본적이지만 출력이 제한적이기 때문에 중단점을 미리 계산하고 case statement를 사용할 수는 없나요?런타임에 계산할 필요가 없고 비교 횟수가 제한됩니다.
32비트 해시만 사용하면 어떨까요?
그것은 어디에서나 거의 최고 속도로 작동할 것입니다.
왜 큰 해시가 필요한지에 대해 저는 다소 혼란스럽습니다.4바이트 해시가 작동한다면 항상 사용하는 것이 어떨까요?암호화 사용을 제외하고, 어쨌든 버킷이 2개32 이상인 해시 테이블을 가진 사람은 누구입니까?
숀 앤더슨의 "비트 트위들링 핵스" 페이지에는 이런 것들을 위한 훌륭한 요리법들이 많이 있습니다.
이 코드에는 분기가 0개이므로 일부 시스템에서는 더 빠를 수 있습니다.또한 일부 시스템(GPGPU)에서는 동일한 워프의 스레드에서 동일한 명령을 실행하는 것이 중요합니다.이 코드는 입력 값에 상관없이 항상 동일한 명령 수이다.
inline int get_num_bytes(unsigned long long value) // where unsigned long long is the largest integer value on this platform
{
int size = 1; // starts at 1 sot that 0 will return 1 byte
size += !!(value & 0xFF00);
size += !!(value & 0xFFFF0000);
if (sizeof(unsigned long long) > 4) // every sane compiler will optimize this out
{
size += !!(value & 0xFFFFFFFF00000000ull);
if (sizeof(unsigned long long) > 8)
{
size += !!(value & 0xFFFFFFFFFFFFFFFF0000000000000000ull);
}
}
static const int size_table[] = { 1, 2, 4, 8, 16 };
return size_table[size];
}
g++ -O3는 다음을 생성합니다(iff가 최적화되었는지 확인).
xor %edx,%edx
test $0xff00,%edi
setne %dl
xor %eax,%eax
test $0xffff0000,%edi
setne %al
lea 0x1(%rdx,%rax,1),%eax
movabs $0xffffffff00000000,%rdx
test %rdx,%rdi
setne %dl
lea (%rdx,%rax,1),%rax
and $0xf,%eax
mov _ZZ13get_num_bytesyE10size_table(,%rax,4),%eax
retq
왜 이렇게 복잡해요?제가 생각해낸 것은 다음과 같습니다.
bytesNeeded = (numBits/8)+((numBits%8) != 0);
기본적으로numBits나머지가 있으면 8 + 1로 나눕니다.
여기에는 이미 많은 답이 있지만, 만약 당신이 숫자를 미리 안다면, c++에서 당신은 a를 사용할 수 있습니다.template프리프로세서를 사용할 수 있습니다.
template <unsigned long long N>
struct RequiredBytes {
enum : int { value = 1 + (N > 255 ? RequiredBits<(N >> 8)>::value : 0) };
};
template <>
struct RequiredBytes<0> {
enum : int { value = 1 };
};
const int REQUIRED_BYTES_18446744073709551615 = RequiredBytes<18446744073709551615>::value; // 8
또는 비트 버전의 경우:
template <unsigned long long N>
struct RequiredBits {
enum : int { value = 1 + RequiredBits<(N >> 1)>::value };
};
template <>
struct RequiredBits<1> {
enum : int { value = 1 };
};
template <>
struct RequiredBits<0> {
enum : int { value = 1 };
};
const int REQUIRED_BITS_42 = RequiredBits<42>::value; // 6
언급URL : https://stackoverflow.com/questions/2274428/how-to-determine-how-many-bytes-an-integer-needs
'programing' 카테고리의 다른 글
| C에서 EOF까지 스캔프를 어떻게 읽습니까? (0) | 2023.10.31 |
|---|---|
| 페이지 속도 인사이트 Google Retackcha에 사용되지 않는 자바스크립트 제거 (0) | 2023.10.31 |
| jquery - .done (),의 사용 .done () .다음으로 () 및 .ajax 요청을 지정된 순서로 수행하기 위한 () 시 (0) | 2023.10.31 |
| "JDBC 드라이버 인스턴스화 할 수 없음" 플라이웨이 명령줄 오류 수정 방법? (0) | 2023.10.31 |
| match_parent width가 RecyclerView에서 작동하지 않습니다. (0) | 2023.10.31 |