C의 정수에서 가장 높은 설정 비트(msb)를 찾는 가장 빠르고 효율적인 방법은 무엇입니까?
정수 n이 있고 최상위 비트의 위치를 알고 싶을 때(즉, 최하위 비트가 오른쪽에 있는 경우 왼쪽 끝 비트인 1의 위치를 알고 싶을 때) 가장 빠르고 효율적인 방법은 무엇입니까?
는 POSIX를 하는 것으로 .ffs()method strings하여 첫 세트비트를하는 문자열이 것 .h의 메서드에서는 첫 번째 세트비트를 찾지만 대응하는 비트가 없는 것 같습니다.fls()★★★★★★ 。
내가 놓치고 있는 확실한 방법이 있을까?
휴대성을 위해 POSIX 기능을 사용할 수 없는 경우는 어떻습니까?
편집: 32비트 아키텍처와 64비트 아키텍처 모두에서 동작하는 솔루션은 어떻습니까(코드 리스트의 대부분은 32비트 int에서만 동작하는 것 같습니다).
-- 빌트인 함수: int __builtin_clz (부호되지 않은 int x)X의 선행 0비트 수를 최대값부터 반환합니다.유효 비트 위치X가 0이면 결과는 정의되지 않습니다. -- 빌트인 함수: int __builtin_clzl (부호되지 않은 길이)인수 유형이 'unsigned'라는 점을 제외하면 '_builtin_clz'와 유사합니다.'오래' -- 빌트인 기능: int __builtin_clzl (긴 길이 서명 없음)인수 유형이 'unsigned'라는 점을 제외하면 '_builtin_clz'와 유사합니다.오래오래.
고급 비트 트위들링 알고리즘이든 단일 명령이든 현재 플랫폼에 맞는 합리적인 효율로 변환되어야 합니다.
입력이 0일 수 있는 경우 유용한 트릭은 다음과 같습니다.__builtin_clz(x | 1) 을 변경하지 않고 낮은 과 같이 됩니다.31★★★★★★에x=0다른 입력에 대한 출력을 변경하지 않습니다.
다른 은 ARM 의 "ARM GCC"와 플랫폼 입니다.__clz(''x86'), ('x86')_lzcnt_u32 를 하고 있는 의 경우,lzcnt주의하세요 (주의하세요.lzcntbsr의 입력에 대해 를 제공합니다0 . 0 ) ) 、 31 lzcnt 、 CPU の )) 。
입력=0은 32는 64는 32는 64는 CLZ는 CLZ는 86은 86은 86은 86은 86은 86은 86은 86은 86은 86은 lzcnt '그럴 때'는bsr에 의해 컴파일러가 플립해야 됩니다.단, 컴파일러는 비트인덱스는 .31-__builtin_clz(x).
('정의되지 않은 결과'는 C Undefined Behavior가 아니라 정의되지 않은 값입니다.명령이 실행되었을 때 행선지 등록기에 있던 것들이야AMD는 이것을 문서화하고 있지만, 인텔은 문서화하고 있지 않습니다만, 인텔의 CPU는 그 동작을 실장하고 있습니다.그러나 이전에 할당한 C 변수에 무엇이 있던 간에, GCC가 C를 asm으로 바꿀 때 일반적으로 그렇게 동작하지 않습니다.'LZCNT의 '출력 의존성'을 깨는 것이 중요한 이유'도 참조해 주십시오.
2^N은 N번째 비트 세트(1 < N)만을 가지는 정수이므로, 가장 높은 세트 비트의 위치(N)를 구하면 그 정수의 정수 로그 베이스 2가 된다.
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObcled
unsigned int v;
unsigned r = 0;
while (v >>= 1) {
r++;
}
이 「명백한」알고리즘은, 모든 사람에게 투과적인 것은 아닙니다만, 최좌단의 비트가 오프가 될 때까지 코드가 1비트씩 반복해 우회전하는 것을 깨닫고, 시프트수를 반환하는 것에 주의해 주세요.또, 복수의 비트가 설정되어 있는 경우에도 동작합니다.그 결과는 항상 최상위 비트에 대한 것입니다.
이 페이지를 아래로 스크롤하면 더 빠르고 복잡한 종류가 있습니다.단, 선두에 0이 많은 숫자를 다루고 있는 것을 알고 있는 경우, C에서는 비트 이동이 비교적 빠르고, 단순한 알고리즘에서는 어레이를 인덱싱할 필요가 없기 때문에 순진한 접근법이 허용 가능한 속도를 제공할 수 있습니다.
메모: 64비트 값을 사용하는 경우, 여분의 클리어 알고리즘을 사용하는 것에 매우 주의해 주세요.대부분의 알고리즘은 32비트 값에서만 정상적으로 동작합니다.
이것은 일종의 정수 로그를 찾는 것과 같습니다.약간 뒤틀리는 요령들이 있지만, 나는 이것을 위해 나만의 도구를 만들었다.물론 목표는 속도이다.
CPU에는 이미 자동 비트 검출기가 있어 정수로 변환에 사용되고 있다는 것을 깨달았습니다.그러니 그걸 써라.
double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness
이 버전은 값을 더블로 캐스팅한 다음 지수를 읽습니다. 이 지수는 비트가 어디에 있었는지 알려줍니다.화려한 시프트와 뺄셈은 IEEE 값에서 적절한 부품을 추출하는 것입니다.
플로트를 사용하는 것이 약간 빠르지만 플로트는 정밀도가 낮기 때문에 처음 24비트 위치만 제공할 수 있습니다.
되지 않은 않고 하려면 , 「C++」를 합니다.memcpy타이핑용 포인터 캐스팅 대신.컴파일러는 효율적으로 인라인화하는 방법을 알고 있습니다.
// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?
double ff=(double)(v|1);
uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;
C99를 합니다.union {double d; uint32_t u[2];};다만, C++ 에서는, 유니언 타입의 펀닝은 일부의 컴파일러에서만 서포트되고 있는 것에 주의해 주세요.ISO C++는 ISO C++를 사용합니다.
이는 보통 선행 제로의 계수 명령 플랫폼 고유의 고유값보다 느리지만 휴대용 ISO C에는 이러한 기능이 없습니다. 제로 명령이만, 그 중으로 CPU로 할 수 .double 수 를 들어 FP의 경우PC는 스토어/새로고침이 필요하며 일반적으로 로드히트 스토어 스톨을 일으킵니다.
알고리즘은 SIMD를 가 적기 에 SIMD이 될 수.SIMD의 CPU 수가 적기 때문입니다.lzcntx86은 AVX512에서만 이러한 명령을 받았습니다.CD
이 방법은 최고의 퍼포먼스(예를 들어 비트보드를 포함한 보드 게임 AI를 작성하는 경우)가 절대적으로 필요한 경우에만 사용할 수 있지만, 가장 효율적인 해결책은 인라인 ASM을 사용하는 것입니다.설명에 대한 코드는 이 블로그 투고의 Optimizations 섹션을 참조하십시오.
[...],
bsrl어셈블리 명령은 최상위 비트의 위치를 계산합니다.이렇게 '이렇게 하다'를 할 수 .asm★★★★★★★★asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
x86 및 게임을 인라인 어셈블러용으로 사용하고 있는 경우 인텔은 명령어("비트 스캔 리버스")를 제공합니다.일부 x86에서는 고속입니다(다른 x86에서는 마이크로코딩 완료).매뉴얼:
소스 오퍼랜드에서 최상위 세트비트(1비트)를 검색합니다.최상위 1비트가 발견되면 해당 비트인덱스는 수신처 오퍼랜드에 저장됩니다.소스 오퍼랜드는 레지스터 또는 메모리 위치일 수 있으며, 대상 오퍼랜드는 레지스터입니다.비트 인덱스는 소스 오퍼랜드의 비트 0에서 부호 없는 오프셋입니다.컨텐츠 소스 피연산자가 0인 경우 대상 피연산자의 컨텐츠는 정의되지 않습니다.
(전원) 에 하고 있는 는 같은 PC가 있습니다.cntlz('이행') 이행복하다
gcc 코드 예시:
#include <iostream>
int main (int,char**)
{
int n=1;
for (;;++n) {
int msb;
asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
std::cout << n << " : " << msb << std::endl;
}
return 0;
}
이 인라인 어셈블러 튜토리얼도 참조해 주세요.이 튜토리얼에서는 (섹션 9.4)이 루프 코드보다 상당히 빠릅니다.
unsigned int
msb32(register unsigned int x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return(x & ~(x >> 1));
}
등록기 1개, 지시서 13개믿거나 말거나, 이것은 보통 위에서 언급한 선형 시간으로 동작하는 BSR 명령보다 빠릅니다.이것은 로그 타임입니다.
http://aggregate.org/MAGIC/ 에서 #Most%20Significant%201%20 비트
이것은 번개처럼 빨라야 합니다.
int msb(unsigned int v) {
static const int pos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v = (v >> 1) + 1;
return pos[(v * 0x077CB531UL) >> 27];
}
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Debruin 기법은 입력이 이미 2의 거듭제곱일 때만 사용해야 합니다.을 사용하다입력의 의 Debruin보다 더._BitScanReverse모든 프로세서에서 사용할 수 있습니다. 「 」입니다._BitScanReverse(또는 컴파일러로 불리는 것이 무엇이든) 가장 빠릅니다(특정 CPU에서는 마이크로 코딩이 가능합니다).
고유함수가 선택사항이 아닌 경우 일반적인 입력을 처리하기 위한 최적의 소프트웨어 솔루션이 여기에 있습니다.
u8 inline log2 (u32 val) {
u8 k = 0;
if (val > 0x0000FFFFu) { val >>= 16; k = 16; }
if (val > 0x000000FFu) { val >>= 8; k |= 8; }
if (val > 0x0000000Fu) { val >>= 4; k |= 4; }
if (val > 0x00000003u) { val >>= 2; k |= 2; }
k |= (val & 2) >> 1;
return k;
}
이 버전은 다른 대부분의 응답과 달리 마지막에 Debruin 룩업이 필요하지 않습니다.제자리에 있는 위치를 계산합니다.
단, 테이블이 바람직할 수 있습니다.반복 호출을 반복하면 테이블의 속도 향상에 따라 캐시 미스 위험이 희미해집니다.
u8 kTableLog2[256] = {
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};
u8 log2_table(u32 val) {
u8 k = 0;
if (val > 0x0000FFFFuL) { val >>= 16; k = 16; }
if (val > 0x000000FFuL) { val >>= 8; k |= 8; }
k |= kTableLog2[val]; // precompute the Log2 of the low byte
return k;
}
이렇게 하면 여기에 나와 있는 소프트웨어 응답 중 최고의 throughput을 얻을 수 있지만, 가끔 호출하는 경우에는 첫 번째 스니펫과 같은 테이블이 없는 솔루션을 선호합니다.
C에 비트 조작 기능을 추가하는 제안이 있습니다.특히 선두의 0은 가장 높은 비트 세트를 찾는 데 도움이 됩니다.http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2827.htm#design-bit-leading.trailing.zeroes.ones 를 참조해 주세요.
가능한 한 빌트인으로서 실장될 것으로 기대되고 있기 때문에, 효율적인 방법인 것을 확인해 주세요.
에 C합니다(C++).std::countl_zero 참조)
Kaz Kylheku 여기
63비트 번호(gcc x86_64의 긴 타입)를 넘는 것에 대해서, 부호 비트를 피해, 2개의 어프로치를 벤치마크 했습니다.
(이 "가장 높은 비트 찾기"가 필요한 일이 있습니다.)
데이터 기반 바이너리 검색을 구현했습니다(위 답변 중 하나에 근거합니다).또한 완전히 풀린 Decision Tree를 수작업으로 구현했습니다.이것은 바로 피연산자가 있는 코드입니다.루프도 없고 테이블도 없어요
Decision Tree(highest_bit_unrolled)는 이진 검색에 명시적 테스트가 있는 n = 0 경우를 제외하고 69% 더 빠르게 벤치마킹되었습니다.
바이너리 검색의 0 케이스에 대한 특수 테스트는 특수 테스트가 없는 Decision Tree보다 48% 빠릅니다.
컴파일러, 머신: (GCC 4.5.2, -O3, x86-64, 2867Mhz 인텔 Core i5).
int highest_bit_unrolled(long long n)
{
if (n & 0x7FFFFFFF00000000) {
if (n & 0x7FFF000000000000) {
if (n & 0x7F00000000000000) {
if (n & 0x7000000000000000) {
if (n & 0x4000000000000000)
return 63;
else
return (n & 0x2000000000000000) ? 62 : 61;
} else {
if (n & 0x0C00000000000000)
return (n & 0x0800000000000000) ? 60 : 59;
else
return (n & 0x0200000000000000) ? 58 : 57;
}
} else {
if (n & 0x00F0000000000000) {
if (n & 0x00C0000000000000)
return (n & 0x0080000000000000) ? 56 : 55;
else
return (n & 0x0020000000000000) ? 54 : 53;
} else {
if (n & 0x000C000000000000)
return (n & 0x0008000000000000) ? 52 : 51;
else
return (n & 0x0002000000000000) ? 50 : 49;
}
}
} else {
if (n & 0x0000FF0000000000) {
if (n & 0x0000F00000000000) {
if (n & 0x0000C00000000000)
return (n & 0x0000800000000000) ? 48 : 47;
else
return (n & 0x0000200000000000) ? 46 : 45;
} else {
if (n & 0x00000C0000000000)
return (n & 0x0000080000000000) ? 44 : 43;
else
return (n & 0x0000020000000000) ? 42 : 41;
}
} else {
if (n & 0x000000F000000000) {
if (n & 0x000000C000000000)
return (n & 0x0000008000000000) ? 40 : 39;
else
return (n & 0x0000002000000000) ? 38 : 37;
} else {
if (n & 0x0000000C00000000)
return (n & 0x0000000800000000) ? 36 : 35;
else
return (n & 0x0000000200000000) ? 34 : 33;
}
}
}
} else {
if (n & 0x00000000FFFF0000) {
if (n & 0x00000000FF000000) {
if (n & 0x00000000F0000000) {
if (n & 0x00000000C0000000)
return (n & 0x0000000080000000) ? 32 : 31;
else
return (n & 0x0000000020000000) ? 30 : 29;
} else {
if (n & 0x000000000C000000)
return (n & 0x0000000008000000) ? 28 : 27;
else
return (n & 0x0000000002000000) ? 26 : 25;
}
} else {
if (n & 0x0000000000F00000) {
if (n & 0x0000000000C00000)
return (n & 0x0000000000800000) ? 24 : 23;
else
return (n & 0x0000000000200000) ? 22 : 21;
} else {
if (n & 0x00000000000C0000)
return (n & 0x0000000000080000) ? 20 : 19;
else
return (n & 0x0000000000020000) ? 18 : 17;
}
}
} else {
if (n & 0x000000000000FF00) {
if (n & 0x000000000000F000) {
if (n & 0x000000000000C000)
return (n & 0x0000000000008000) ? 16 : 15;
else
return (n & 0x0000000000002000) ? 14 : 13;
} else {
if (n & 0x0000000000000C00)
return (n & 0x0000000000000800) ? 12 : 11;
else
return (n & 0x0000000000000200) ? 10 : 9;
}
} else {
if (n & 0x00000000000000F0) {
if (n & 0x00000000000000C0)
return (n & 0x0000000000000080) ? 8 : 7;
else
return (n & 0x0000000000000020) ? 6 : 5;
} else {
if (n & 0x000000000000000C)
return (n & 0x0000000000000008) ? 4 : 3;
else
return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
}
}
}
}
}
int highest_bit(long long n)
{
const long long mask[] = {
0x000000007FFFFFFF,
0x000000000000FFFF,
0x00000000000000FF,
0x000000000000000F,
0x0000000000000003,
0x0000000000000001
};
int hi = 64;
int lo = 0;
int i = 0;
if (n == 0)
return 0;
for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
int mi = lo + (hi - lo) / 2;
if ((n >> mi) != 0)
lo = mi;
else if ((n & (mask[i] << lo)) != 0)
hi = mi;
}
return lo + 1;
}
빠르고 더러운 테스트 프로그램:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int highest_bit_unrolled(long long n);
int highest_bit(long long n);
main(int argc, char **argv)
{
long long n = strtoull(argv[1], NULL, 0);
int b1, b2;
long i;
clock_t start = clock(), mid, end;
for (i = 0; i < 1000000000; i++)
b1 = highest_bit_unrolled(n);
mid = clock();
for (i = 0; i < 1000000000; i++)
b2 = highest_bit(n);
end = clock();
printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);
printf("time1 = %d\n", (int) (mid - start));
printf("time2 = %d\n", (int) (end - mid));
return 0;
}
-O2만 사용하면 차이가 커집니다.Decision Tree는 거의 4배 더 빠릅니다.
또, 순진한 비트의 시프트 코드에 대해서도 벤치마크를 실시했습니다.
int highest_bit_shift(long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}
이는 예상대로 적은 숫자에 대해서만 빠른 속도입니다.n == 1에 대해 가장 높은 비트가 1이라는 것을 확인할 때 80% 이상 더 빨리 벤치마크를 수행했습니다.그러나 63비트 공간에서 무작위로 선택한 숫자의 절반이 63비트 세트를 가지고 있습니다!
입력 0x3FFFFFFFF에서는 Decision Tree 버전이 1보다 상당히 빠르고 비트시프터보다 1120%(12.2배) 빠릅니다.
또, GCC 빌트인에 대해서 Decision Tree를 벤치마킹 해, 같은 숫자에 대해서 반복하는 것이 아니라, 복수의 입력을 조합해 시험합니다.분기 예측이 고착되어 있을 수도 있고 반복 시 인위적으로 빨라지는 비현실적인 캐싱 시나리오도 있을 수 있습니다.
조쉬의 기준을 확장하면...다음과 같이 clz를 개선할 수 있습니다.
/***************** clz2 ********************/
#define NUM_OF_HIGHESTBITclz2(a) ((a) \
? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
: 0)
asm:에 대해서는 bsr과 bsrl이 있습니다(이것은 "롱" 버전입니다).보통 게 더 빠를 수도 있어요.
와, 정말 많은 답변이 있었네요.나는 오래된 질문에 대답한 것에 대해 미안하지 않다.
int result = 0;//could be a char or int8_t instead
if(value){//this assumes the value is 64bit
if(0xFFFFFFFF00000000&value){ value>>=(1<<5); result|=(1<<5); }//if it is 32bit then remove this line
if(0x00000000FFFF0000&value){ value>>=(1<<4); result|=(1<<4); }//and remove the 32msb
if(0x000000000000FF00&value){ value>>=(1<<3); result|=(1<<3); }
if(0x00000000000000F0&value){ value>>=(1<<2); result|=(1<<2); }
if(0x000000000000000C&value){ value>>=(1<<1); result|=(1<<1); }
if(0x0000000000000002&value){ result|=(1<<0); }
}else{
result=-1;
}
이 답변은 다른 답변과 상당히 유사합니다.아, 그렇군요.
당신의 질문은 부호 없는 정수가 아닌 정수(아래 v라고 함)에 대한 것이라고 생각합니다.
int v = 612635685; // whatever value you wish
unsigned int get_msb(int v)
{
int r = 31; // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.
while (!(v & 0x80000000) && r--) { // mask of the highest bit
v <<= 1; // multiply integer by 2.
}
return r; // will even return -1 if no bit was set, allowing error catch
}
부호를 고려하지 않고 작동시키려면 루프 앞에 'v <<= 1;'을 추가하면 됩니다(그리고 그에 따라 r 값을 30으로 변경).제가 잊은 게 있으면 알려주세요.테스트해 본 적은 없지만 잘 될 거예요.
이것은 커 보이지만 블루스미스의 루프 감사에 비하면 매우 빠르게 작동합니다.
int Bit_Find_MSB_Fast(int x2)
{
long x = x2 & 0x0FFFFFFFFl;
long num_even = x & 0xAAAAAAAA;
long num_odds = x & 0x55555555;
if (x == 0) return(0);
if (num_even > num_odds)
{
if ((num_even & 0xFFFF0000) != 0) // top 4
{
if ((num_even & 0xFF000000) != 0)
{
if ((num_even & 0xF0000000) != 0)
{
if ((num_even & 0x80000000) != 0) return(32);
else
return(30);
}
else
{
if ((num_even & 0x08000000) != 0) return(28);
else
return(26);
}
}
else
{
if ((num_even & 0x00F00000) != 0)
{
if ((num_even & 0x00800000) != 0) return(24);
else
return(22);
}
else
{
if ((num_even & 0x00080000) != 0) return(20);
else
return(18);
}
}
}
else
{
if ((num_even & 0x0000FF00) != 0)
{
if ((num_even & 0x0000F000) != 0)
{
if ((num_even & 0x00008000) != 0) return(16);
else
return(14);
}
else
{
if ((num_even & 0x00000800) != 0) return(12);
else
return(10);
}
}
else
{
if ((num_even & 0x000000F0) != 0)
{
if ((num_even & 0x00000080) != 0)return(8);
else
return(6);
}
else
{
if ((num_even & 0x00000008) != 0) return(4);
else
return(2);
}
}
}
}
else
{
if ((num_odds & 0xFFFF0000) != 0) // top 4
{
if ((num_odds & 0xFF000000) != 0)
{
if ((num_odds & 0xF0000000) != 0)
{
if ((num_odds & 0x40000000) != 0) return(31);
else
return(29);
}
else
{
if ((num_odds & 0x04000000) != 0) return(27);
else
return(25);
}
}
else
{
if ((num_odds & 0x00F00000) != 0)
{
if ((num_odds & 0x00400000) != 0) return(23);
else
return(21);
}
else
{
if ((num_odds & 0x00040000) != 0) return(19);
else
return(17);
}
}
}
else
{
if ((num_odds & 0x0000FF00) != 0)
{
if ((num_odds & 0x0000F000) != 0)
{
if ((num_odds & 0x00004000) != 0) return(15);
else
return(13);
}
else
{
if ((num_odds & 0x00000400) != 0) return(11);
else
return(9);
}
}
else
{
if ((num_odds & 0x000000F0) != 0)
{
if ((num_odds & 0x00000040) != 0)return(7);
else
return(5);
}
else
{
if ((num_odds & 0x00000004) != 0) return(3);
else
return(1);
}
}
}
}
}
연속적인 근사치를 사용한 C 버전:
unsigned int getMsb(unsigned int n)
{
unsigned int msb = sizeof(n) * 4;
unsigned int step = msb;
while (step > 1)
{
step /=2;
if (n>>msb)
msb += step;
else
msb -= step;
}
if (n>>msb)
msb++;
return (msb - 1);
}
장점: 루프 수는 항상 같기 때문에 지정된 수에 관계없이 실행 시간이 일정합니다.('unsigned int' 사용 시 4루프)
또 다른 포스터는 바이트 단위 룩업을 사용한 룩업 테이블을 제공했습니다.(256개의 룩업엔트리가 아닌 32K의 메모리 비용으로) 성능을 향상시키고 싶은 경우 C#7 for에 있는15비트 룩업테이블을 사용하는 솔루션이 있습니다.네트워크
이치노에 이를 되지 않는 합니다.Marshal.AllocHGlobal보다시피 퍼포먼스를 최대화하기 위해 예 전체가 네이티브로 기술되어 있습니다.
readonly static byte[] msb_tab_15;
// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
var p = new byte[0x8000];
for (byte n = 0; n < 16; n++)
for (int c = (1 << n) >> 1, i = 0; i < c; i++)
p[c + i] = n;
msb_tab_15 = p;
}
테이블은 위의 코드를 사용하여 한 번만 초기화해야 합니다.읽기 전용이므로 단일 글로벌 복사본을 공유하여 동시에 액세스할 수 있습니다.이 표를 사용하면 다양한 정수 폭(8, 16, 32 및 64비트)에 대한 정수2 로그를 빠르게 검색할 수 있습니다.
것에 해 주세요.0 비트되어 있지 않은 에는, 「최고 세트 비트」의 .-1이 구분은 아래 코드에서 0-값의 상위 단어를 적절하게 처리하기 위해 필요합니다.자세한 내용은 생략하고 각 정수 프리미티브의 코드를 다음에 나타냅니다.
ulong(64비트) 버전
/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 0x40) - 1; // handles cases v==0 and MSB==63
int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}
uint(32비트) 버전
/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
if ((int)v <= 0)
return (int)((v >> 26) & 0x20) - 1; // handles cases v==0 and MSB==31
int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}
상기의 다양한 과부하
public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];
이는 에서 최고의 성능을 발휘하는 완전하고 효과적인 솔루션입니다.NET 4.7.2는 다양한 대안을 위해 특수 성능 테스트 하니스와 비교했습니다.이들 중 일부는 다음과 같습니다.테스트 파라미터는 모든 65비트위치의 균일한 밀도(0... 31/63+값)였습니다.0(결과 -1이 생성됩니다).목표 인덱스 위치 아래의 비트가 무작위로 채워졌습니다.테스트는 x64 한정 릴리스 모드로, JIT 최적화가 유효하게 되어 있습니다.
여기까지가 저의 공식 답변입니다.다음은 상기 코드의 퍼포먼스와 정확성을 검증하기 위해 실시한 테스트와 관련된 대체 테스트 응시자를 위한 간단한 메모와 소스 코드 링크입니다.
Tab16A로 코딩된 위에 제공된 버전은 여러 번의 실행에서 일관된 승자였습니다.액티브한 작업/스크래치 형식의 이러한 다양한 후보자는, 여기, 여기, 그리고 여기 있습니다.
후보 1명HighestOne_Tab16A 622,496후보 2명HighestOne_Tab16C 628,234후보 3명HighestOne_Tab8A 649,1464명의 후보HighestOne_Tab8B 656,8475명의 후보HighestOne_Tab16B 657,1476명의 후보HighestOne_Tab16D 659,6507 _ highest _ 1 bit _관리 대상 외HighestOne_U 702,9008 de_Brujn.Index OfMSB 709,6729 _ old _ 2 .Highest One_Old2 715,81010 _ test _ A 。HighestOne8 757,18811 _ old _ 1 .HighestOne_Old1 757,92512 _ test _ A 。Highest One5 (안전하지 않음)760,38713 _ test _ B .HighestOne8 (안전하지 않음) 763,90414 _ test _ A .HighestOne3(안전하지 않음) 766,43315 _ test _ A .Highest One 1 (안전하지 않음)767,32116 _ test _ A .HighestOne4(안전하지 않음) 771,70217 _ test _ B .HighestOne2(안전하지 않음) 772,13618 _test_B.Highest One 1 (안전하지 않음)772,52719 _ test _ B .HighestOne3(안전하지 않음) 774,14020 _ test _ A 。HighestOne7 (안전하지 않음) 774,58121 _ test _ B .HighestOne7 (안전하지 않음)775,46322 _ test _ A .HighestOne2(안전하지 않음) 776,86523명의 지원자HighestOne_NoTab 777,69824 _ test _ B 。HighestOne6(안전하지 않음) 779,48125 _ test _ A .HighestOne6 (안전하지 않음) 781,55326 _ test _ B 。Highest One4 (안전하지 않음)785,50427_test_B.HighestOne5(안전하지 않음) 789,79728 _ test _ A .HighestOne0(안전하지 않음) 809,56629 _ test _ B .Highest One0 (안전하지 않음)814,99030 _ highest _ 1 bit 。Highest One 824,34530 _bitarray_ext.RtlFindMostSignificantBit 894,06931명의 지원자HighestOne_Naive 898,865
주목할 만한 것은 의 끔찍한 퍼포먼스이다.ntdll.dll!RtlFindMostSignificantBitP/Invoke 경 :
[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);
매우 유감입니다.실제 기능은 다음과 같습니다.
RtlFindMostSignificantBit:
bsr rdx, rcx
mov eax,0FFFFFFFFh
movzx ecx, dl
cmovne eax,ecx
ret
이 다섯 줄에서 비롯되는 성능 저하를 상상할 수 없기 때문에 관리/원어민 전환 패널티가 원인일 것입니다.및 64KB)테 32KB(또는 64KB) 테 32KB(또는 64KB) the 32KB the 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 는 the the the the the the the the the the the the the the the the the the the the the theshort (및128 (256 바이트의 다이렉트 (16 바이트) 。byte8-bit)룩업테이블.(8-bit) 룩업테이블은 16비트룩업보다 했지만, 후자가 일관되게 이것을.
public static int HighestOne_Tab8A(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;
int j;
j = /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
return j + msb_tab_8[v >> j];
}
마지막으로 지적할 것은 나의 deBrujn 방식이 더 나아지지 않았다는 것에 꽤 놀랐다는 것이다.이것은 내가 이전에 자주 사용했던 방법이다.
const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
N_bsr64 = 0x03F79D71B4CB0A89;
readonly public static sbyte[]
bsf64 =
{
63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5,
},
bsr64 =
{
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63,
};
public static int IndexOfLSB(ulong v) =>
v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;
public static int IndexOfMSB(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;
v |= v >> 1; v |= v >> 2; v |= v >> 4; // does anybody know a better
v |= v >> 8; v |= v >> 16; v |= v >> 32; // way than these 12 ops?
return bsr64[(v * N_bsr64) >> 58];
}
이 SO 질문에서는 deBrujn 메서드가 얼마나 우수하고 훌륭한지에 대해 많은 논의가 이루어지고 있으며, 저는 이에 동의하는 경향이 있었습니다.deBrujn과 direct lookup table 메서드(가장 빠른 것으로 판명)는 모두 테이블룩업을 해야 하고 브랜치도 매우 적지만 64비트 곱셈 연산도 deBrujn만이 있다고 생각합니다.테스트만 했어요.IndexOfMSB이 아닌 --deBrujn의 기능IndexOfLSB하지만 후자의 경우 조작이 적기 때문에 (위 참조) 훨씬 더 좋은 기회가 될 것으로 기대하며 LSB를 위해 계속 사용할 것입니다.
어때
int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}
?
이 질문이 매우 오래된 것은 알지만, MSB() 함수를 직접 구현해 본 결과, 여기 및 다른 웹사이트에서 제공되는 대부분의 솔루션이 효율성에 대한 개인적인 정의상 가장 효율적인 것은 아니라는 것을 알게 되었습니다(아래 업데이트 참조).이유는 다음과 같습니다.
대부분의 솔루션(특히 오른쪽에서 왼쪽으로 선형 스캔을 하는 일종의 이진 검색 체계 또는 순진한 접근 방식을 사용하는 솔루션)은 임의의 이진 숫자에 대해 매우 긴 0 시퀀스로 시작하는 경우가 많지 않다는 사실을 무시하는 것처럼 보인다.실제로 모든 비트 폭의 경우 모든 정수의 절반은 1로 시작하고 4분의 1은 01로 시작합니다.무슨 말인지 알겠어?가장 유의한 비트 위치에서 시작하여 가장 유의하지 않은 비트 위치(왼쪽에서 오른쪽)로 이어지는 선형 스캔은 언뜻 보기에는 "선형"이 아닙니다.
어떤 비트폭에서도 테스트해야 할 평균 비트 수는 최대 2비트임을 알1 수 있습니다.이것은, 비트수(!)에 대해서, 상각 후의 시간의 복잡도를 O(1)로 환산합니다.
물론 최악의 경우는 여전히 O(n)로 바이너리 검색과 같은 접근법에서 얻을 수 있는 O(log(n)보다 더 나쁘지만, 최악의 경우는 거의 없기 때문에 대부분의 응용 프로그램에서는 무시할 수 있습니다(Update: not surchy:몇 개일 수도 있지만 가능성이 높을 수 있습니다(아래 업데이트 참조).
다음은 제가 생각해낸 "naughve" 접근법입니다. 적어도 제 머신에서는 대부분의 다른 접근법보다 우선합니다(32비트 ints에 대한 검색 스킴은 항상 log(32) = 5단계를 필요로2 하는 반면, 이 바보 같은 알고리즘은 평균 2단계 미만이 필요합니다). 순수 C가 아니라 C++입니다.
template <typename T>
auto msb(T n) -> int
{
static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
"msb<T>(): T must be an unsigned integral type.");
for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
{
if ((n & mask) != 0)
return i;
}
return 0;
}
업데이트: 여기에 기재한 내용은 모든 비트 조합이 동일한 임의의 정수에 대해 완전히 해당되지만(내 속도 테스트에서는 32비트 정수의 MSB를 확인하는 데 걸리는 시간을 측정했을 뿐), 일반적으로 이러한 함수가 호출되는 실제 정수는 다른 패턴을 따릅니다.예를 들어 이 함수는 객체 크기가 2의 거듭제곱인지 또는 객체 크기보다 크거나 같은 2의 다음 거듭제곱을 찾기 위해 사용됩니다.MSB를 사용하는 대부분의 응용 프로그램에는 정수가 나타낼 수 있는 최대 수보다 훨씬 작은 숫자가 포함되어 있습니다(개체 크기는 size_t의 모든 비트를 사용하는 경우가 거의 없습니다).이 경우 실제로는 바이너리 검색 접근법보다 성능이 떨어집니다.따라서 모든 정수를 통해 보다 빠르게 루핑할 수 있지만 아마 후자가 더 나을 것입니다.
TL;DR: 실생활 정수는 아마도 이 단순한 알고리즘의 최악의 경우로 치우쳐 있을 것입니다.그 때문에, 실제로는 임의의 정수에 대해서 상각 O(1)가 되어 있어도, 최종적으로는 성능이 저하됩니다.
1인수는 다음과 같습니다(대략적인 드래프트).n은 비트 수(비트 폭)입니다.n비트로 나타낼 수 있는 정수는 총 2개입니다n.1로 시작하는 정수는 2개입니다n - 1(처음 1은 고정, 나머지 n - 1비트는 무엇이든 상관 없음).이러한 정수는 MSB를 결정하기 위해 루프를 한 번만 개입시키면 됩니다.또한n - 2 01로 시작하는 정수는 2회, 001로n - 3 시작하는 정수는 2회, 반복은 3회 등입니다.
가능한 모든 정수에 대해 필요한 모든 반복 횟수를 합산하여 총 정수 수인 2로n 나누면 n비트 정수의 MSB를 결정하는 데 필요한 평균 반복 횟수를 얻을 수 있습니다.
(1 * 2n - 1 + 2 * 2n - 2 + 3 * 2n - 3 + ... + n ) / 2n
이 일련의 평균 반복은 실제로 수렴되며 무한대로 향하는 n에 대해 2의 제한이 있습니다.
따라서 순진한 왼쪽에서 오른쪽으로 알고리즘은 실제로 임의의 수의 비트에 대해 상각된 상수 시간 복잡도 O(1)를 가집니다.
이 페이지에서 현재 제공되는 알고리즘의 몇 가지(간단한) 벤치마크를 소개합니다.
알고리즘은 부호 없는 int의 모든 입력에 대해 테스트되지 않았습니다.따라서 어떤 것을 맹목적으로 사용하기 전에 먼저 그것을 확인합니다.
machine clz(_builtin_clz)와 asm이 가장 잘 작동합니다.asm은 clz보다 더 빠른 것 같습니다.단순한 벤치마크 때문일 수도 있습니다.
//////// go.c ///////////////////////////////
// compile with: gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/***************** math ********************/
#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */ \
((unsigned) log2(a)) /* thus: do not use if a <= 0 */
#define NUM_OF_HIGHESTBITmath(a) ((a) \
? (1U << POS_OF_HIGHESTBITmath(a)) \
: 0)
/***************** clz ********************/
unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */
#define NUM_OF_HIGHESTBITclz(a) ((a) \
? (1U << POS_OF_HIGHESTBITclz(a)) \
: 0)
/***************** i2f ********************/
double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)
#define NUM_OF_HIGHESTBITi2f(a) ((a) \
? (1U << POS_OF_HIGHESTBITi2f(a)) \
: 0)
/***************** asm ********************/
unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)
#define NUM_OF_HIGHESTBITasm(a) ((a) \
? (1U << POS_OF_HIGHESTBITasm(a)) \
: 0)
/***************** bitshift1 ********************/
#define NUM_OF_HIGHESTBITbitshift1(a) (({ \
OUT = a; \
OUT |= (OUT >> 1); \
OUT |= (OUT >> 2); \
OUT |= (OUT >> 4); \
OUT |= (OUT >> 8); \
OUT |= (OUT >> 16); \
}), (OUT & ~(OUT >> 1))) \
/***************** bitshift2 ********************/
int POS[32] = {0, 1, 28, 2, 29, 14, 24, 3,
30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
#define POS_OF_HIGHESTBITbitshift2(a) (({ \
OUT = a; \
OUT |= OUT >> 1; \
OUT |= OUT >> 2; \
OUT |= OUT >> 4; \
OUT |= OUT >> 8; \
OUT |= OUT >> 16; \
OUT = (OUT >> 1) + 1; \
}), POS[(OUT * 0x077CB531UL) >> 27])
#define NUM_OF_HIGHESTBITbitshift2(a) ((a) \
? (1U << POS_OF_HIGHESTBITbitshift2(a)) \
: 0)
#define LOOPS 100000000U
int main()
{
time_t start, end;
unsigned ui;
unsigned n;
/********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/
printf("math\n");
for (ui = 0U; ui < 18; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui));
printf("\n\n");
printf("clz\n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui));
printf("\n\n");
printf("i2f\n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui));
printf("\n\n");
printf("asm\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui));
}
printf("\n\n");
printf("bitshift1\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
}
printf("\n\n");
printf("bitshift2\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
}
printf("\n\nPlease wait...\n\n");
/************************* Simple clock() benchmark ******************/
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITmath(ui);
end = clock();
printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITclz(ui);
end = clock();
printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITi2f(ui);
end = clock();
printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITasm(ui);
end = clock();
printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift1(ui);
end = clock();
printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift2(ui);
end = clock();
printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n");
return EXIT_SUCCESS;
}
바이너리 검색의 일종으로, 모든 종류의 (부정되지 않은!) 정수 타입으로 동작합니다.
#include <climits>
#define UINT (unsigned int)
#define UINT_BIT (CHAR_BIT*sizeof(UINT))
int msb(UINT x)
{
if(0 == x)
return -1;
int c = 0;
for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
if(static_cast<UINT>(x >> i))
{
x >>= i;
c |= i;
}
return c;
}
완료하려면:
#include <climits>
#define UINT unsigned int
#define UINT_BIT (CHAR_BIT*sizeof(UINT))
int lsb(UINT x)
{
if(0 == x)
return -1;
int c = UINT_BIT-1;
for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
if(static_cast<UINT>(x << i))
{
x <<= i;
c ^= i;
}
return c;
}
c99는 우리에게 주어졌습니다.이것은 모든 특별한 소스를 필요로 하지 않는다.log2구현에 대해 설명합니다.의 '보다 낫다'를 할 수 .log2뭇매를 맞다
const auto n = 13UL;
const auto Index = (unsigned long)log2(n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)
안n0UL또한 다음과 같은 이유로 인해 주의해야 합니다.
is is가 반환되고 FE_DIVBYZERO가 발생합니다.
는 그 를 썼습니다.Index로로 합니다.ULONG_MAX여기: https://ideone.com/u26vsi
일시적 gcc의 유일한 답변에 대한 시각적 결과는 다음과 같습니다.
const auto n = 13UL;
unsigned long Index;
_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)
의 문서에는 다음과 같이 기술되어 있습니다.Index 말합니다
처음 발견된 세트 비트(1)의 비트 위치와 함께 로드됩니다.
있는은 만약의 경우입니다.n0UL로 설정되어 있습니다.n1UL, 은, 지만이이 of of of of of of of of of . . 、 . 、 . . . but 。n0UL을 사용하다
세트 비트를 찾을 수 없는 경우 0
바람직한 「」와 , 「」를 참조해 주세요.log2의 구현은 해야 합니다.Index이 경우 플래그가 지정된 값으로 이동합니다. 또 다시 써봤습니다.ULONG_MAX이 플래그 값에 대해서는, http://rextester.com/GCU61409 를 참조해 주세요.
위의 답변에서 알 수 있듯이 가장 중요한 비트를 판별하는 방법은 여러 가지가 있습니다.단, 또한 지적했듯이 메서드는 32비트 또는 64비트 레지스터에 고유할 수 있습니다.stanford.edu bitacks 페이지에는 32비트 컴퓨팅과 64비트 컴퓨팅 모두에 대응하는 솔루션이 있습니다.약간의 작업만으로도 MSB를 획득하기 위한 견고한 교차 아키텍처 접근 방식을 제공할 수 있습니다.64비트 및 32비트 컴퓨터에서 컴파일/작업한 솔루션은 다음과 같습니다.
#if defined(__LP64__) || defined(_LP64)
# define BUILD_64 1
#endif
#include <stdio.h>
#include <stdint.h> /* for uint32_t */
/* CHAR_BIT (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif /* CHAR_BIT */
/*
* Find the log base 2 of an integer with the MSB N set in O(N)
* operations. (on 64bit & 32bit architectures)
*/
int
getmsb (uint32_t word)
{
int r = 0;
if (word < 1)
return 0;
#ifdef BUILD_64
union { uint32_t u[2]; double d; } t; // temp
t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
while (word >>= 1)
{
r++;
}
#endif /* BUILD_64 */
return r;
}
비트 연산자를 생각해 보십시오.
나는 처음에 질문을 잘못 이해했다.맨 왼쪽 비트가 설정된 int(나머지는 0)를 생성해야 합니다.cmp가 이 값으로 설정되어 있는 경우:
position = sizeof(int)*8
while(!(n & cmp)){
n <<=1;
position--;
}
코드:
// x>=1;
unsigned func(unsigned x) {
double d = x ;
int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
printf( "The left-most non zero bit of %d is bit %d\n", x, p);
}
또는 Y=1을 설정하여 FPU 명령 FYL2X(Y*Log2 X)의 정수 부분을 가져옵니다.
저의 겸손한 방법은 매우 간단합니다.
MSB(x) = INT[로그(x) / 로그(2)]
번역:MSB x는 (기준 x의 로그를 기준 2의 로그로 나눈) 정수 값입니다.
이것은 모든 프로그래밍 언어에 쉽고 빠르게 적응할 수 있습니다.계산기로 시험해 보고 작동하는지 직접 확인해 보세요.
VPTEST(D, W, B) 명령과 PSRLDQ 명령의 조합을 사용하여 다음 위치에 있는 Perl 명령의 에뮬레이션을 사용하여 다음과 같이 최상위 비트를 포함하는 바이트에 초점을 맞춥니다.
https://github.com/philiprbrenan/SimdAvx512
if (1) { #TpositionOfMostSignificantBitIn64
my @m = ( # Test strings
#B0 1 2 3 4 5 6 7
#b0123456701234567012345670123456701234567012345670123456701234567
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000001',
'0000000000000000000000000000000000000000000000000000000000000010',
'0000000000000000000000000000000000000000000000000000000000000111',
'0000000000000000000000000000000000000000000000000000001010010000',
'0000000000000000000000000000000000001000000001100100001010010000',
'0000000000000000000001001000010000000000000001100100001010010000',
'0000000000000000100000000000000100000000000001100100001010010000',
'1000000000000000100000000000000100000000000001100100001010010000',
);
my @n = (0, 1, 2, 3, 10, 28, 43, 48, 64); # Expected positions of msb
sub positionOfMostSignificantBitIn64($) # Find the position of the most significant bit in a string of 64 bits starting from 1 for the least significant bit or return 0 if the input field is all zeros
{my ($s64) = @_; # String of 64 bits
my $N = 128; # 128 bit operations
my $f = 0; # Position of first bit set
my $x = '0'x$N; # Double Quad Word set to 0
my $s = substr $x.$s64, -$N; # 128 bit area needed
substr(VPTESTMD($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 4) : ($f += 32); # Test 2 dwords
substr(VPTESTMW($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 2) : ($f += 16); # Test 2 words
substr(VPTESTMB($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 1) : ($f += 8); # Test 2 bytes
$s = substr($s, -8); # Last byte remaining
$s < $_ ? ++$f : last for # Search remaing byte
(qw(10000000 01000000 00100000 00010000
00001000 00000100 00000010 00000001));
64 - $f # Position of first bit set
}
ok $n[$_] eq positionOfMostSignificantBitIn64 $m[$_] for keys @m # Test
}
웹 검색 전(그리고 이 페이지를 찾기 전)에 이 작업을 수행할 루틴이 필요했습니다.바이너리 검색을 기반으로 나만의 해결책을 생각해 냈어요.전에도 이런 일이 있었겠지만!이는 일정한 시간에 실행되며 게시된 "명백한" 솔루션보다 더 빠를 수 있습니다. 다만, 제가 특별히 주장하는 것은 아니지만, 단지 관심을 위해 게시한 것입니다.
int highest_bit(unsigned int a) {
static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
const unsigned int *mask = maskv;
int l, h;
if (a == 0) return -1;
l = 0;
h = 32;
do {
int m = l + (h - l) / 2;
if ((a >> m) != 0) l = m;
else if ((a & (*mask << l)) != 0) h = m;
mask++;
} while (l < h - 1);
return l;
}
여기서 하려는 것은 정수의 정수 log2를 계산하는 것입니다.
#include <stdio.h>
#include <stdlib.h>
unsigned int
Log2(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1; int k=0;
for( step = 1; step < bits; ) {
n |= (n >> step);
step *= 2; ++k;
}
//printf("%ld %ld\n",x, (x - (n >> 1)) );
return(x - (n >> 1));
}
한 번에 2비트 이상의 검색을 시도할 수 있습니다.
unsigned int
Log2_a(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1;
int step2 = 0;
//observe that you can move 8 bits at a time, and there is a pattern...
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//}
//}
//}
for( step2=0; x>1L<<step2+8; ) {
step2+=8;
}
//printf("step2 %d\n",step2);
for( step = 0; x>1L<<(step+step2); ) {
step+=1;
//printf("step %d\n",step+step2);
}
printf("log2(%ld) %d\n",x,step+step2);
return(step+step2);
}
이 접근법에서는 바이너리 검색을 사용합니다.
unsigned int
Log2_b(unsigned long x)
{
unsigned long n = x;
unsigned int bits = sizeof(x)*8;
unsigned int hbit = bits-1;
unsigned int lbit = 0;
unsigned long guess = bits/2;
int found = 0;
while ( hbit-lbit>1 ) {
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
//when value between guess..lbit
if( (x<=(1L<<guess)) ) {
//printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
hbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
//when value between hbit..guess
//else
if( (x>(1L<<guess)) ) {
//printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
lbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
}
if( (x>(1L<<guess)) ) ++guess;
printf("log2(x%ld)=r%d\n",x,guess);
return(guess);
}
또 다른 바이너리 검색 방법은 아마도 더 읽기 쉬울 것이다.
unsigned int
Log2_c(unsigned long x)
{
unsigned long v = x;
unsigned int bits = sizeof(x)*8;
unsigned int step = bits;
unsigned int res = 0;
for( step = bits/2; step>0; )
{
//printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
while ( v>>step ) {
v>>=step;
res+=step;
//printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
}
step /= 2;
}
if( (x>(1L<<res)) ) ++res;
printf("log2(x%ld)=r%ld\n",x,res);
return(res);
}
그리고 당신은 이것들을 테스트하고 싶을 것이기 때문에,
int main()
{
unsigned long int x = 3;
for( x=2; x<1000000000; x*=2 ) {
//printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
}
return(0);
}
'또 다른' 접근 방식이기 때문에 이것을 넣는 것은 이미 주어진 다른 접근 방식과는 다른 것 같습니다.
-1x==0그 이외의 경우floor( log2(x)) 31최고 결과 31)
32비트 문제를 4비트로 줄이고 표를 사용합니다.고상하진 않지만 실용적이죠
않을 때 입니다.__builtin_clz이치노
보다 콤팩트하게 하기 위해 루프를 사용하여 r에 4를 더해 최대 7회 반복을 줄일 수 있습니다.또는 (64비트의 경우)와 같은 일부 하이브리드: 8로 줄이기 위한 루프, 4로 줄이기 위한 테스트.
int log2floor( unsigned x ){
static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
int r = 0;
unsigned xk = x >> 16;
if( xk != 0 ){
r = 16;
x = xk;
}
// x is 0 .. 0xFFFF
xk = x >> 8;
if( xk != 0){
r += 8;
x = xk;
}
// x is 0 .. 0xFF
xk = x >> 4;
if( xk != 0){
r += 4;
x = xk;
}
// now x is 0..15; x=0 only if originally zero.
return r + wtab[x];
}
여기 GCC와 Clang에서 동작하는 C용 고속 솔루션이 있습니다.복사하여 붙여넣을 준비가 되어 있습니다.
#include <limits.h>
unsigned int fls(const unsigned int value)
{
return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}
unsigned long flsl(const unsigned long value)
{
return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}
unsigned long long flsll(const unsigned long long value)
{
return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}
그리고 C++용으로 조금 개선된 버전입니다.
#include <climits>
constexpr unsigned int fls(const unsigned int value)
{
return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}
constexpr unsigned long fls(const unsigned long value)
{
return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}
constexpr unsigned long long fls(const unsigned long long value)
{
return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}
에서는 '다 하다'라고 가정하고 있습니다.value 될 것이다0을 수정해야 .
언급URL : https://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i
'itsource' 카테고리의 다른 글
| '휘발성'의 정의는 이렇게 변덕스러운 건가요?아니면 GCC에 표준 컴플라이언스 문제가 있는 건가요? (0) | 2022.08.19 |
|---|---|
| 코틀린에서 JSON을 해석하는 방법 (0) | 2022.08.19 |
| Java의 다양한 유형의 스레드 세이프 세트 (0) | 2022.08.19 |
| Nuxt 가져오기 내에서 이름이 지정된 경우에는 Vuex 작업이 작동하지 않음 (0) | 2022.08.19 |
| 스프링-MVC 컨트롤러에서 404를 트리거합니까? (0) | 2022.08.19 |