C의 정수 자릿수를 판별하려면 어떻게 해야 하나요?
예를 들어.
n = 3432, result 4
n = 45, result 2
n = 33215, result 5
n = -357, result 3
그냥 끈으로 바꿔서 끈의 길이를 알 수 있을 것 같은데, 그건 복잡해 보여.
재귀적 접근법:-)
int numPlaces (int n) {
if (n < 0) return numPlaces ((n == INT_MIN) ? INT_MAX: -n);
if (n < 10) return 1;
return 1 + numPlaces (n / 10);
}
또는 반복:
int numPlaces (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX: -n;
while (n > 9) {
n /= 10;
r++;
}
return r;
}
또는 원시 속도:
int numPlaces (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n < 10) return 1;
if (n < 100) return 2;
if (n < 1000) return 3;
if (n < 10000) return 4;
if (n < 100000) return 5;
if (n < 1000000) return 6;
if (n < 10000000) return 7;
if (n < 100000000) return 8;
if (n < 1000000000) return 9;
/* 2147483647 is 2^31-1 - add more ifs as needed
and adjust this final return as well. */
return 10;
}
위의 항목은 MINT를 더 잘 처리하도록 수정되었습니다. 정수에 대한 합리적인n 2 2 2의 보완 규칙을 따르지 않는 이상한 시스템에서는 추가 조정이 필요할 수 있습니다.
원시 속도 버전은 실제로 부동 소수점 버전보다 성능이 우수합니다.
int numPlaces (int n) {
if (n == 0) return 1;
return floor (log10 (abs (n))) + 1;
}
1억 번의 반복을 통해 다음과 같은 결과를 얻을 수 있습니다.
Raw speed with 0: 0 seconds
Raw speed with 2^31-1: 1 second
Iterative with 2^31-1: 5 seconds
Recursive with 2^31-1: 6 seconds
Floating point with 1: 6 seconds
Floating point with 2^31-1: 7 seconds
사실 조금 놀랐습니다.인텔 칩의 FPU는 괜찮은 것 같았지만, 일반적인 FP 운영은 아직 손으로 최적화된 정수 코드와는 비교가 되지 않는 것 같습니다.
스톰소울의 제안에 따라 업데이트:
스톰소울을 사용하여 멀티피터 솔루션을 테스트하면 4초의 시간이 주어지므로 분할피터 솔루션보다 훨씬 빠르지만 최적화된 if-statement 솔루션과 일치하지 않습니다.
랜덤으로 생성된 1000개의 숫자 풀에서 인수를 선택하면 원시 속도 타임아웃이 2초로 단축됩니다.따라서 매번 같은 인수를 갖는 것은 장점이 있는 것처럼 보이지만 그래도 리스트에서 가장 빠른 접근법입니다.
-O2로 컴파일하면 속도는 향상되지만 상대 위치는 개선되지 않았습니다(반복 횟수를 10배 증가시켜 확인했습니다).
더 이상의 분석은 CPU 효율의 내부 작업(다른 유형의 최적화, 캐시 사용, 분기 예측, 실제로 보유하고 있는 CPU, 실내 환경 온도 등)에 대해 진지하게 검토해야 합니다. 이 작업은 유료 작업에 방해가 됩니다.이는 흥미로운 전환이지만, 어느 순간 최적화를 위한 투자 수익률이 너무 낮아져 문제가 되지 않습니다.질문에 답할 수 있는 충분한 해결책을 가지고 있다고 생각합니다(결국 속도에 관한 것은 아닙니다).
추가 업데이트:
아키텍처에 의존하지 않는 명백한 오류를 제외하고 이 답변에 대한 최종 업데이트가 될 것입니다.스톰소울의 용기 있는 측정 노력에 영감을 받아 스톰소울의 자체 테스트 프로그램에 따라 수정된 테스트 프로그램 및 답변에 나와 있는 모든 방법의 샘플 수치를 게시합니다.이것은 특정 머신에 탑재되어 있는 것입니다.어디서 주행하느냐에 따라 주행거리가 달라질 수 있습니다(그 때문에 테스트 코드를 게시합니다).
원하는 대로 할 수 있습니다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#define numof(a) (sizeof(a) / sizeof(a[0]))
/* Random numbers and accuracy checks. */
static int rndnum[10000];
static int rt[numof(rndnum)];
/* All digit counting functions here. */
static int count_recur (int n) {
if (n < 0) return count_recur ((n == INT_MIN) ? INT_MAX : -n);
if (n < 10) return 1;
return 1 + count_recur (n / 10);
}
static int count_diviter (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
while (n > 9) {
n /= 10;
r++;
}
return r;
}
static int count_multiter (int n) {
unsigned int num = abs(n);
unsigned int x, i;
for (x=10, i=1; ; x*=10, i++) {
if (num < x)
return i;
if (x > INT_MAX/10)
return i+1;
}
}
static int count_ifs (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n < 10) return 1;
if (n < 100) return 2;
if (n < 1000) return 3;
if (n < 10000) return 4;
if (n < 100000) return 5;
if (n < 1000000) return 6;
if (n < 10000000) return 7;
if (n < 100000000) return 8;
if (n < 1000000000) return 9;
/* 2147483647 is 2^31-1 - add more ifs as needed
and adjust this final return as well. */
return 10;
}
static int count_revifs (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n > 999999999) return 10;
if (n > 99999999) return 9;
if (n > 9999999) return 8;
if (n > 999999) return 7;
if (n > 99999) return 6;
if (n > 9999) return 5;
if (n > 999) return 4;
if (n > 99) return 3;
if (n > 9) return 2;
return 1;
}
static int count_log10 (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n == 0) return 1;
return floor (log10 (n)) + 1;
}
static int count_bchop (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n >= 100000000) {
r += 8;
n /= 100000000;
}
if (n >= 10000) {
r += 4;
n /= 10000;
}
if (n >= 100) {
r += 2;
n /= 100;
}
if (n >= 10)
r++;
return r;
}
/* Structure to control calling of functions. */
typedef struct {
int (*fnptr)(int);
char *desc;
} tFn;
static tFn fn[] = {
NULL, NULL,
count_recur, " recursive",
count_diviter, " divide-iterative",
count_multiter, " multiply-iterative",
count_ifs, " if-statements",
count_revifs, "reverse-if-statements",
count_log10, " log-10",
count_bchop, " binary chop",
};
static clock_t clk[numof (fn)];
int main (int c, char *v[]) {
int i, j, k, r;
int s = 1;
/* Test code:
printf ("%11d %d\n", INT_MIN, count_recur(INT_MIN));
for (i = -1000000000; i != 0; i /= 10)
printf ("%11d %d\n", i, count_recur(i));
printf ("%11d %d\n", 0, count_recur(0));
for (i = 1; i != 1000000000; i *= 10)
printf ("%11d %d\n", i, count_recur(i));
printf ("%11d %d\n", 1000000000, count_recur(1000000000));
printf ("%11d %d\n", INT_MAX, count_recur(INT_MAX));
/* */
/* Randomize and create random pool of numbers. */
srand (time (NULL));
for (j = 0; j < numof (rndnum); j++) {
rndnum[j] = s * rand();
s = -s;
}
rndnum[0] = INT_MAX;
rndnum[1] = INT_MIN;
/* For testing. */
for (k = 0; k < numof (rndnum); k++) {
rt[k] = (fn[1].fnptr)(rndnum[k]);
}
/* Test each of the functions in turn. */
clk[0] = clock();
for (i = 1; i < numof (fn); i++) {
for (j = 0; j < 10000; j++) {
for (k = 0; k < numof (rndnum); k++) {
r = (fn[i].fnptr)(rndnum[k]);
/* Test code:
if (r != rt[k]) {
printf ("Mismatch error [%s] %d %d %d %d\n",
fn[i].desc, k, rndnum[k], rt[k], r);
return 1;
}
/* */
}
}
clk[i] = clock();
}
/* Print out results. */
for (i = 1; i < numof (fn); i++) {
printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));
}
return 0;
}
컴파일하려면 올바른 명령줄을 사용해야 합니다.특히, 당신은 얻기 위해 수학 라이브러리를 명시적으로 나열할 필요가 있을 수 있습니다.
log10()아래에서 는 '데비안'입니다.gcc -o testprog testprog.c -lm.
그리고, 그 결과에 대해서는, 이하와 같이 환경 대응의 리더 보드를 소개합니다.
최적화 수준 0:
Time for reverse-if-statements: 1704
Time for if-statements: 2296
Time for binary chop: 2515
Time for multiply-iterative: 5141
Time for divide-iterative: 7375
Time for recursive: 10469
Time for log-10: 26953
최적화 레벨 3:
Time for if-statements: 1047
Time for binary chop: 1156
Time for reverse-if-statements: 1500
Time for multiply-iterative: 2937
Time for divide-iterative: 5391
Time for recursive: 8875
Time for log-10: 25438
floor (log10 (abs (x))) + 1
http://en.wikipedia.org/wiki/Logarithm
다음은 Kendall Willets에 의한 십진수 자릿수를 계산하는 매우 빠른 방법입니다.
int count_digits(uint32_t n) {
#ifndef __has_builtin
# define __has_builtin(x) 0
#endif
#if __has_builtin(__builtin_clz)
// This increments the upper 32 bits (log10(T) - 1) when >= T is added.
# define K(T) (((sizeof(#T) - 1ull) << 32) - T)
static const uint64_t table[] = {
K(0), K(0), K(0), // 8
K(10), K(10), K(10), // 64
K(100), K(100), K(100), // 512
K(1000), K(1000), K(1000), // 4096
K(10000), K(10000), K(10000), // 32k
K(100000), K(100000), K(100000), // 256k
K(1000000), K(1000000), K(1000000), // 2048k
K(10000000), K(10000000), K(10000000), // 16M
K(100000000), K(100000000), K(100000000), // 128M
K(1000000000), K(1000000000), K(1000000000), // 1024M
K(1000000000), K(1000000000) // 4B
};
return (n + table[__builtin_clz(n | 1) ^ 31]) >> 32u;
#else
int count = 1;
for (;;) {
if (n < 10) return count;
if (n < 100) return count + 1;
if (n < 1000) return count + 2;
if (n < 10000) return count + 3;
n /= 10000u;
count += 4;
}
return count;
#endif
}
패스트 패스는 GCC와 clang 중 어느 것을 사용할 수 있는지에 의존합니다만, 폴백이 적절히 기능하고 있습니다.count_digits완전히 휴대할 수 있습니다.
그러면 매우 효율적인 코드(godbolt)가 생성됩니다.
count_digits(unsigned int):
mov edx, edi
mov eax, edi
or edx, 1
bsr edx, edx
movsx rdx, edx
add rax, QWORD PTR count_digits(unsigned int)::table[0+rdx*8]
shr rax, 32
ret
x86 어셈블리 및 조회 테이블을 사용하는 고정 비용 버전:
int count_bsr(int i) {
struct {
int max;
int count;
} static digits[32] = {
{ 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 },
{ 99, 2 }, { 99, 2 }, { 99, 2 },
{ 999, 3 }, { 999, 3 }, { 999, 3 },
{ 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 },
{ 99999, 5 }, { 99999, 5 }, { 99999, 5 },
{ 999999, 6 }, { 999999, 6 }, { 999999, 6 },
{ 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 },
{ 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 },
{ 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 },
{ INT_MAX, 10 }, { INT_MAX, 10 }
};
register const int z = 0;
register unsigned log2;
if (i < 0) i = -i;
__asm__ __volatile__ (
"bsr %1, %0;" \
"cmovz %2, %0;"\
: "=r" (log2) \
: "rm" (i), "r"(z));
return digits[log2].count + ( i > digits[log2].max );
}
다른 하나는 더 작은 룩업 테이블과 여기서 가져온 로그 10 근사치입니다.
int count_bsr2( int i ) {
static const unsigned limits[] =
{0, 10, 100, 1000, 10000, 100000,
1000000, 10000000, 100000000, 1000000000};
register const int z = 0;
register int l, log2;
if (i < 0) i = -i;
__asm__ __volatile__ (
"bsr %1, %0;" \
"cmovz %2, %0;"\
: "=r" (log2) \
: "rm" (i), "r"(z));
l = (log2 + 1) * 1233 >> 12;
return (l + ((unsigned)i >= limits[l]));
}
둘 다 x86 -INT_MIN이 INT_MIN과 같다는 사실을 이용합니다.
업데이트:
여기에 제시된 바와 같이 count_bsr 및 64비트 전용 count_bsr_mod 루틴에 대한 타이밍은 랜덤 부호 분포로 세트를 생성하도록 수정된 매우 멋진 팍스디아블로 테스트 프로그램을 사용하여 바이너리 검색 및 바이너리 찹 알고와 비교하여 약간 빠른 것입니다.테스트는 "-O3 -falign-timeout=16 -falign-timeout=16 -march=corei7-avx" 옵션을 사용하여 gcc 4.9.2로 구축되었으며 터보 및 sleep 상태가 꺼진 상태에서 정지 상태였던 Sandy Bridge 시스템에서 수행되었습니다.
bsr mod 시간: 270000bsr 시간: 340000바이너리 셧다운 시간: 800000바이너리 검색 시간: 7700바이너리 검색 모드 시간: 470000
테스트 소스,
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#define numof(a) (sizeof(a) / sizeof(a[0]))
/* Random numbers and accuracy checks. */
static int rndnum[10000];
static int rt[numof(rndnum)];
/* All digit counting functions here. */
static int count_bchop (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n >= 100000000) {
r += 8;
n /= 100000000;
}
if (n >= 10000) {
r += 4;
n /= 10000;
}
if (n >= 100) {
r += 2;
n /= 100;
}
if (n >= 10)
r++;
return r;
}
static int count_bsearch(int i)
{
if (i < 0)
{
if (i == INT_MIN)
return 11; // special case for -2^31 because 2^31 can't fit in a two's complement 32-bit integer
i = -i;
}
if (i < 100000) {
if (i < 1000) {
if (i < 10) return 1;
else if (i < 100) return 2;
else return 3;
} else {
if (i < 10000) return 4;
else return 5;
}
} else {
if (i < 10000000) {
if (i < 1000000) return 6;
else return 7;
} else {
if (i < 100000000) return 8;
else if (i < 1000000000) return 9;
else return 10;
}
}
}
// Integer log base 10, modified binary search.
static int count_bsearch_mod(int i) {
unsigned x = (i >= 0) ? i : -i;
if (x > 99)
if (x > 999999)
if (x > 99999999)
return 9 + (x > 999999999);
else
return 7 + (x > 9999999);
else
if (x > 9999)
return 5 + (x > 99999);
else
return 3 + (x > 999);
else
return 1 + (x > 9);
}
static int count_bsr_mod(int i) {
struct {
int m_count;
int m_threshold;
} static digits[32] =
{
{ 1, 9 }, { 1, 9 }, { 1, 9 }, { 1, 9 },
{ 2, 99 }, { 2, 99 }, { 2, 99 },
{ 3, 999 }, { 3, 999 }, { 3, 999 },
{ 4, 9999 }, { 4, 9999 }, { 4, 9999 }, { 4, 9999 },
{ 5, 99999 }, { 5, 99999 }, { 5, 99999 },
{ 6, 999999 }, { 6, 999999 }, { 6, 999999 },
{ 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 },
{ 8, 99999999 }, { 8, 99999999 }, { 8, 99999999 },
{ 9, 999999999 }, { 9, 999999999 }, { 9, 999999999 },
{ 10, INT_MAX }, { 10, INT_MAX }
};
__asm__ __volatile__ (
"cdq \n\t"
"xorl %%edx, %0 \n\t"
"subl %%edx, %0 \n\t"
"movl %0, %%edx \n\t"
"bsrl %0, %0 \n\t"
"shlq $32, %%rdx \n\t"
"movq %P1(,%q0,8), %q0 \n\t"
"cmpq %q0, %%rdx \n\t"
"setg %%dl \n\t"
"addl %%edx, %0 \n\t"
: "+a"(i)
: "i"(digits)
: "rdx", "cc"
);
return i;
}
static int count_bsr(int i) {
struct {
int max;
int count;
} static digits[32] = {
{ 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 },
{ 99, 2 }, { 99, 2 }, { 99, 2 },
{ 999, 3 }, { 999, 3 }, { 999, 3 },
{ 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 },
{ 99999, 5 }, { 99999, 5 }, { 99999, 5 },
{ 999999, 6 }, { 999999, 6 }, { 999999, 6 },
{ 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 },
{ 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 },
{ 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 },
{ INT_MAX, 10 }, { INT_MAX, 10 }
};
register const int z = 0;
register unsigned log2;
if (i < 0) i = -i;
__asm__ __volatile__ (
"bsr %1, %0;" \
"cmovz %2, %0;"\
: "=r" (log2) \
: "rm" (i), "r"(z));
return digits[log2].count + ( i > digits[log2].max );
}
/* Structure to control calling of functions. */
typedef struct {
int (*fnptr)(int);
const char *desc;
} tFn;
static tFn fn[] = {
{ NULL, NULL },
{ count_bsr_mod, " bsr mod" },
{ count_bsr, " bsr" },
{ count_bchop, " binary chop" },
{ count_bsearch, " binary search" },
{ count_bsearch_mod," binary search mod"}
};
static clock_t clk[numof (fn)];
int main (int c, char *v[]) {
int i, j, k, r;
int s = 1;
/* Test code:
printf ("%11d %d\n", INT_MIN, count_bsearch(INT_MIN));
//for (i = -1000000000; i != 0; i /= 10)
for (i = -999999999; i != 0; i /= 10)
printf ("%11d %d\n", i, count_bsearch(i));
printf ("%11d %d\n", 0, count_bsearch(0));
for (i = 1; i != 1000000000; i *= 10)
printf ("%11d %d\n", i, count_bsearch(i));
printf ("%11d %d\n", 1000000000, count_bsearch(1000000000));
printf ("%11d %d\n", INT_MAX, count_bsearch(INT_MAX));
return 0;
/* */
/* Randomize and create random pool of numbers. */
int p, n;
p = n = 0;
srand (time (NULL));
for (j = 0; j < numof (rndnum); j++) {
rndnum[j] = ((rand() & 2) - 1) * rand();
}
rndnum[0] = INT_MAX;
rndnum[1] = INT_MIN;
/* For testing. */
for (k = 0; k < numof (rndnum); k++) {
rt[k] = (fn[1].fnptr)(rndnum[k]);
}
/* Test each of the functions in turn. */
clk[0] = clock();
for (i = 1; i < numof (fn); i++) {
for (j = 0; j < 10000; j++) {
for (k = 0; k < numof (rndnum); k++) {
r = (fn[i].fnptr)(rndnum[k]);
/* Test code:
if (r != rt[k]) {
printf ("Mismatch error [%s] %d %d %d %d\n",
fn[i].desc, k, rndnum[k], rt[k], r);
return 1;
}
/* */
}
}
clk[i] = clock();
}
/* Print out results. */
for (i = 1; i < numof (fn); i++) {
printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));
}
return 0;
}
응답: " " " " 。snprintf(0,0,"%+d",n)-1
결과가 0이 될 때까지 루프에서 10으로 나눕니다.반복 횟수는 소수 자릿수에 해당합니다.
0 의 값으로 0 자리수를 얻을 것으로 상정하고 있습니다.
int countDigits( int value )
{
int result = 0;
while( value != 0 ) {
value /= 10;
result++;
}
return result;
}
if (x == MININT) return 10; // abs(MININT) is not defined
x = abs (x);
if (x<10) return 1;
if (x<100) return 2;
if (x<1000) return 3;
if (x<10000) return 4;
if (x<100000) return 5;
if (x<1000000) return 6;
if (x<10000000) return 7;
if (x<100000000) return 8;
if (x<1000000000) return 9;
return 10; //max len for 32-bit integers
매우 품위 없다.하지만 다른 모든 솔루션보다 빠릅니다.정수 분할 로그와 FP 로그는 비용이 많이 듭니다.퍼포먼스가 문제가 되지 않는다면 log 10 솔루션이 마음에 듭니다.
다음은 나눗셈이나 곱셈을 사용하지 않고 전개된 바이너리 검색입니다.주어진 숫자의 분포에 따라 if 스테이트먼트가 언롤된 다른 스테이트먼트보다 우선할 수도 있고 그렇지 않을 수도 있지만 항상 루프와 곱셈/division/log10을 사용하는 스테이트먼트를 우선할 수도 있습니다.
전체 범위를 아우르는 균일한 난수 분포를 통해 내 기계에서는 paxdiablo의 count_bchop() 실행 시간의 평균 79%, count_ifs()의 평균 88%, count_revifs()의 97%를 차지했다.
지수 분포에서는(n자리 숫자의 확률은 m자리 숫자의 숫자와 같습니다).여기서 m m n) count_ifs()와 count_revifs()는 모두 내 함수보다 우선합니다.지금으로서는 왜 그랬는지 모르겠다.
int count_bsearch(int i)
{
if (i < 0)
{
if (i == INT_MIN)
return 10; // special case for -2^31 because 2^31 can't fit in a two's complement 32-bit integer
i = -i;
}
if (i < 100000) {
if (i < 1000) {
if (i < 10) return 1;
else if (i < 100) return 2;
else return 3;
} else {
if (i < 10000) return 4;
else return 5;
}
} else {
if (i < 10000000) {
if (i < 1000000) return 6;
else return 7;
} else {
if (i < 100000000) return 8;
else if (i < 1000000000) return 9;
else return 10;
}
}
}
Bit Twiddle Hacks에서:
명확한 방법으로 정수의 정수 로그 기준 10을 찾습니다.
비교 순서를 적어 둡니다.
아무도 언급하지 않았기 때문에 10^ 미만은 SIMD로 실행할 수 있습니다.여기 sse2, avx2, arm-v8용 이브 라이브러리가 있는 구현이 있습니다.
https://godbolt.org/z/bscr3MWr4
이게 얼마나 빠른지는 모르겠지만, AVX-2는 꽤 괜찮은 것 같아요.
count_digits(int): # @count_digits(int)
vmovd xmm0, edi
vpbroadcastd ymm0, xmm0
vmovdqa ymm1, ymmword ptr [rip + .LCPI0_0] # ymm1 = [10,100,1000,10000,100000,1000000,10000000,100000000]
vpcmpgtd ymm0, ymm1, ymm0
vmovmskps ecx, ymm0
bsf edx, ecx
add edx, 1
xor esi, esi
cmp edi, 1000000000
setl sil
mov eax, 10
sub eax, esi
test cl, cl
cmovne eax, edx
vzeroupper
ret
구글 검색 중 우연히 발견했습니다.http://web.archive.org/web/20190108211528/http : //www.hackersdelight.org/hdcodetxt/ilog.c.txt
빠른 벤치마크를 통해 바이너리 검색 방식이 승리했음을 명확히 알 수 있습니다.lakshmanaraj의 코드는 매우 좋고, Alexander Korobka의 코드는 ~30%, Deadcode는 조금 더 빠르지만(~10%) 위의 링크에서 다음과 같은 트릭이 10% 더 향상되었습니다.
// Integer log base 10, modified binary search.
int ilog10c(unsigned x) {
if (x > 99)
if (x < 1000000)
if (x < 10000)
return 3 + ((int)(x - 1000) >> 31);
// return 3 - ((x - 1000) >> 31); // Alternative.
// return 2 + ((999 - x) >> 31); // Alternative.
// return 2 + ((x + 2147482648) >> 31); // Alternative.
else
return 5 + ((int)(x - 100000) >> 31);
else
if (x < 100000000)
return 7 + ((int)(x - 10000000) >> 31);
else
return 9 + ((int)((x-1000000000)&~x) >> 31);
// return 8 + (((x + 1147483648) | x) >> 31); // Alternative.
else
if (x > 9)
return 1;
else
return ((int)(x - 1) >> 31);
// return ((int)(x - 1) >> 31) | ((unsigned)(9 - x) >> 31); // Alt.
// return (x > 9) + (x > 0) - 1; // Alt.
}
자릿수가 10이므로, 「10」, 「10」, 「10」에 해 주세요.digits = ilog10c(x)+1.
수 있습니다.-.
수 요:floor (log10 (abs (x))) + 1만 하면 .
if(x<10)
return 1;
if(x<100)
return 2;
if(x<1000)
return 3;
etc etc
이것에 의해, 로그나 곱셈이나 나눗셈과 같이, 계산 비용이 많이 드는 함수를 회피할 수 있습니다.이 기능을 함수로 캡슐화함으로써 이 기능을 숨길 수 있습니다.그것은 복잡하거나 유지하기가 어렵지도 않기 때문에 나는 코딩 연습이 나쁘다고 해서 이 접근법을 무시하지 않을 것이다. 그렇게 하는 것은 아기를 목욕물과 함께 버리는 것이라고 생각한다.
C언어에 대해 조금 조정해 주세요.
floor( log10( abs( (number)?number:1 ) ) + 1 );
int n = 437788;
int N = 1;
while (n /= 10) N++;
v..에서 r 자리수를 가져오지 않는 이진 검색 의사 알고리즘.
if (v < 0 ) v=-v;
r=1;
if (v >= 100000000)
{
r+=8;
v/=100000000;
}
if (v >= 10000) {
r+=4;
v/=10000;
}
if (v >= 100) {
r+=2;
v/=100;
}
if( v>=10)
{
r+=1;
}
return r;
void main()
{
int a,i;
printf("Enter the number :");
scanf("%d",&a);
while(a>0)
{
a=a/10;
i++;
}
getch();
}
플로어(log10(...))를 사용하지 마십시오.이것들은 부동소수점 함수이며, 추가하는 데 시간이 걸립니다.가장 빠른 방법은 다음과 같은 기능이 될 것입니다.
int ilog10(int num)
{
unsigned int num = abs(num);
unsigned int x, i;
for(x=10, i=1; ; x*=10, i++)
{
if(num < x)
return i;
if(x > INT_MAX/10)
return i+1;
}
}
일부 사용자가 제안한 바이너리 검색 버전은 분기 예측 오류로 인해 속도가 느려질 수 있습니다.
편집:
몇 가지 테스트를 해봤는데 정말 흥미로운 결과가 나왔어요.팍스에서 테스트한 모든 함수와 lakshmanaraj에서 제공하는 바이너리 검색 기능을 함께 테스트했습니다.테스트는 다음 코드 스니펫에 의해 수행됩니다.
start = clock();
for(int i=0; i<10000; i++)
for(int j=0; j<10000; j++)
tested_func(numbers[j]);
end = clock();
tested_func_times[pass] = end-start;
numbers [ ]배열에는 int 타입의 전체 범위(MIN_INT 제외)에서 랜덤으로 생성된 번호가 포함됩니다.THE SAME number [ ]어레이로 테스트된 각 기능에 대해 테스트를 반복했습니다.전체 테스트는 10회 실시되었으며, 결과는 모든 패스에 평균이 적용되었습니다.코드는 -O3 최적화 레벨을 가진 GCC 4.3.2로 컴파일되었습니다.
결과는 다음과 같습니다.
floating-point log10: 10340ms
recursive divide: 3391ms
iterative divide: 2289ms
iterative multiplication: 1071ms
unrolled tests: 859ms
binary search: 539ms
정말 깜짝 놀랐어요.바이너리 검색이 생각보다 훨씬 더 잘 수행되었습니다.저는 GCC가 어떻게 이 코드를 asm으로 컴파일했는지 확인했습니다.O_O. 이제 정말 대단해.생각했던 것보다 훨씬 더 잘 최적화되어 대부분의 지점을 매우 교묘하게 피했습니다.당연히 빠릅니다.
이 수식(log10(abs(x)))을 사용하여 숫자의 자릿수를 찾을 수 있습니다.여기서 ceil은 숫자보다 큰 정수를 반환합니다.
가장 간단한 방법은 다음과 같습니다.
int digits = 0;
if (number < 0) digits = 1;
while (number) {
number /= 10;
digits++;
}
숫자를 입력하면 답이 나옵니다.
부호 있는 정수의 길이(자릿수)를 찾는 간단한 방법은 다음과 같습니다.
while ( abs(n) > 9 )
{
num /= 10;
++len;
}
어디에n의 길이와 위치를 찾는 정수입니다.len는, 정수내의 자리수와 같습니다.이것은, 다음의 양쪽의 값에 대해서 유효합니다.n(부정 또는 양).
에의 문의처abs()양의 정수만 사용하는 경우 옵션입니다.
언급URL : https://stackoverflow.com/questions/1068849/how-do-i-determine-the-number-of-digits-of-an-integer-in-c
'programing' 카테고리의 다른 글
| Vue 컴포넌트로의 Particles.js (0) | 2022.07.19 |
|---|---|
| Vue에서 v-model에 최소/최대 특성을 적용하는 방법 (0) | 2022.07.19 |
| Vuejs js는 1페이지 어플리케이션이 아닌 여러 페이지에 대응합니다. (0) | 2022.07.19 |
| Java에서 2개의 XML 문서를 비교하는 가장 좋은 방법 (0) | 2022.07.19 |
| 다형성:"ArrayList list = new ArrayList" 대신 "List list = new ArrayList"를 사용하는 이유는 무엇입니까? (0) | 2022.07.19 |