C에서 정수의 자릿수를 어떻게 결정합니까?
예를 들어
n = 3432, result 4
n = 45, result 2
n = 33215, result 5
n = -357, result 3
나는 그것을 문자열로 바꾸고 문자열의 길이를 얻을 수 있다고 생각하지만 그것은 복잡하고 해킹 된 것처럼 보입니다.
floor (log10 (abs (x))) + 1
http://en.wikipedia.org/wiki/Logarithm
재귀 적 접근 방식 :-)
int numPlaces (int n) {
if (n < 0) return numPlaces ((n == INT_MIN) ? MAX_INT: -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;
}
위의 내용은 MININT를 더 잘 처리하도록 수정되었습니다. 정수에 대해 합리적인 2 n 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 문 솔루션과 일치하지 않습니다.
무작위로 생성 된 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
가장 짧은 대답 : snprintf(0,0,"%+d",n)-1
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;
결과가 0이 될 때까지 루프에서 10으로 나눕니다. 반복 횟수는 소수 자릿수에 해당합니다.
0 값에서 0 자리를 얻을 것으로 예상한다고 가정합니다.
int countDigits( int value )
{
int result = 0;
while( value != 0 ) {
value /= 10;
result++;
}
return result;
}
당신은 할 수 있습니다 : floor (log10 (abs (x))) + 1또는 사이클을 저장하려면 비교를 할 수 있습니다
if(x<10)
return 1;
if(x<100)
return 2;
if(x<1000)
return 3;
etc etc
이렇게하면 로그 나 곱셈 또는 나눗셈과 같은 계산 비용이 많이 드는 함수를 피할 수 있습니다. 우아하지 않지만 함수로 캡슐화하여 숨길 수 있습니다. 유지 관리가 복잡하거나 어렵지 않으므로 잘못된 코딩 관행 때문에이 접근 방식을 무시하지 않을 것입니다. 나는 목욕물과 함께 아기를 내 던질 것이라고 생각합니다.
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 );
}
더 작은 조회 테이블과 여기 에서 가져온 log10 근사치가있는 또 다른 것 입니다.
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과 같다는 사실을 활용합니다.
최신 정보:
제안에 따라 여기에는 임의 부호 분포로 집합을 생성하도록 수정 된 매우 멋진 paxdiablo의 테스트 프로그램을 사용하여 이진 검색 및 이진 절단 알고리즘에 비해 count_bsr 및 약간 더 빠른 64 비트 전용 count_bsr_mod 루틴이 있습니다. 테스트는 "-O3 -falign-functions = 16 -falign-jumps = 16 -march = corei7-avx"옵션을 사용하여 gcc 4.9.2로 빌드되었으며 터보 및 절전 상태가 꺼진 다른 정지 상태의 Sandy Bridge 시스템에서 실행되었습니다.
BSr 모드의 시간 : 270000 BSR 시간 : 340000 바이너리 절단 시간 : 800000 이진 검색 시간 : 770000 이진 검색 모드 시간 : 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;
}
Bit Twiddling Hacks에서 :
비교 순서에 유의하십시오.
Google 검색 중에이 문제를 발견했습니다. 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이므로 digits = ilog10c(x)+1.
네거티브를 지원하지 않지만 -.
다음은 나눗셈이나 곱셈없이 펼쳐진 이진 검색입니다. 주어진 숫자의 분포에 따라 풀린 if 문으로 수행 한 다른 문을 이길 수도 있고 그렇지 않을 수도 있지만 항상 루프와 곱셈 / 나눗셈 / log10을 사용하는 문을 이겨야합니다.
전체 범위를 포괄하는 난수의 균일 한 분포를 통해 내 컴퓨터에서는 paxdiablo의 count_bchop () 실행 시간의 평균 79 %, count_ifs ()의 시간 88 %, count_revifs ()의 시간의 97 %를 평균했습니다.
지수 분포 ( n 자리 숫자 의 확률은 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;
}
}
}
int n = 437788;
int N = 1;
while (n /= 10) N++;
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
매우 우아하지 않습니다. 그러나 다른 모든 솔루션보다 빠릅니다. Integer Division 및 FP 로그는 비용이 많이 듭니다. 성능이 문제가되지 않는다면 log10 솔루션이 가장 좋습니다.
C 언어에 대해 약간 조정하십시오.
floor( log10( abs( (number)?number:1 ) ) + 1 );
나는 늦었다는 것을 알고 있지만이 코드는 다른 모든 답변보다 + x10 빠릅니다.
int digits(long long x)
{
x < 0 ? x = -x : 0;
return x < 10 ? 1 :
x < 100 ? 2 :
x < 1000 ? 3 :
x < 10000 ? 4 :
x < 100000 ? 5 :
x < 1000000 ? 6 :
x < 10000000 ? 7 :
x < 100000000 ? 8 :
x < 1000000000 ? 9 :
x < 10000000000 ? 10 : 0;
}
...
int x = -937810;
printf("%d : %d digits\n", x, digits(x));
밖:
-937810 : 6 digits
floor (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;
}
}
일부 사람들이 제안한 이진 검색 버전은 분기 예측 오류로 인해 느려질 수 있습니다.
편집하다:
몇 가지 테스트를했고 정말 흥미로운 결과를 얻었습니다. Pax가 테스트 한 모든 기능과 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 제외). 테스트는 동일한 숫자 [] 배열에서 테스트 된 각 함수에 대해 반복되었습니다. 전체 테스트는 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. 이제 이것은 인상적입니다. 제가 생각했던 것보다 훨씬 더 잘 최적화되어 정말 영리한 방법으로 대부분의 지점을 피했습니다. 빠르다는 것은 당연합니다.
다음 공식을 사용하여 숫자의 자릿수를 찾을 수 있습니다. ceil (log10 (abs (x))) 여기서 ceil은 숫자보다 큰 정수를 반환합니다.
가장 간단한 방법은 다음과 같습니다.
int digits = 0;
if (number < 0) digits = 1;
while (number) {
number /= 10;
digits++;
}
digits gives the answer.
A simple way to find the length (i.e number of digits) of signed integer is this:
while ( abs(n) > 9 )
{
num /= 10;
++len;
}
Where n is the integer you want to find the length of and where len is equal to the number of digits in the integer. This works for both values of n (negative or positive).
The call on abs() is optional, if you are only working with positive integers.
For c#, here is a very fast and simple solution...
private static int NumberOfPlaces(int n)
{
//fast way to get number of digits
//converts to signed string with +/- intact then accounts for it by subtracting 1
return n.ToString("+#;-#;+0").Length-1;
}
void main()
{
int a,i;
printf("Enter the number :");
scanf("%d",&a);
while(a>0)
{
a=a/10;
i++;
}
getch();
}
'Programing' 카테고리의 다른 글
| manage.py 셸을 사용하지 않고 모델 객체에 액세스하는 Django 스크립트 (0) | 2020.11.19 |
|---|---|
| jQuery로 포커스가있는 요소를 선택하는 방법 (0) | 2020.11.19 |
| Haskell에있는 2 개 목록의 데카르트 곱 (0) | 2020.11.19 |
| 두 세트의 1000 개 숫자를 서로 어떻게 비교할 수 있습니까? (0) | 2020.11.19 |
| div id에 대한 임의의 문자열 생성 (0) | 2020.11.19 |