먼저 '1'앞에 모든 비트를 설정하십시오.

32 비트 부호없는 정수를 가정하십시오. 이 정수는 2의 거듭 제곱이라고 가정 할 수 있으므로 1 비트만 설정됩니다. 정수 비트를 제외한 모든 비트를 정수로 설정하려고합니다. 따라서 (간결을 위해 8 비트 정수를 사용) 00001000은 11111000이됩니다.먼저 '1'앞에 모든 비트를 설정하십시오.

이것은 물론 한 세트의 비트를 찾고 높은 비트를 반복하면서 그것들을 설정함으로써 달성 될 수 있습니다. 가장 높은 설정 비트의 위치 반환 highest_set 가정 :

이

uint32_t f(uint32_t x) 
{ 
    int n = highest_set(x); 
    for (int i = 31; i != n; --i) { 
     x |= 1 << i; 
    } 
    return x; 
}

f의 런타임 그러나 x의 값에 따라 않는, 그리고 내가이 일을하는 영리한 방법이 있다고 생각합니다.

출처

2012-09-13 Viktor Dahl

개념적으로 쉬운 일은 x-1을 취한 다음 0xffffffff과 XOR하는 것입니다. 아래의 주석에서 harold가 수행 한 것처럼 ~(x-1)으로 작성하면 XORing을 변경하지 않고도 다른 크기의 정수를 처리 할 수 있습니다.

출처

2012-09-13 17:29:29 David

당신이 언급 한'~ (x - 1)'해결책은 아마도 현대의 어떤 것에 더 빠를 것입니다. 또한 적은 코드. – harold

@harold 동의 함. 나는 룩업 테이블에 대한 부분을 제거했다. 왜냐하면 대부분의 경우 실제 이점이 없기 때문에 더 복잡해 졌기 때문이다. – David

uint32_t f(uint32_t x) 
{ 
    bool bitset=false; //C++ 
    for (int i =0; i<sizeof(int); i++) { 
    if(bitset) //After the first 1 
     { x |= 1 << i; } 
     else 
     { 
      if(x&(1<<i)) 
      bitset=true; //if 1 found then the flag is raised 
     } 

    } 
    return x; 
}

출처

2012-09-13 17:33:11 user1655481

오른쪽 시프트 로그 (값), 또는 1의 의 비트 마스크 좌측 시프트 로그 (값)와. 이것은 모든 입력에 대해 동일한 실행 시간을 갖는 일반적인 솔루션이어야하며, 보장은 없습니다.

출처

2012-09-13 17:40:34 Stu

쉬운 지속적으로 32 배 루프에 많은 솔루션 위의 모든 시간을 필요로하지 않는 솔루션을

while (!(x & 0x80000000)) 
    x |= x << 1;

이 코드를 이해합니다. 그러나 위의 다윗의 해결책은 가장 빠른 것입니다.

출처

2013-08-01 03:58:34

먼저 '1'앞에 모든 비트를 설정하십시오.

답변

관련 문제