32비트 이진수의 길이 출력하는 알고리즘 최인몇?

[익명(175.192)]

최소 인스트럭션 개수 몇개?

클로드 소넷트가 제시한 바로는

약 7~8개의 인스트럭션으로 대체 가능하다고 함.

출력 예시

0b001 -> 1 

0b011 -> 2 

0b100 -> 3 

0b1010 -> 4 

0b10000 -> 5 

0b111111 -> 6 

0b10001000 -> 8

[익명(chartman)]

lambda x: int(math.log(x, 2) + 1

[익명(175.192)]

그거는 인스트럭션 20~40개 소요됨

[익명(175.192)]

LOOKUP_TABLE[x | (x >> 1) | (x >> 2) | (x >> 4) | ( x >> 8) | (x >> 16)] 이렇게 하면 7~8 인스트럭션임

[익명(chartman)]

어셈이면 제일 먼저 나오는 1을 찾는 명령어를 찾아보고 싶군

[익명(175.192)]

그거는 평균 16 워스트케이스엔 32인스트럭션 소요됨

[익명(175.192)]

나는 x << ((x > (1 << ((x > (1<<15) ? 16 : 0)+7) ? 8 : 3) 이런식의 알고리즘 생각했음

[익명(175.192)]

내가 생각한 알고리즘은 브랜치도 많고 디펜던시도 많고 대신 메모리 참조가 적어서 이점임.

[익명(175.192)]

인스트럭션 아마 12개? 쯤 나올거 같음

[트렌더(monday9400)]

Bsr쓰면됨 ㅇㅇ 32비트를왜고려함

[익명(175.192)]

오오

[익명(175.192)]

이런 명령어도 있구나

[익명(175.192)]

64비트면 clz써서 64에서 빼야함