«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

Code Run

msb (most significant set bit)구하기 본문

코딩 tip

msb (most significant set bit)구하기

comkiwer 2018. 1. 16. 22:44

방법 1. GCC인 경우 builtin 함수를 이용한다.

 __builtin_clz(k) 함수를 이용하여 leading zero bit의 개수를 구한뒤 32(또는 31)에서 빼준다.

GCC-other builtin 링크



방법 2. 아래 코드의 msbPos, msbComki 와 같이 IEEE754의 부동소수점 표기법을 이용하는 방법이다.
          지수부에 담겨있는 값이 결국에는 msbIndex임을 이해한다면 여러가지 방법으로  구할 수 있다.

 IEEE754 부동소수점 표기법


아래 msbPos, msbComki 코드는  msb를 알아보고자 하는 수가  0인 경우 -1023을 반환한다.
필요에 따라 적절히 코드를 수정하여 사용할 필요가 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
Get most significant bit
use IEEE 754 - 64bit floating point
Little Endianness
(-1)^S * (1 + M) * 2^E
S : Sign (부호)     =>  1 bit
E : Exponent (지수) => 11 bit (bias 1023)
M : Mantissa (가수) => 52 bit
*/
#include <bits/stdc++.h>
using namespace std;
 
/// http://codeforces.com/blog/entry/10330
/// use IEEE 754
int msbPos(unsigned k) {
    union { double d; int a[2]; };
    d = k;
    return (a[1>> 20- 1023;
}
 
/// comkiwer's code : use IEEE 754
inline int msbComki(double d){
    unsigned int*= (unsigned int*)&d;
    return ((*++p)>>20)-1023;
    //return (*(((unsigned int*)&d)+1)>>20)-1023;
}
 
/// use bitwise : get msb value
int msbVal(unsigned k) {
    k |= (k>>1);
    k |= (k>>2);
    k |= (k>>4);
    k |= (k>>8);
    k |= (k>>16);
    return k - (k >> 1);
}
 
void test01(){
    for(int i=0;i<10;++i){
        unsigned int k = 0;
        printf("%8d : %2d, %2d\n", i, msbPos(k), msbComki(k));
    }
}
 
int main() {
 //   test01();
    double st, et;
    const int LIMIT = 200 * 1000 * 1000;
    {
        st = clock();
        for (int i = 1; i < LIMIT; i++) {
            int msbIdx = msbPos(i);
            //int t = 31-__builtin_clz(i);
            if(msbIdx==-1023return -1;
        }
        et = clock();
        cout << (et - st) / 1000.0 << endl;
    }
    {
        st = clock();
        for (int i = 1; i < LIMIT; i++) {
            int msbIdx = msbComki(i);
            if(msbIdx==-1023return -1;
        }
        et = clock();
        cout << (et - st) / 1000.0 << endl;
    }
    return 0;
}
 
cs