비트 조작을 이용하여 64비트 값에서 유일한 세트 비트의 위치를 효율적으로 찾는 방법은?
그냥 내게 타입의 가치가 있다고 말해요.uint64_t옥텟의 수열(1 옥텟 = 8비트)로 볼 수 있습니다. 그uint64_t값은 MSB 위치에 하나의 세트 비트만 포함하는 것으로 알려져 있습니다.그래서.uint64_t값은 다음과 같은 이진 표현 중 하나일 수 있습니다.
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7
00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000 pos = 15
00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000 pos = 23
00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000 pos = 31
00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000 pos = 39
00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 pos = 47
00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 55
10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 63
설정된 비트 위치를 반환하되 설정된 비트가 없으면 0을 반환하는 빠른 함수가 필요합니다.
가능하다면 루프나 분기 없이 하고 싶습니다.
값에 세심하게 설계된 64비트 상수를 곱한 다음 상위 4비트를 마스킹합니다.64비트 곱셈이 빠른 모든 CPU의 경우, 이것이 가능한 한 최적일 것입니다.
int field_set(uint64_t input) {
uint64_t field = input * 0x20406080a0c0e1ULL;
return (field >> 60) & 15;
}
// field_set(0x0000000000000000ULL) = 0
// field_set(0x0000000000000080ULL) = 1
// field_set(0x0000000000008000ULL) = 2
// field_set(0x0000000000800000ULL) = 3
// field_set(0x0000000080000000ULL) = 4
// field_set(0x0000008000000000ULL) = 5
// field_set(0x0000800000000000ULL) = 6
// field_set(0x0080000000000000ULL) = 7
// field_set(0x8000000000000000ULL) = 8
clang은 이를 프레임 설정 및 정리를 세지 않고 세 가지 x86_64 명령어로 구현합니다.
_field_set:
push %rbp
mov %rsp,%rbp
movabs $0x20406080a0c0e1,%rax
imul %rdi,%rax
shr $0x3c,%rax
pop %rbp
retq
다른 입력에 대한 결과는 거의 무작위적입니다.(그러지 마세요.)
이 방법을 7의 값을 반환하도록 확장할 실현 가능한 방법은 없다고 생각합니다.63 범위는 직접적으로(상수의 구조는 허용하지 않음), 결과에 7을 곱하면 결과를 해당 범위로 변환할 수 있습니다.
이 상수가 어떻게 설계되었는지와 관련하여:저는 다음과 같은 관찰을 시작했습니다.
- 부호 없는 곱셈은 대부분의 CPU에서 빠른 연산이므로 유용한 효과를 얻을 수 있습니다.써야지요. :)
- 모든 것에 0을 곱하면 0이 됩니다.이것이 노비트 세트 입력에 대한 원하는 결과와 일치하기 때문에, 우리는 지금까지 잘 하고 있습니다.
- 모든 것에 다음을 곱합니다.
1ULL<<63(즉, "pos=63" 값)은 동일한 값, 즉 0으로만 나타날 수 있습니다. (이 값은 하위 비트를 설정할 수 없으며 변경할 상위 비트도 없습니다.)따라서 이 값이 올바른 결과로 처리될 수 있는 방법을 찾아야 합니다. - 이 값을 올바른 결과로 만드는 편리한 방법은 60비트씩 오른쪽으로 이동하는 것입니다.이렇게 하면 충분히 편리한 표현인 "8"로 바뀝니다.다른 출력은 1~7로 인코딩을 진행할 수 있습니다.
상수에 다른 비트 필드를 각각 곱하는 것은 "위치"와 같은 수의 비트를 왼쪽으로 이동시키는 것과 같습니다.60비트 단위로 오른쪽으로 이동하면 지정된 위치의 왼쪽에 있는 4비트만 결과에 나타납니다.따라서 하나를 제외한 모든 경우를 다음과 같이 만들 수 있습니다.
uint64_t constant = ( 1ULL << (60 - 7) | 2ULL << (60 - 15) | 3ULL << (60 - 23) | 4ULL << (60 - 31) | 5ULL << (60 - 39) | 6ULL << (60 - 47) | 7ULL << (60 - 55) );
지금까지 상수는0x20406080a0c0e0ULL. 그러나 이것은 다음에 대해 올바른 결과를 제공하지 않습니다.pos=63; 이 상수는 짝수이므로 이 상수에 해당 입력을 곱하면 0이 됩니다.최저 비트를 설정해야 합니다(즉,constant |= 1ULL그 사건을 해결하고 우리에게 최종적인 가치를 제공하는 것입니다.0x20406080a0c0e1ULL.
위 구성은 결과를 다르게 인코딩하도록 수정할 수 있습니다.그러나, 의 출력.8는 위에서 설명한 대로 고정되며, 다른 모든 출력은 4비트(즉, 0 ~ 15)에 맞아야 합니다.
여기에 휴대용 솔루션이 있습니다. 그러나 다음과 같은 전문화된 지침을 활용하는 솔루션보다 느립니다.clz(선행 0 카운트).알고리즘의 각 단계마다 그것이 어떻게 작동하는지 설명하는 코멘트를 추가했습니다.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
uint64_t t, c;
t = a - 1; // create mask
c = t >> 63; // correction for zero inputs
t = t + c; // apply zero correction if necessary
t = t & 0x0101010101010101ULL; // mark each byte covered by mask
t = t * 0x0101010101010101ULL; // sum the byte markers in uppermost byte
t = (t >> 53) - 1; // retrieve count and diminish by 1 for bit position
t = t + c; // apply zero correction if necessary
return (int)t;
}
int main (void)
{
int i;
uint64_t a;
a = 0;
printf ("a=%016llx bit_pos=%2d reference_pos=%2d\n", a, bit_pos(a), 0);
for (i = 7; i < 64; i += 8) {
a = (1ULL << i);
printf ("a=%016llx bit_pos=%2d reference_pos=%2d\n",
a, bit_pos(a), i);
}
return EXIT_SUCCESS;
}
이 코드의 출력은 다음과 같습니다.
a=0000000000000000 bit_pos= 0 reference_pos= 0
a=0000000000000080 bit_pos= 7 reference_pos= 7
a=0000000000008000 bit_pos=15 reference_pos=15
a=0000000000800000 bit_pos=23 reference_pos=23
a=0000000080000000 bit_pos=31 reference_pos=31
a=0000008000000000 bit_pos=39 reference_pos=39
a=0000800000000000 bit_pos=47 reference_pos=47
a=0080000000000000 bit_pos=55 reference_pos=55
a=8000000000000000 bit_pos=63 reference_pos=63
x86_64 플랫폼에서 내 컴파일러는 다음과 같이 번역합니다.bit_pos()다음 기계 코드로 입력합니다.
bit_pos PROC
lea r8, QWORD PTR [-1+rcx]
shr r8, 63
mov r9, 0101010101010101H
lea rdx, QWORD PTR [-1+r8+rcx]
and rdx, r9
imul r9, rdx
shr r9, 53
lea rax, QWORD PTR [-1+r8+r9]
ret
[이후 업데이트]
황혼에 의한 대답은 나에게 나의 원래 생각이 불필요하게 복잡하다는 것을 분명히 했습니다.사실, dustwuff의 접근 방식을 사용하면 원하는 기능을 다음과 같이 훨씬 더 간결하게 표현할 수 있습니다.
/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
const uint64_t magic_multiplier =
(( 7ULL << 56) | (15ULL << 48) | (23ULL << 40) | (31ULL << 32) |
(39ULL << 24) | (47ULL << 16) | (55ULL << 8) | (63ULL << 0));
return (int)(((a >> 7) * magic_multiplier) >> 56);
}
합리적인 컴파일러라면 마법 곱셈기를 미리 계산할 것입니다.0x070f171f272f373fULL됩니다. x86_64 대상에 대해 방출된 코드는 다음으로 축소됩니다.
bit_pos PROC
mov rax, 070f171f272f373fH
shr rcx, 7
imul rax, rcx
shr rax, 56
ret
POSIX를 사용할 수 있다면 다음의 기능을 사용합니다.strings.h(아니오)string.h의 위치를 을 반환합니다.!). 최하위 비트 집합(인덱스된 하나)의 위치를 반환하거나 인수가 0인 경우 0을 반환합니다.대부분의 구현 환경에서ffs()인라인화되어 해당 기계 명령어로 컴파일됩니다.bsf 또한 glibc를 가지고 있습니다.ffsll()위해서long long가능하다면 당신의 문제에 훨씬 더 적합한 주장.
값 mod 0x8C는 각 경우에 대해 고유한 값을 산출합니다.
이 값 모드 0x11은 여전히 고유합니다.
표의 두 번째 값은 결과 모드 0x11입니다.
128 9
32768 5
8388608 10
2147483648 0
549755813888 14
140737488355328 2
36028797018963968 4
9223372036854775808 15
따라서 간단한 룩업 테이블로 충분합니다.
int find_bit(uint64_t bit){
int lookup[] = { the seventeen values };
return lookup[ (bit % 0x8C) % 0x11];
}
분기도, 컴파일러 트릭도 없습니다.
완성도를 위해 배열은
{ 31, 0, 47, 15, 55, 0, 0, 7, 23, 0, 0, 0, 39, 63, 0, 0}
기본 제공이 아닌 작업에 대한 알고리즘을 원하는 경우 이렇게 하면 됩니다.1비트 이상 설정된 경우에도 가장 의미 있는 1비트의 비트 수를 산출합니다.검토 중인 비트 범위를 절반으로 반복적으로 나누어 상위 절반에 설정된 비트가 있는지 테스트하고 절반을 새 비트 범위로 사용하면 하위 절반을 새 비트 범위로 사용하여 위치를 줄입니다.
#define TRY_WINDOW(bits, n, msb) do { \
uint64_t t = n >> bits; \
if (t) { \
msb += bits; \
n = t; \
} \
} while (0)
int msb(uint64_t n) {
int msb = 0;
TRY_WINDOW(32, n, msb);
TRY_WINDOW(16, n, msb);
TRY_WINDOW( 8, n, msb);
TRY_WINDOW( 4, n, msb);
TRY_WINDOW( 2, n, msb);
TRY_WINDOW( 1, n, msb);
return msb;
}
C++ 태그는 제거되었지만 C++로 컴파일하여 사용할 수 있으므로 휴대용 C++ 답변이 있습니다.extern C인터페이스:
만약 당신이 2의 거듭제곱을 가지고 있고 당신이 1을 빼면 당신은 그 위치와 같은 설정된 비트의 수를 가진 이진수로 끝납니다.
설정된 비트 수(이진)를 세는 방법1s) Stl의 각 구현에 의해 가장 효율적으로 포장됩니다.std::bitset멤버함수count
사양은 다음과 같습니다.0둘 다를 위해 돌아온0아니면1, 그래서 덧붙였어요.as_specified_pos이 요건을 충족시키기 위해.개인적으로 저는 자연적인 가치를 돌려주는 것을 그냥 두고 싶습니다.64지나가면0차별화할 수 있고, 속도를 낼 수 있습니다.
다음 코드는 매우 휴대성이 뛰어나야 하며 컴파일러 공급업체가 플랫폼별로 최적화했을 가능성이 높습니다.
#include <bitset>
uint64_t pos(uint64_t val)
{
return std::bitset<64>(val-1).count();
}
uint64_t as_specified_pos(uint64_t val)
{
return (val) ? pos(val) : 0;
}
g++가 있는 리눅스에서 나는 다음과 같은 분해된 코드를 받습니다.
0000000000000000 <pos(unsigned long)>:
0: 48 8d 47 ff lea -0x1(%rdi),%rax
4: f3 48 0f b8 c0 popcnt %rax,%rax
9: c3 retq
a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
0000000000000010 <as_specified_pos(unsigned long)>:
10: 31 c0 xor %eax,%eax
12: 48 85 ff test %rdi,%rdi
15: 74 09 je 20 <as_specified_pos(unsigned long)+0x10>
17: 48 8d 47 ff lea -0x1(%rdi),%rax
1b: f3 48 0f b8 c0 popcnt %rax,%rax
20: f3 c3 repz retq
현대 하드웨어에는 이에 대한 전문적인 지침이 있습니다(LZCNT, TZCNT on Intel 프로세서).
대부분의 컴파일러는 쉽게 생성할 수 있는 고유한 특성을 가지고 있습니다.다음 위키백과 페이지를 참조하십시오.
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7..., 그러나 설정된 비트가 없으면 0을 반환합니다.
이것은 첫 번째 비트 또는 비트가 설정되지 않은 경우에도 동일하게 반환됩니다. 그러나 x86_64에서는 bsrq가 수행하는 작업이 정확합니다.
int bsrq_x86_64(uint64_t x){
int ret;
asm("bsrq %0, %1":"=r"(ret):"r"(x));
return ret;
}
그러나 첫 번째 비트가 설정되면 0도 반환됩니다. 여기에는 일정한 시간에 실행되고(루프 또는 분기 없음) 비트가 설정되지 않으면 -1을 반환하는(첫 번째 비트가 설정된 경우와 구별하기 위해) 메서드가 있습니다.
int find_bit(unsigned long long x){
int ret=0,
cmp = (x>(1LL<<31))<<5; //32 if true else 0
ret += cmp;
x >>= cmp;
cmp = (x>(1<<15))<<4; //16 if true else 0
ret += cmp;
x >>= cmp;
cmp = (x>(1<<7))<<3; //8
ret += cmp;
x >>= cmp;
cmp = (x>(1<<3))<<2; //4
ret += cmp;
x >>= cmp;
cmp = (x>(1<<1))<<1; //2
ret += cmp;
x >>= cmp;
cmp = (x>1);
ret += cmp;
x >>= cmp;
ret += x;
return ret-1;
}
기술적으로는 가장 중요한 설정 비트의 위치만 반환합니다.사용되는 플로트 유형에 따라 빠른 역 사각형 또는 다른 비트 트위들링 해킹을 사용하여 더 적은 작업으로 수행할 수 있습니다.
그건 그렇고, 컴파일러 내장을 사용하는 것이 괜찮다면, 그냥 다음과 같이 하면 됩니다.
__builtin_popcountll(n-1)아니면__builtin_ctzll(n)아니면__builtin_ffsll(n)-1
간단한 룩업 솔루션.m=67는 값이 가장 작은 정수입니다.(1<<k)%m모든 것이 다 다르죠for k<m. 사용(파이톤 교환 가능 코드):
lut = [-1]*67
for i in range(0,64) : lut[(1<<i)%67] = i
그리고나서lut[a%67]주는k한다면a = 1<<k.-1값이 사용되지 않습니다.
언급URL : https://stackoverflow.com/questions/32339078/how-to-find-the-position-of-the-only-set-bit-in-a-64-bit-value-using-bit-manipul
'programing' 카테고리의 다른 글
| MySQL Workbench에서 limit 절 제거 (0) | 2023.10.31 |
|---|---|
| 워드프레스에서 PHPSESSID 쿠키 도메인 이름을 변경하는 방법은? (0) | 2023.10.31 |
| XML을 읽을 LINQ (0) | 2023.10.31 |
| 불규칙한 분리기를 위해 팬더 read_csv의 분리기를 더 유연한 wrt 공백으로 만드는 방법은 무엇입니까? (0) | 2023.10.31 |
| 안드로이드 스튜디오를 다운로드하지 않고 안드로이드 SDK를 다운로드하려면 어떻게 해야 합니까? (0) | 2023.10.31 |