C에서 가장 높은 순서 비트 찾기

C에서 가장 높은 순서 비트 찾기

이 질문에는 이미 다음과 같은 답이 있습니다.

C에서 정수에서 가장 높은 설정 비트(msb)를 찾는 가장 빠르고 효율적인 방법은 무엇입니까? (32개 답변)

마감됨2년 전에.

제가 원하는 것은 제가 숫자를 입력할 수 있는 것이고 그것은 가장 높은 주문 비트를 반환할 것입니다.저는 간단한 방법이 있다고 확신합니다.다음은 출력 예입니다(왼쪽이 입력).

1 -> 12 -> 23 -> 24 -> 45 -> 46 -> 47 -> 48 -> 89 -> 8...
63 -> 32

해커의 기쁨에서:

int hibit(unsigned int n) {
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

이 버전은 32비트 int용이지만 논리를 64비트 이상으로 확장할 수 있습니다.

fls여러 아키텍처에 대한 하드웨어 지침을 요약합니다.저는 이것이 아마도 가장 간단하고 빠른 방법일 것이라고 생각합니다.

1<<(fls(input)-1)

이 정도면 효과가 있을 겁니다.

int hob (int num)
{
    if (!num)
        return 0;

    int ret = 1;

    while (num >>= 1)
        ret <<= 1;

    return ret;
}

hob(1234)이 1024를 반환합니다.
hob(hob)이 1024를 반환합니다.
hob(1023)이 512를 반환합니다.

난독화된 코드처럼?사용해 보십시오.

1 << (int) log2 (x)

이 파티에 약간 늦었지만 컴파일러로서 현대의 GCC를 고려할 때 제가 찾은 가장 간단한 해결책은 다음과 같습니다.

static inline int_t get_msb32 (register unsigned int val)
{
  return 32 - __builtin_clz(val);
}

static inline int get_msb64 (register unsigned long long val)
{
  return 64 - __builtin_clzll(val);
}

그것은 심지어 상대적으로 휴대가 가능합니다(적어도 어떤 GCC 플랫폼에서도 작동할 것입니다).

계속해서 제거 낮은 순서 비트가 떠오릅니다...

int highest_order_bit( int x )
{
    int y = x;
    do { 
        x = y;
        y = x & (x-1); //remove low order bit
    }
    while( y != 0 );
    return x;
}

리눅스 커널에는 여러 아키텍처에 가장 효율적인 방식으로 코딩된 이와 같은 편리한 비트톱이 많이 있습니다.일반 버전은 include/asm-generic/bitops/fls.h(및 friends)에서 찾을 수 있지만 속도가 중요하고 휴대성이 중요하지 않은 경우 인라인 어셈블리를 사용하는 정의는 include/asm-x86/bitops.h를 참조하십시오.

빠른 방법은 조회 테이블을 사용하는 것입니다.32비트 입력 및 8비트 조회 테이블의 경우 에서는 4회만 반복하면 됩니다.

int highest_order_bit(int x)
{
    static const int msb_lut[256] =
        {
            0, 0, 1, 1, 2, 2, 2, 2, // 0000_0000 - 0000_0111
            3, 3, 3, 3, 3, 3, 3, 3, // 0000_1000 - 0000_1111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_0000 - 0001_0111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_1000 - 0001_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_0000 - 0010_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_1000 - 0010_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_0000 - 0011_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_1000 - 0011_1111

            6, 6, 6, 6, 6, 6, 6, 6, // 0100_0000 - 0100_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0100_1000 - 0100_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_0000 - 0101_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_1000 - 0101_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_0000 - 0110_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_1000 - 0110_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_0000 - 0111_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_1000 - 0111_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1000_0000 - 1000_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1000_1000 - 1000_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_0000 - 1001_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_1000 - 1001_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_0000 - 1010_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_1000 - 1010_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_0000 - 1011_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_1000 - 1011_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1100_0000 - 1100_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1100_1000 - 1100_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_0000 - 1101_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_1000 - 1101_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_0000 - 1110_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_1000 - 1110_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_0000 - 1111_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_1000 - 1111_1111
        };

    int byte;
    int byte_cnt;

    for (byte_cnt = 3; byte_cnt >= 0; byte_cnt--)
    {
        byte = (x >> (byte_cnt * 8)) & 0xff;
        if (byte != 0)
        {
            return msb_lut[byte] + (byte_cnt * 8);
        }
    }

    return -1;
}

이 문제는 기존 라이브러리 호출로 쉽게 해결할 수 있습니다.

int highestBit(int v){
  return fls(v) << 1;
}

Linux man 페이지에는 이 기능과 다른 입력 유형에 대한 자세한 내용이 나와 있습니다.

휴대용 솔루션이 필요 없고 코드가 x86 호환 CPU에서 실행 중인 경우 Microsoft Visual C/C++ 컴파일러에서 제공하는 _BitScanReverse() 고유 함수를 사용할 수 있습니다.가장 높은 비트 세트를 반환하는 BSR CPU 명령에 매핑됩니다.

제가 가장 좋아하는 알고리즘은 다음과 같습니다.

unsigned hibit(unsigned n) {
    n |= (n >>  1u);
    n |= (n >>  2u);
    n |= (n >>  4u);
    n |= (n >>  8u);
    n |= (n >> 16u);
    return n - (n >> 1);
}

또한 unint64_t에 대해 다음과 같이 쉽게 확장됩니다.

uint64_t hibit(uint64_t n) {
    n |= (n >>  1u);
    n |= (n >>  2u);
    n |= (n >>  4u);
    n |= (n >>  8u);
    n |= (n >> 16u);
    n |= (n >> 32u);
    return n - (n >> 1);
}

심지어 __int128까지

__int128 hibit(__int128 n) {
    n |= (n >>  1u);
    n |= (n >>  2u);
    n |= (n >>  4u);
    n |= (n >>  8u);
    n |= (n >> 16u);
    n |= (n >> 32u);
    n |= (n >> 64u);
    return n - (n >> 1);
}

또한 컴파일러를 사용하지 않고도 크로스 플랫폼 솔루션을 제공합니다.

// Note doesn't cover the case of 0 (0 returns 1)
inline unsigned int hibit( unsigned int x )
{
  unsigned int log2Val = 0 ;
  while( x>>=1 ) log2Val++;  // eg x=63 (111111), log2Val=5
  return 1 << log2Val ; // finds 2^5=32
}

제가 생각해낸 멋진 해결책은 비트를 이진법으로 검색하는 것입니다.

uint64_t highestBit(uint64_t a, uint64_t bit_min, uint64_t bit_max, uint16_t bit_shift){
    if(a == 0) return 0;
    if(bit_min >= bit_max){
        if((a & bit_min) != 0)
            return bit_min;
        return 0;
    }
    uint64_t bit_mid = bit_max >> bit_shift;
    bit_shift >>= 1;
    if((a >= bit_mid) && (a < (bit_mid << 1)))
        return bit_mid;
    else if(a > bit_mid)
        return highestBit(a, bit_mid, bit_max, bit_shift);
    else
        return highestBit(a, bit_min, bit_mid, bit_shift);

}

비트 최대값은 2의 최고 거듭제곱이므로 64비트 숫자의 경우 2^63이 됩니다.비트 이동은 비트 수의 절반으로 초기화되어야 하므로 64비트의 경우 32비트가 됩니다.

언급URL : https://stackoverflow.com/questions/53161/find-the-highest-order-bit-in-c