현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

[완료] 2의 거듭제곱에서 지수를 빠르게 구하는 방법

klara의 이미지
글쓴이: klara / 작성시간: 월, 2012/07/23 - 11:12오전

2의 거듭제곱수가 있을때, 그 지수를 빠르게, 예를 들면 간단한 산술연산이나 비트연산만으로 구할 수 있는 방법이 없을까요?
즉, 지수를 구하는 어떤 함수 foo()가 있다면

foo(1) == 0
foo(2) == 1
foo(4) == 2
foo(8) == 3
foo(16) == 4
...

이와같은 결과를 얻고싶습니다.
밑이 2인 로그를 취하는 방법도 있지만, 이쪽은 로그를 계산해야되고, 거기다가 부동소수점연산이 되버립니다.
혹시나 이미 알려진 방법이 있는지 궁금합니다.

Forums: 
프로그래밍 QnA
ymir의 이미지

글쓴이: ymir / 작성시간: 월, 2012/07/23 - 11:49오전

r-shift 는 어떨까요?

uint32_t foo(uint32_t n)
{
    uint32_t i = 0;
 
    while ((n = n >> 1))
        ++i;
 
    return i;
}

되면 한다! / feel no sorrow, feel no pain, feel no hurt, there's nothing gained.. only love will then remain.. 『 Ｍｉｚｚ 』

klara의 이미지

글쓴이: klara / 작성시간: 월, 2012/07/23 - 12:24오후

루프로 0이 될때까지 시프트 시키는것도 떠오르긴 했었는데, 루프없이 할 순 없을까요?
사실 프로그램짜다보니 결국 별로 필요없는 질문이 되어버리긴 했는데, 뭔가 기상천외한 방법이 나오기를 기대하고 남겨둡니다.

ymir의 이미지

글쓴이: ymir / 작성시간: 월, 2012/07/23 - 12:48오후

정수형에서 처음 1이 나오는 bit 의 offset 을 구해야 하는 문제인데..
loop 안 쓰고는... 금방 생각이 떠오르지 않네요..;;

검색 결과도.. 음.. 그다지 신통치는 않습니다.
http://stackoverflow.com/questions/8729109/get-bit-offset-in-c

되면 한다! / feel no sorrow, feel no pain, feel no hurt, there's nothing gained.. only love will then remain.. 『 Ｍｉｚｚ 』

rhseo6953의 이미지

글쓴이: rhseo6953 / 작성시간: 월, 2012/07/23 - 8:02오후

...

ymir의 이미지

글쓴이: ymir / 작성시간: 화, 2013/01/29 - 6:18오후

오래전 글이긴 한데, 코드 분석하다 아래 매크로를 보니 이 글이 생각나더군요.
그냥 참고 삼아 올려봅니다.

#define BITNO_32(x) (((x) >> 16) ? 16 + BITNO_16((x) >> 16) : BITNO_16((x)))
#define BITNO_16(x) (((x) >> 8) ? 8 + BITNO_8((x) >> 8) : BITNO_8((x)))
#define BITNO_8(x) (((x) >> 4) ? 4 + BITNO_4((x) >> 4) : BITNO_4((x)))
#define BITNO_4(x) (((x) >> 2) ? 2 + BITNO_2((x) >> 2) : BITNO_2((x)))
#define BITNO_2(x) (((x) & 2) ? 1 : 0)

되면 한다! / feel no sorrow, feel no pain, feel no hurt, there's nothing gained.. only love will then remain.. 『 Ｍｉｚｚ 』

jick의 이미지

글쓴이: jick / 작성시간: 월, 2012/07/23 - 1:22오후

1인 비트의 위치를 구하는 ffs라는 함수가 있습니다.

x86 전용이라면 bsf(bit scan forward), bsr(bit scan reverse)라는 명령을 쓸 수도 있습니다.

qiiiiiiiip의 이미지

글쓴이: qiiiiiiiip / 작성시간: 월, 2012/07/23 - 1:30오후


테이블을 쓰는방법 등등..

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

snowall의 이미지

글쓴이: snowall / 작성시간: 월, 2012/07/23 - 1:38오후

2진수로 쓴다면, n자리 중 몇번째 자리에 1이 있는지 보는 거네요. mux-demux 개념을 응용해보면 어떨까 싶은데요

