실제로 선행 0을 계산할 필요가 없습니다. 주석에서 pmg가 제안한대로 찾고있는 숫자가 시퀀스 OEIS A023758 의 숫자라는 사실을 이용하여 즉, i> = j 인 2 ^ i-2 ^ j 형식의 숫자를 이용하면 후행 0을 계산할 수 있습니다 ( 즉, j-1 ), 원래 값에서 해당 비트를 토글 ( 2 ^ j-1 을 더하는 것과 동일 ) 한 다음 해당 값이 2 ^ i-1 형식인지 확인합니다 . GCC / clang 내장 함수를 사용하면

bool has_compact_bits(int val) {
    if (val == 0) return true; // __builtin_ctz undefined if argument is zero
    int j = __builtin_ctz(val) + 1;
    val |= (1 << j) - 1; // add 2^j - 1
    val &= (val + 1); // val set to zero if of the form (2^i - 1)
    return val == 0;
}

이 버전 은 KamilCuk이 제안한 버전과 팝 카운트 만있는 Yuri Feldman이 제안한 버전 보다 약간 빠릅니다 .

당신이 C ++ (20)를 사용하는 경우, 당신은 대체하여 휴대용 기능을 얻을 수 있습니다 __builtin_ctz으로 std::countr_zero:

#include <bit>

bool has_compact_bits(int val) {
    int j = std::countr_zero(static_cast<unsigned>(val)) + 1; // ugly cast
    val |= (1 << j) - 1; // add 2^j - 1
    val &= (val + 1); // val set to zero if of the form (2^i - 1)
    return val == 0;
}

캐스트는 추악하지만 비트를 조작 할 때 부호없는 유형으로 작업하는 것이 더 낫다는 경고입니다. Pre-C ++ 20 대안은 다음과 같습니다.boost::multiprecision::lsb .

편집하다:

취소 선 링크에 대한 벤치 마크는 Yuri Feldman 버전에 대해 popcount 명령이 생성되지 않았기 때문에 제한되었습니다. 를 사용하여 내 PC에서 컴파일하려고 시도 -march=westmere하면서 동일한 시퀀스로 10 억 번의 반복에 대해 다음 시간을 측정했습니다 std::mt19937.

• 현재 버전 : 5.7 초
• KamilCuk의 두 번째 버전 : 4.7 초
• 내 버전 : 4.7 초
• Eric Postpischil의 첫 번째 버전 : 4.3 초
• Yuri Feldman의 버전 (명시 적으로 사용 __builtin_popcount) : 4.1 초

따라서 적어도 내 아키텍처에서 가장 빠른 것은 popcount가있는 것 같습니다.

편집 2 :

새로운 Eric Postpischil 버전으로 벤치 마크를 업데이트했습니다. 의견에서 요청했듯이 내 테스트 코드는 여기 에서 찾을 수 있습니다 . PRNG에 필요한 시간을 추정하기 위해 no-op 루프를 추가했습니다. KevinZ의 두 가지 버전도 추가했습니다. 코드가 clang에서 컴파일 -O3 -msse4 -mbmi되어 가져 오기 popcnt및 blsi지시가 가능합니다 (Peter Cordes 덕분에).

결과 : 적어도 내 아키텍처에서 Eric Postpischil의 버전은 Yuri Feldman의 버전만큼 빠르며 지금까지 제안 된 다른 버전보다 두 배 이상 빠릅니다.