숫자의 binary log을 찾는 방법이 있는지 알고 싶습니다. 숫자가 4이고 2를 올리면 4가 2가된다고합시다.이동하지 않고 O (1) 시간 (레지스터 x86 또는 SIMD에서 작동)의 이진 대수?
이것은 이동 및 카운팅에서는 가능하지만 조작은 O(N)입니다. 어떤 방법으로 O(1)을 n에 넣을 수 있습니까? x = 2^n?
여기 n을 찾으려면 x을 한 번에 사용하거나 O(1)을 알고 싶습니다.
x86을 지정 했으므로 가장 중요한 세트 비트의 위치를보고하는 BSR (비트 스캔 역방향) opcode를 원하는 것처럼 들립니다.
[FYI : big-O 표기법은 점근 적 복잡성을 나타냅니다 (즉 N -> 무한대). N이 한정된 한계 (이 경우 32 또는 64)를 갖는다면별로 의미가 없습니다.]
BSR은 x86 명령어입니다. 나는 그것을 참고해야 할 것이다, FYI에 감사한다. 나는 창조적이 될 때만이 물건을 거의 사용하지 않습니다. – pandoragami
어떤 컴파일러를 사용 하느냐에 따라 ASM을 작성하는 데 사용할 수있는 내장 함수가있을 것입니다. 확실히 gcc와 MSVC는 모두 다른 내장 함수를 사용합니다. –
@Paul R GCC를 사용하고 있는데, 내장 함수 전체를 살펴 보았고'BSR'과 비슷한 기능을 찾을 수 없습니다. 네가 뭔가 생각하면 나 한테 알려줘. – pandoragami
참조 : http://stackoverflow.com/a/994709/253056 –
그래,이 스레드의 대답 후에 어셈블러 부분을 알아 냈습니다. 나는 BSR이 존재한다는 것을 모른다. Thx 노트. – pandoragami
SIMD에서 float로 변환하고 지수를 추출 할 수 있습니다. HW 각도에 대해서는 – harold