n자리 2진수 비트필드에 대해서 b[0]*1+b[1]*2+b[2]*3+...+b[n]*(n+1)를 쓰면 k번째 자리에만 1이 있다고 하면 이 답이 k+1로 떨어집니다.

보통, 정수는 32비트 등으로 고정된 자릿수를 사용하므로 굳이 반복문을 안써도 그냥 32개의 곱셈과 덧셈으로 충분하겠죠.
(그러나 이렇게 해버리면 반복문이 더 빠를지도 모릅니다.)

덧셈만 갖고 만들고 싶다면, b=2^k라고 가정하고,
c=(b-1)
k=c[0]+c[1]+...+c[n]+1
이렇게 됩니다.

n=32등으로 고정된 자릿수라서 이런게 가능한 것이고, 비트 수가 고정되지 않는다면 그냥 루프문 돌려야겠네요.

피할 수 있을때 즐겨라! http://melotopia.net/b

qiiiiiiiip의 이미지

글쓴이: qiiiiiiiip / 작성시간: 월, 2012/07/23 - 1:43오후

32개의 곱셈과 덧셈..

또는

k=c[0]+c[1]+...+c[n]+1

가 이미 루프 아닌가요?

snowall의 이미지

글쓴이: snowall / 작성시간: 월, 2012/07/23 - 1:59오후

매우 반복적이긴 하지만 명시적으로 루프는 아니죠. ㅎㅎ

아무튼 조건대로 1.루프를 사용하지 않고 2.산술연산만으로 구했으니까요

루프라고 하신다면 루프로 볼 수도 있지만, 그렇다면 저는 더이상은 모르겠습니다.

애초에 이 아이디어는 demux에서 떠올렸거든요. 그런데 demux를 산수로 구현해보니 위와 같이 되네요...ㅜ

그리고 제가 1을 더한 것은 틀렸네요. 메르센 수는 2^n -1 은 2진수 표현에서 1이 n번 반복되는군요. 실수했습니다.

피할 수 있을때 즐겨라! http://melotopia.net/b

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2012/07/23 - 2:32오후

첨부터 끝까지 나올때까지 검사하는 루프가 맘에 들지 않는다면
바이너리 서치를 구현하면 되죠. ^^

hiseob의 이미지

글쓴이: hiseob / 작성시간: 월, 2012/07/23 - 3:00오후

if(arg & (0x1 << 0)) {
return 0;
}
if (arg & (0x1 << 1)) {
return 1;
}
...
}
if (arg & (0x1 << 31)) {
return 31;
}

루프가 정말 싫으시다면야 뭐...

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2012/07/23 - 3:44오후

32비트 언사인드를 가정하고 할때,
나올수 있는 결과는 총 32개이지요. (0 제외)
그러다면, deterministic한 알고리즘을 사용하였을때, 하나의 비교로 최대 반의 결과값을 invalidate시킬수 있습니다.
그러면 적어도 worst case 최대 5번의 비교를 하여야만 결과값을 구할 수 있습니다.
그렇다는 것은, binary search를 통해 worst case의 비교값 5번과 같다는 것을 알 수 있으며, 이것이 optimal입니다.

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2012/07/23 - 4:04오후

2의 제곱수를 배열에 담아두고 맞춰보는 게 제일 빠를 겁니다.

간단하죠?

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2012/07/23 - 4:10오후

윗분 2의 제곱수를 인덱스로 놓는 경우를 말씁하시는거라면.
32비트 언사인드의 경우
2^32 * 1 = 4,294,967,296 (char 배열이라고 가정하겠습니다)
대략 4기가바이트가 필요합니다, 하지만 물론 계산은 단 한번의 포인터 액세스로 가능하겠지요 ^^;;;
맵을 말씁하신거라면, tree map의 경우 바이너리 써치와 같이 최대 5번,
hash map의 경우, 일단 해쉬값을 구하는데 걸리는 인트스럭션 개수(적어도 5번 이상일듯...) + 1번의 포인터 오퍼레이션이 필요하겠지요..

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2012/07/23 - 4:56오후

2진수나 16진수로 압축해서 저장하면 줄어들겠죠.

그런데 이 경우 다시 연산속도가 느려집니다.

그냥 크더라도 저장하는 게 낫겠네요.

그런데 어떻게 해서 4기가 바이트인가요? 4,294,967,296은 10글자니까 10바이트면 되는 거 아닌가요?

