숫자의 0이 아닌 비트 왼쪽 끝을 끄기

Question

O(1)에서 가장 왼쪽의 non-zero 비트를 끌 수있는 방법은 무엇입니까? 예를 들어

이

n = 366 (base 10) = 101101110 (in base 2) 

그런 다음 왼쪽 non-zero 비트를 끈 후, 수 =처럼 보이는 001101110

n은 항상있을 것입니다> 0

Answer 1

n = 2^x + y. x = log(n) base 2

가장 높은 세트 비트 x입니다.

그 비트를 재설정하기 위해

그래서, number &= ~(1 << x);

또 다른 방법 : 가능성이 더 빠른 솔루션

int highestOneBit(int i) { 
    i |= (i >> 1); 
    i |= (i >> 2); 
    i |= (i >> 4); 
    i |= (i >> 8); 
    i |= (i >> 16); 
    return i - (i >> 1); 
} 

int main() { 
    int n = 32767; 
    int z = highestOneBit(n); // returns the highest set bit number i.e 2^x. 
    cout<< (n&(~z)); // Resets the highest set bit. 
    return 0; 
} 

Answer 2

체크 아웃 this question, 프로세서 명령어를 사용하여.

그러나, O는 (LGN) 솔루션입니다 :

당신이 어떤 상황에서 O(1) 주장하는 경우 글쎄, immintrin.h에 정의 된 인텔 내장 함수 기능 _bit_scan_reverse()는 하드웨어가 가장 큰 비에 대한 찾을 않습니다

int cmsb(int x) 
{ 
    unsigned int count = 0; 
    while (x >>= 1) { 
     ++count; 
    } 

    return x & ~(1 << count); 
} 

Answer 3

int 수의 제로 비트.

비록 연산이 루프 (기능적으로 동등한 것)를 사용하지만, 지연 시간이 고정 3 일 때 (Intel Intrinsics Guide) 그 일정 시간을 믿습니다.

기능은 가장 중요한 비 제로 비트 따라서 간단한 일에 인덱스를 반환합니다

n = n & ~(1 << _bit_scan_reverse(n)); 

가 수행해야합니다.

이 내장 함수는 n == 0에 대해 정의되지 않았습니다. 따라서 조심해야합니다. n> 0 인 원래 게시물의 가정을 따릅니다.