00000000000000110011010101100000



총 3종의 회로로 구성됨

1. 비트 반전

2. 가장 작은 1 위치 찾기

3. 32-5 인코더




가장 작은 1 위치 찾기 회로부터 설명하자면

지금 저 스샷을 보면 입력이

111984640

이진법으로 쓰면

0b00000110101011001100000000000000 인데, 여기서 가장 오른쪽에 있는 1만 남겨서

0b00000000000000000100000000000000 을 만들어주는 회로임



구조가 상당히 간단한데 입력을 A라고 한다면

(~A+1)&A를 하면 끝난다 (~는 bitwise not)


입력인 A

0b00000110101011001100000000000000 에다 bit not을 하면

0b11111001010100110011111111111111 이 되고 여기에다가 1을 더하면

0b11111001010100110100000000000000 이 되고 이걸 처음값과 and연산을 하면

0b00000000000000000100000000000000 이 되는 방식


이걸 처음 봤을때 정말 기가 막혔던 적이 있다




이런 방식으로 가장 작은 1 위치 찾기는 아주 쉽게 할 수 있다

문제는 이진 로그를 구하기 위해선 가장 작은 1위치가 아니라 가장 큰 1위치를 구해야 한다는 점이다

그래서 비트 반전 회로가 등장한다



비트 반전 회로의 수도 코드는 다음과 같다

A=(A<< 1)&0xAAAAAAAA+ (A>>1)&0x55555555

A=(A<< 2)&0xCCCCCCCC + (A>>2)&0x33333333

A=(A<< 4)&0xF0F0F0F0 + (A>> 4)&0x0F0F0F0F

A=(A<< 8)&0xFF00FF00 + (A>> 8)&0x00FF00FF

A=(A<<16)&0xFFFF0000 + (A>>16)&0x0000FFFF


각 단계에 따라 빨간색과 파란색이 자리를 교체하게 된다

0b0000_0000_0000_0011_0011_0101_0110_0000 이 입력되면

0b0000_0000_0000_0011_0011_1010_1001_0000 (1개씩 자리바꿈)

0b0000_0000_0000_1100_1100_1010_0110_0000 (2개씩 자리바꿈)

0b0000_0000_1100_0000_1010_1100_0000_0110 (4개씩 자리바꿈)

0b1100_0000_0000_0000_0000_0110_1010_1100 (8개씩 자리바꿈)

0b0000_0110_1010_1100_1100_0000_0000_0000 (16개씩 자리바꿈)



이 과정을 거치면 계산에 걸리는 시간이 10틱이나 걸리고 조합기를 20개나 사용하긴 하지만 비트를 반전시키는 것이 가능하다

배보다 배꼽이 더 큰셈인데 더 좋은방법이 있을지는 모르겠음


아무튼 우리가 원하는 값을 비트플립시킨다음에 가장 작은 1위치를 찾게 된다면 결과적으로

우리가 처음 입력한 값의 가장 큰 1위치를 찾는것과 다름없는 계산을 하게 된다





3번째 회로는 32-5 인코더인데 적절한 비트연산을 통해

0b00000000000000000100000000000000 를 14로 바꿔준다

가장 오른쪽 자리를 0번 자리라고 쳤을 때 1은 14번 자리에 위치해있다


그런데 우린 이걸 비트플립한거였으니까 저 자리수도 한번 뒤집어주기위해 31에서 저 값을 빼야한다

31에서 14를 빼면 17이 되고 이게 우리가 원하는 값이다

log2(210272) =17.6818 내림처리하면 17!


32비트 연산을 위해 34개나 조합기를 사용하고 있지만 나름 공간복잡도는 log2(N)이다

조합기 갯수 = (4*log2(N)) + (3) + (2*log2(N)+1) = 6log2(N) + 4

만약 64비트 버전이였다면 6개만 늘어나서 40개로 처리가 가능한 셈


청사진

https://factoriobin.com/post/R1TO5lOI


청사진(왼쪽에 디버그용 전등 포함된 버전, textplate, nixie tubes 모드 필요)

https://factoriobin.com/post/AoZHyxME