msb (most significant set bit)구하기

방법 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을 반환한다.
필요에 따라 적절히 코드를 수정하여 사용할 필요가 있다.

/**
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*p = (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==-1023) return -1;
        }
        et = clock();
        cout << (et - st) / 1000.0 << endl;
    }
    {
        st = clock();
        for (int i = 1; i < LIMIT; i++) {
            int msbIdx = msbComki(i);
            if(msbIdx==-1023) return -1;
        }
        et = clock();
        cout << (et - st) / 1000.0 << endl;
    }
    return 0;
}