루프없이 C ++에서 int에서 가장 중요한 비 0 비트를 추출하십시오.

Question

C ++의 정수에서 가장 중요한 비트를 추출하고 그 n 비트를 정수로 변환하고 싶습니다.

예 :

int a=1200;
// its binary representation within 32 bit word-size is
// 00000000000000000000010010110000

.

이제는 그 표현으로부터 가장 중요한 4 자리를 추출하고 싶습니다. 즉, 제 1111

00000000000000000000010010110000
                     ^^^^

.

및 이들을 다시 정수로 변환하십시오 (10 진수= 9의 1001).

루프없이 간단한 C ++ 기능으로 어떻게 작동합니까?

Answer 1

일부 프로세서는 정수의 선도적 인 바이너리 0을 계산하는 명령을 가지고 있으며 일부 컴파일러에는 해당 지침을 사용할 수 있도록 도구가 있습니다.예를 들어 gcc를 사용하여 다음을 사용합니다.

uint32_t significant_bits(uint32_t value, unsigned bits) {
    unsigned leading_zeros = __builtin_clz(value);
    unsigned highest_bit = 32 - leading_zeros;
    unsigned lowest_bit = highest_bit - bits;

    return value >> lowest_bit;
}

.

단순화를 위해 요청 된 비트 수가 사용 가능한지 확인합니다.Microsoft의 컴파일러의 경우 Intrinsic을 __lzcnt라고합니다.

컴파일러가 내장성을 제공하지 않고 프로세서가 적절한 지침이 없으면 0을 신속하게 계산하는 한 가지 방법은 바이너리 검색을 사용합니다.

unsigned leading_zeros(int32_t value) {
    unsigned count = 0;
    if ((value & 0xffff0000u) == 0) {
        count += 16;
        value <<= 16;
    }
    if ((value & 0xff000000u) == 0) {
        count += 8;
        value <<= 8;
    }
    if ((value & 0xf0000000u) == 0) {
        count += 4;
        value <<= 4;
    }
    if ((value & 0xc0000000u) == 0) {
        count += 2;
        value <<= 2;
    }
    if ((value & 0x80000000u) == 0) {
        count += 1;
    }
    return count;
}

.

Answer 2

빠르지는 않지만 (int)(log(x)/log(2) + .5) + 1는 가장 중요한 0이 아닌 비트의 위치를 알려줍니다.알고리즘을 마무리하는 것은 똑바로 똑바로 앞으로 있습니다.

Answer 3

이것은 작동하는 것으로 보인다 (UINT32와 함께 C #에서 수행 한 다음 Bjarne에 사과드립니다) :

        unsigned int input = 1200;
        unsigned int most_significant_bits_to_get = 4;
        // shift + or the msb over all the lower bits
        unsigned int m1 = input | input >> 8 | input >> 16 | input >> 24;
        unsigned int m2 = m1 | m1 >> 2 | m1 >> 4 | m1 >> 6;
        unsigned int m3 = m2 | m2 >> 1;
        unsigned int nbitsmask = m3 ^ m3 >> most_significant_bits_to_get;

        unsigned int v = nbitsmask;
        unsigned int c = 32; // c will be the number of zero bits on the right
        v &= -((int)v);
        if (v>0) c--;
        if ((v & 0x0000FFFF) >0) c -= 16;
        if ((v & 0x00FF00FF) >0) c -= 8;
        if ((v & 0x0F0F0F0F) >0 ) c -= 4;
        if ((v & 0x33333333) >0) c -= 2;
        if ((v & 0x55555555) >0) c -= 1;

        unsigned int result = (input & nbitsmask) >> c;

.

정수 수학 만 사용하는 것을 의미했습니다.

@ olicharlesworth의 링크에서 몇 가지 코드를 사용 했으므로 바를 눌러 루틴 코드를 뒤에서 사용하여 조건부를 제거 할 수 있습니다.