말씀대로 기상천외한 방법을 찾으신다면,

The first 84 powers of two
http://en.wikipedia.org/wiki/Power_of_two

여기에 십진수 목록이 있습니다.

매자리마다 2~6개정도씩 있는데 이 자릿수로 검색하는 방법을 무슨 알고리듬이라고 하는 걸까요?

4자리 4개, 5자리 3, 6자리 3, 7자리 4, 8자리 3, 9자리 3, 10자리 4, 11자리 3, 12자리 3, 13자리 4, 15자리 3...

그리고 끝자리는 2,4,8,6 순으로 반복됩니다.

해시인가요? 트리맵인가요?

제가 전산과가 아니라 잘 모릅니다.

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2012/07/23 - 4:56오후

배열은.....
연속적이여야 합니다...
그래서 필요없어도 1~2^32까지의 인덱스를 모두 가지고 있어야 하고요. (그렇기에 compression이라는 개념자체가 들어올 수 없습니다;;;)

님께서 말씀하신 바는 맵인데..
이는 일단 바이너리 서치나, 해쉬를 통해 key value 페어의 위치를 구해야 합니다.

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2012/07/23 - 5:00오후

제가 압축한다는 뜻은 1인 자릿수만 저장한다는 뜻이었습니다.

그러니까 원래대로 되는 거라서 말이 안된다는 뜻이었습니다.

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2012/07/23 - 5:10오후

아. 숫자의 digit 개수를 가지고 본다는 말씁이신가요?
하지만 digit개수 자채를 세는데에 들어가는 연산 개수가 따로...
이런건 따로 알고리즘이라기 보다는 핵에 가깝겠지요.

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2012/07/23 - 5:12오후

2진수에서 1의 위치를 검색하는 게 자릿수 찾는 거나 마찬가지죠.

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2012/07/23 - 6:31오후

10의 자릿수마다 4,3,3개씩 반복되서 할당되는 것 같습니다.

언제까지 그렇게 되는 지는 원리를 따져봐야 합니다.

"a, b, c가 자연수라고 할 때, 순서쌍 (a,b,c)는 10^a<=2^b && 10^(a+1)>2^(b+c)를 만족한다.

이를 만족하는 순서쌍을 출력하라."

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2012/07/23 - 7:14오후

2^90 1237940039285380274899124224
2^91 2475880078570760549798248448
2^92 4951760157141521099596496896
2^93 9903520314283042199192993792
2^94 19807040628566084398385987584
2^95 39614081257132168796771975168
2^96 79228162514264337593543950336
2^97 158456325028528675187087900672
2^98 316912650057057350374175801344
2^99 633825300114114700748351602688
2^100 1267650600228229401496703205376 <- 세번째 3이 있네요.
2^101 2535301200456458802993406410752
2^102 5070602400912917605986812821504
2^103 10141204801825835211973625643008
2^104 20282409603651670423947251286016
2^105 40564819207303340847894502572032
2^106 81129638414606681695789005144064

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2012/07/23 - 4:36오후

참고: 2의 제곱수인지 확인하는 방법과 나누기로 찾는 방법입니다.
http://en.wikipedia.org/wiki/Power_of_two

역시 2로 나누기(비트 연산 포함)가 제일 빠른 듯 합니다.

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

klara의 이미지

글쓴이: klara / 작성시간: 일, 2012/07/29 - 10:38오전

답변 달아주신분들 모두 감사합니다. 이식성은 없겠지만 전용명령어가 있다는 건 재밌네요.

나그네나그네의 이미지

글쓴이: 나그네나그네 / 작성시간: 일, 2012/07/29 - 2:32오후

제가 생각한 최소 연산 횟수는 10번이군요.
1024를 예로 들 경우
(숫자가 32bit integer일 경우에)

a = 0000 0000 0000 0000 0000 0100 0000 0000
int answer = 0 // 답 저장

if( a & (1111 1111 1111 1111 0000 0000 0000 0000)) answer += 16
if(a & (1111 1111 0000 0000 1111 1111 0000 0000)) answer += 8
if(a & (1111 0000 1111 0000 1111 0000 1111 0000)) answer += 4
if(a & (1100 1100 1100 1100 1100 1100 1100 1100)) answer += 2
if(a & (1010 1010 1010 1010 1010 1010 1010 1010)) answer += 1

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.