정수의 1비트를 연속된 영역에서 테스트할 수 있는 우아하고 빠른 방법이 있는가?
비트 값 1을 가진 위치(32비트 정수의 경우 0부터 31까지)가 연속 영역을 형성하는지 테스트해야 한다.예를 들면 다음과 같다.
00111111000000000000000000000000 is contiguous
00111111000000000000000011000000 is not contiguous
나는 이 시험, 즉 어떤 기능을 원한다.has_contiguous_one_bits(int), 휴대하기 위해서.
한 가지 분명한 방법은 첫 번째 세트 비트를 찾기 위해 위치를 반복하고, 그 다음 첫 번째 세트 비트를 찾아 더 이상의 세트 비트를 확인하는 것이다.
더 빠른 방법이 있는지 궁금하다.가장 높고 가장 낮은 세트 비트를 찾는 빠른 방법이 있다면(그러나 이 질문에서 휴대용 세트 비트가 없는 것으로 나타난다) 가능한 구현은 다음과 같다.
bool has_contiguous_one_bits(int val)
{
auto h = highest_set_bit(val);
auto l = lowest_set_bit(val);
return val == (((1 << (h-l+1))-1)<<l);
}
재미로 연속 비트를 가진 첫 100개의 정수를 소개한다.
0 1 2 3 4 6 7 8 12 14 15 16 24 28 30 31 32 48 56 60 62 63 64 96 112 120 124 126 127 128 192 224 240 248 252 254 255 256 384 448 480 496 504 508 510 511 512 768 896 960 992 1008 1016 1020 1022 1023 1024 1536 1792 1920 1984 2016 2032 2040 2044 2046 2047 2048 3072 3584 3840 3968 4032 4064 4080 4088 4092 4094 4095 4096 6144 7168 7680 7936 8064 8128 8160 8176 8184 8188 8190 8191 8192 12288 14336 15360 15872 16128 16256 16320
그들은 물론 형식이다.(1<<m)*(1<<n-1)부정적으로m그리고n.
해결책:
static _Bool IsCompact(unsigned x)
{
return (x & x + (x & -x)) == 0;
}
간략하게:
x & -x가장 낮은 비트 설정x(혹은 0인 경우)x0이다.
x + (x & -x)연속 1s의 가장 낮은 문자열을 상위 1개(또는 0으로 감음)로 변환한다.
x & x + (x & -x)그 1비트를 지워버린다.
(x & x + (x & -x)) == 0다른 1비트가 남아 있는지 테스트한다.
더 긴 시간:
-x대등하다~x+1(을 위해)int그 문제에서, 우리는 둘의 보완점을 가정하지만,unsigned선호된다.비트가 뒤집힌 후~x 1 1 , 1의 1 bits 는 1 bits flight bit in.~x처음 0비트를 하다가 멈췄다.그러므로, 의 낮은 부분들은-x그것의 첫 번째 1까지 그리고 포함하는 것은 의 낮은 부분과 같다.x, 그러나 모든 상위 비트는 플립된다. (예:~10011100주다01100011, 그리고 1을 더하면01100100, 그래서 낮은 사람들.100같은 것이지만 높은 것10011에 속아 넘어가다01100.) 그러면x & -x둘 다에 1인 1비트를 주는데, 그것은 가장 낮은 1비트를 우리에게 준다.00000100) (만약x 0, 0,x & -x0이다.)
에 추가하기x연속 1초를 모두 통과시켜 0초로 변경한다.다음 높은 0비트에서 1을 남긴다(또는 하이엔드를 통과하여 래핑된 총 0을 남긴다).10100000.)
ANDed with ANDed ANDEDx.따라서 1비트 더 높은 값이 있을 경우에만 결과가 0이 아니다.
사실 어떤 본질도 사용할 필요가 없다.
첫 번째 1보다 먼저 0을 뒤집어라.그 다음 새로운 값이 메르센 수인지 시험한다.이 알고에서는 0이 참으로 매핑된다.
bool has_compact_bits( unsigned const x )
{
// fill up the low order zeroes
unsigned const y = x | ( x - 1 );
// test if the 1's is one solid block
return not ( y & ( y + 1 ) );
}
물론, 본질적인 것을 사용하고자 하는 경우, 다음과 같은 팝카운트 방법이 있다.
bool has_compact_bits( unsigned const x )
{
size_t const num_bits = CHAR_BIT * sizeof(unsigned);
size_t const sum = __builtin_ctz(x) + __builtin_popcount(x) + __builtin_clz(z);
return sum == num_bits;
}
사실 선행 0은 세지 않아도 된다.의견에서 pmg가 제안한 바와 같이, 당신이 찾고 있는 숫자가 시퀀스 OEIS A023758의 숫자라는 사실을 이용하라.i >=j와 함께 2^i - 2^j 형식의 숫자, 후행 0(즉, j - 1)을 세고, 원래 값에서 해당 비트를 전환(추가 2^j - 1)한 다음, 그 값이 2^i - 1. GCC/클랑 본질로,
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;
}
이 버전은 당신의 버전과 카밀콕이 제안한 버전과 유리 펠드만이 팝카운트만으로 제안한 버전보다 약간 더 빠르다.
C++20을 사용하는 경우, 교체하여 휴대할 수 있는 기능을 얻을 수 있다.__builtin_ctz포함:
#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;
}
출연진은 못생겼지만 비트를 조작할 때는 서명되지 않은 타입으로 작업하는 것이 좋다는 경고다.C++20 이전 대안은 입니다.
편집:
취소선 링크의 벤치마크는 Yuri Feldman 버전에 대한 팝카운트 명령이 방출되지 않았기 때문에 제한되었다.다음을 사용하여 내 PC에서 컴파일 시도 중-march=westmere 나는 억 서 서 서 서 서 서 서 서 서 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는는std::mt19937:
- 버전: 5.7초
- 카밀콕의 두 번째 버전: 4.7초
- 내 버전: 4.7초
- Eric Postpischil의 첫 번째 버전: 4.3초
- 으로 유리 펠드만 사용)
__builtin_popcount-: 4.1초
그래서 적어도 내 건축에서는 팝카운트가 가장 빠른 것 같다.
편집 2:
나는 나의 벤치마크를 새로운 Eric Postpischil 버전으로 업데이트했다.코멘트에서 요청한 대로 내 시험 코드는 여기서 찾을 수 있다.PRNG에 필요한 시간을 추정하기 위해 노-오프 루프를 추가했고 케빈Z의 두 버전도 추가했다.코드가 clang에 컴파일됨-O3 -msse4 -mbmi갖기 위해popcnt그리고blsi지시(Peter Codes 덕분).
결과:적어도 내 건축에서 에릭 포스피스칠의 버전은 유리 펠드만의 버전만큼 정확하고, 지금까지 제안된 다른 버전보다 적어도 두 배는 빠르다.
빠른지 확실하지 않지만, 다음 사항을 확인하여 원라이너를 수행할 수 있음val^(val>>1)최대 2비트를 켠다.
이는 서명되지 않은 유형에서만 작동함: 에서 전환0상위(논리적 이동)에서는 부호 비트의 복사본으로 이동하는 산술적 우위 이동이 아니라 필수적이다.
#include <bitset>
bool has_compact_bits(unsigned val)
{
return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2;
}
거절하다0 비트 만 수락 (, 정확히1의 연속의그의연그그그그그그그그는는는는는는는는는는는는는는는는는는는는는는는는는), 는리-AND:val0이 아닌이 질문에 대한 기타 답변 수락0빽빽하게
bool has_compact_bits(unsigned val)
{
return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2 and val;
}
C++를 사용하면 다음과 같은 방법으로 팝카운트를 표시할 수 있음std::bitset::count(), 또는 C++20에서 by. C는 여전히 popcnt 또는 그 중 하나가 가능한 대상의 유사한 지시사항에 신뢰성 있게 컴파일할 수 있는 휴대용 방법을 가지고 있지 않다.
CPU는 이를 위한 전용 지침을 매우 빠르게 가지고 있다.PC에서는 BSR/BSF(1985년 80386년에 소개), ARM에서는 CLZ/CTZ이다.
최소값 집합 비트의 인덱스를 찾으려면 1을 사용하여 해당 양만큼 정수를 오른쪽으로 이동하십시오.다른 하나를 사용하여 가장 유의한 세트 비트의 색인을 찾고 정수를 (1u<(bsr+1)--1과 비교하십시오.
불행히도 35년은 하드웨어와 일치하도록 C++ 언어를 업데이트하기에 충분하지 않았다.C++에서 이러한 지침을 사용하려면 본질적인 것이 필요하며, 이는 휴대할 수 없으며, 약간 다른 형식으로 결과를 반환해야 한다.전처리기 사용,#ifdef컴파일러를 검출한 후 적절한 성질을 사용한다.은 MSVC에 있다._BitScanForward_BitScanForward64_BitScanReverse_BitScanReverse64GCC와 땡땡이에서는.__builtin_clz그리고__builtin_ctz.
0 대신 0과 비교하면 일부 작업이 절약된다.
bool has_compact_bits2(int val) {
if (val == 0) return true;
int h = __builtin_clz(val);
// Clear bits to the left
val = (unsigned)val << h;
int l = __builtin_ctz(val);
// Invert
// >>l - Clear bits to the right
return (~(unsigned)val)>>l == 0;
}
다음은 위의 지침보다 적은 하나의 지침으로 나타난다.gcc10 -O3에 x86_64 및 사용:
bool has_compact_bits3(int val) {
if (val == 0) return true;
int h = __builtin_clz(val);
val <<= h;
int l = __builtin_ctz(val);
return ~(val>>l) == 0;
}
Godbolt에서 테스트됨.
다음과 같은 요구 사항을 다시 요약할 수 있다.
- 이전 비트와 다른 비트 수를 N으로 설정(비트를 통해 반복)
- N=2 및 첫 번째 또는 마지막 비트가 0인 경우 대답은 yes이다.
- N=1이면 예(모든 1이 한쪽에 있기 때문에)라고 대답한다.
- 만약 N=0이고 어떤 비트가 0이라면, 당신은 1이 없다. 만약 당신이 그 대답을 예스나 노라고 생각한다면, 당신에게 달려있다.
- 다른 모든 것: 대답은 '아니오'이다.
모든 비트를 뒤져보면 다음과 같이 보일 수 있다.
unsigned int count_bit_changes (uint32_t value) {
unsigned int bit;
unsigned int changes = 0;
uint32_t last_bit = value & 1;
for (bit = 1; bit < 32; bit++) {
value = value >> 1;
if (value & 1 != last_bit {
changes++;
last_bit = value & 1;
}
}
return changes;
}
그러나 이것은 확실히 최적화될 수 있다(예를 들어, 를 중단시킴으로써).for을 반복하다.value도달된0즉, 값 1이 있는 유의한 비트가 더 이상 존재하지 않는다는 것을 의미한다.
할 수 있다).val입력으로:
uint32_t x = val;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
모든 0이 가장 유의한 값보다 낮은 숫자를 구하다1가득 찬
계산도 할 수 있다.y = val & -val최소 1비트를 제외한 모든 부분을 벗긴다.val(예를 들어,7 & -7 == 1그리고12 & -12 == 4).
경고: 다음 기간 동안 실패함val == INT_MIN그래서 이 사건을 따로 처리해야 할 겁니다만, 이 일은 즉시 처리하십시오.
그 다음 오른쪽 시프트y한 위치에 의해, 실제 LSB보다 약간 낮게 하기 위해val, 그리고 에 대해 같은 루틴을 한다.x:
uint32_t y = (val & -val) >> 1;
y |= y >> 1;
y |= y >> 2;
y |= y >> 4;
y |= y >> 8;
y |= y >> 16;
그러면x - y또는x & ~y또는x ^ y전체 길이에 걸쳐 ' '' 비트 마스크를 생성한다.val…에 비유하기만 하면 된다.val을 알아보다val이다.
gcc 빌트인 지침을 사용하여 다음 사항을 확인할 수 있다.
세트 비트 수
되지 않은 x)int__builtin_popcount(x에 에)
x 단위의 1비트 수를 반환한다.
(a - b):
a: 가장 높은 세트 비트(32 - CTZ)의 색인(32 비트는 부호 없는 정수로 32 비트가 있기 때문에 32).
int__builtin_clz(x에 ~ )
가장 유의한 비트 위치에서 시작하여 x 단위로 선행 0비트 수를 반환한다.x가 0이면 결과가 정의되지 않는다.
b: 가장 낮은 설정 비트(CLZ):
int__builtin_clz(x에 ~ )
가장 유의한 비트 위치에서 시작하여 x 단위로 선행 0비트 수를 반환한다.x가 0이면 결과가 정의되지 않는다.
예를 들어, n = 0b0001100110인 경우, 팝카운트를 사용하여 4를 얻지만 인덱스 차이(a - b)는 6을 반환한다.
bool has_contiguous_one_bits(unsigned n) {
return (32 - __builtin_clz(n) - __builtin_ctz(n)) == __builtin_popcount(n);
}
다음과 같이 기록될 수도 있다.
bool has_contiguous_one_bits(unsigned n) {
return (__builtin_popcount(n) + __builtin_clz(n) + __builtin_ctz(n)) == 32;
}
나는 그것이 현재 가장 많이 제시된 대답보다 더 우아하거나 효율적이라고 생각하지 않는다.
return (x & x + (x & -x)) == 0;
다음 어셈블리와 함께:
mov eax, edi
neg eax
and eax, edi
add eax, edi
test eax, edi
sete al
이해하기가 더 쉬울 겁니다
자, 여기 비트 위에 루핑하는 버전이 있다.
template<typename Integer>
inline constexpr bool has_compact_bits(Integer val) noexcept
{
Integer test = 1;
while(!(test & val) && test) test<<=1; // skip unset bits to find first set bit
while( (test & val) && test) test<<=1; // skip set bits to find next unset bit
while(!(test & val) && test) test<<=1; // skip unset bits to find an offending set bit
return !test;
}
처음 두 루프는 첫 번째 콤팩트한 지역을 찾았다.최종 루프는 그 지역 너머에 다른 세트 비트가 있는지 점검한다.
'IT이야기' 카테고리의 다른 글
| Vue.js의 프로펠러에 값이 공급되는지 점검하십시오. (0) | 2022.04.24 |
|---|---|
| jquery로 업데이트할 경우 Vuejs 바인딩이 작동하지 않음 (0) | 2022.04.24 |
| 스티커 헤더 도구 모음 설정 (0) | 2022.04.23 |
| v-for 및 v-model을 사용한 vuex 계산 속성이 포함된 Vue js (0) | 2022.04.23 |
| V-bind 스토어 상태 변경 시 클래스를 업데이트하지 않음 (0) | 2022.04.23 |