서로 다른 특정 두 신호에 대한 bitwise-or


팩토리오에서 서로 다른 두 신호의 bitwise or 연산을 하는 것은 매우 간단하다



철판 신호 10100011111101101000011110100000 (-1544124512 ~= -1.5G)

구리 신호 00000000101100010011010100010101 (11613461 ~= 11M) 가 or 되어서

철판 신호 10100011111101111011011110110101 (-1544046667 ~= 1.5G) 가 출력으로 나오는 것을 볼 수 있다



그렇다면 서로 같은 두 신호를 bitwise or하고싶으면 어떻게 해야 할까?




같은 특정 두 신호에 대한 bitwise-or


당연하게도 이런 식으로는 사용할 수 없다

이러면 그저 두 철판 출력 값이 더해진

-1544124512+11613461 = -1532511051이 출력될 뿐 bitwise-or 값인 -1544046667을 얻을 수 없다


따라서 아래처럼 신호를 다른 값으로 변경하는게 먼저 수행되어야 한다



이렇게 철판 신호를 구리 신호로 치환해버리면 처음 상황처럼 서로 다른 두개의 신호를 or하는 문제로 바꿀 수 있게 된다


그런데 이건 우리가 입력신호가 "철판"이라는 것을 알 때만 사용할 수 있는 해결책이다

만약 철판이 아닌 임의의 값에 대하여서 bitwise-or를 수행하고 싶다면?

수백개의 신호가 동시에 입력 되더라도 각각 bitwise-or를 수행하고 싶다면?

이것이 가능할까?




임의의 특정 두 신호에 대한 bitwise-or


이걸 해결하기 위해 광란의 비트 장난질이 시작된다..


자릿수

3

2

1

0

입력1

a

b

c

d

입력2

e

f

g

h

|

a|e

b|f

c|g

d|h

(| : or 연산)

구현하고자 하는 수식은 결국 bitwise-or 연산임 각 자리의 비트수끼리 or 연산을 해서 결과물을 만드는것

예를 들어 1번 비트에 해당하는 값을 얻고 싶다면 0번 비트나 2번 비트의 영향은 받지 않아야함


팩토리오 회로 환경에서 이걸 최대한 응용하려면 무슨 방법이 있을까? 고민하다가 팩토리오의 덧셈은 아주 가격이 싸다는걸 생각함


자릿수

3

2

1

0

a

b

c

d

e

f

g

h

+

a+e

b+f

c+g

d+h


일단은 두 개의 입력 값을 무지성으로 더해봤음

1비트의 값을 2개 더하면 그 값은 2비트의 출력이 됨 그걸 고려해서 위의 표를 다시 작성하면 이렇게 됨



자릿수

4

3

2

1

0

a

b

c

d

e

f

g

h

+

(a+e)/2


(b+f)/2

(a+e)%2

(c+g)/2

(b+f)%2

(d+h)/2

(c+g)%2


(d+h)%2

(% : 나머지 연산)


a+e를 한다고 쳤을 경우 a와 e가 둘 다 1이여서 더한 값이 2가 된다면 한자리 위의 자릿수에 carry가 올라가게 됨

그리고 자기 자신의 자릿수는 더한 값을 2로 나눈 나머지 값이 들어가게 됨

이걸 산술식이 아니라 논리식으로 다시 써보면



자릿수

4

3

2

1

0

a

b

c

d

e

f

g

h

+

a&e


b&f

a^e

c&g

b^f

d&h

c^g


d^h

(& : and 연산, ^ : xor 연산)


이렇게 간결하게 표현할 수 있다

둘 다 1이면 다음 자릿수에 1이 반영되고(and)

둘 중에 하나만 1일 때만 현재 자리수에 1이 반영됨(xor)


문제는 현재 자릿수의 연산 결과가 다음 자릿수의 반영이 되어서 뒤섞여 버리는데 이걸 어케 써먹느냐는 것

따라서 그냥 더하는건 별로 의미가 없고 전처리가 필요하다



자릿수

4

3

2

1

0

a

b

c

d

0

1

0

1

&


0

b

0

d


이렇게 abcd에 0101...0101을 and 연산을 취해주면 a,c는 사라지고 0b0d를 추출할 수 있게 됨

같은 방법으로 efgh에서 0f0h를 얻을 수 있음

이 두개를 다시 더해보면?


자릿수

4

3

2

1

0

0

b

0

d

0

f

0

h

+


b&f

b^f

d&h

d^h


신호가 섞이지 않은 상태인 b&f, b^f, d&h, d^h를 얻을 수 있다

이걸 좀전과 마찬가지로 0101 and 연산을 취해주면 0, b^f, 0, d^h 이렇게 xor 결과만 추출할 수도 있고

1010 and 연산을 취해주면 b&f, 0, d&h, 0 이렇게 and 결과만 추출할 수도 있음


b,d,f,h에서 b&f, b^f, d&h, d^h를 얻는게 가능했으니 당연하게

a,c,e,g에서 a&e, a^e, c&g, c^g 것 또한 가능함



이걸 어떻게 써먹을 수 있는가 하면

a | e = (a & e) + (a ^ e)

가 성립하는걸 이용할 수 있음(or는 둘 중 하나 이상이 참인 것, and는 둘 다 참인 것, xor는 하나만 참인 것 이니깐)

a&e와 a^e는 위에서 말한 방법으로 얻었으니 이 결과를 그냥 팩토리오 회로 덧셈 시스템으로 연결해주기만 하면 or 결과를 얻을 수 있다


표로 그릴려니 너무 귀찮아서 아래로는 그냥 텍스트로만 설명


최종적으로 얻고싶은건

{a|e, b|f, c|g, d|h} 임

이걸 얻기 위해 과정을 역으로 따라가면


{a|e, b|f, c|g, c|h}

= {a&e, b&f, c&g, d&h} + {a^e, b^f, c^g, d^h}

= ({a&e, 0, c&g, 0} + {0, b&f, 0, d&h}) + ({a^e, 0, c^g, 0} + {0, b^f, 0, d^h})

= {a&e, 0, c&g, 0} + {a^e, 0, c^g, 0} + {0, b&f, 0, d&h} + {0, b^f, 0, d^h}

= ( {a&e, a^e, c&g, c^g} & {1,0,1,0} )
+( {a&e, a^e, c&g, c^g} & {0,1,0,1} << 1 )
+({ {b&f, b^f, d&h, d^h} & {1,0,1,0} >> 1)

+({ {b&f, b^f, d&h, d^h} & {0,1,0,1} )

= ( {a&e, a^e, c&g, c^g} & {1,0,1,0} )
+( {a&e, a^e, c&g, c^g} & {0,1,0,1} ) + ( {a&e, a^e, c&g, c^g} & {0,1,0,1} )
+({ {b&f, b^f, d&h, d^h} & {1,0,1,0} >> 1)

+({ {b&f, b^f, d&h, d^h} & {0,1,0,1} )


{a&e, a^e, c&g, c^g}

= {0, a, 0, e} + {0, e, 0, g}

= ({0, a, b, c} & {0,1,0,1}) + ({0, e, f, g} & {0,1,0,1})

= (({a, b, c, d}>>1) & {0,1,0,1}) + (({e, f, g, h}>>1) & {0,1,0,1})


{b&f, b^f, d&h, d^h}

= {0, b, 0, d} + {0, f, 0, h}

= ({a, b, c, d} & {0,1,0,1}) + ({e, f, g, h} & {0,1,0,1})


{a, b, c, d}와 {e, f, g, h}를 이용해서 {a|e, b|f, c|g, d|h}를 얻을 수 있었다!



이것의 회로 구현체






철판 신호가

10100011111101101000011110100000 (-1544124512 ~= -1.5G)

00000000101100010011010100010101 (11613461 ~= 11M) 가 or 되어서

10100011111101111011011110110101 (-1544046667 ~= 1.5G)

가 나오고


구리판 신호가

00000000010101101001111001101110 (5676654 ~= 5.6M)

00011011000111001001010010010110 (454857878 ~= 454M) 가 or 되어서

00011011010111101001111011111110 (459185918 ~= 459M)
이 나오는 모습



이렇게 원하는 시그널끼리 bitwise or 하는것에 성공하였음

더 최적화 된 방법이 있는지는 모르겠지만 일단은 조합기13개, 레이턴시3, 처리량제한X

이 정도 사양이면 못 써먹을 정도는 아닌듯




Bitwise AND, XOR 연산은?


bitwise and나 bitwise xor가 필요하다면 위의 과정에서 이미 a&e, a^e는 상대적으로 쉽게 얻었던 것을 사용하면 된다


or을 좀더 간략화 한 형태

레이턴시는 3으로 동일하고 조합기 수만 조금 줄었다




청사진


https://factoriobin.com/post/zET8_Rn6




결론


팩토리오 회로는 각신호(노란별) 연산과 합선된 선로는 0 tick 덧셈이 된다는 점을 잘 활용하면 아주 다양한 일들을 할 수 있는데

그 점을 적극 활용하면서 임의의 두신호에 대한 bitwise 연산을 구현했다는 점에서 아주 마음에 드는 결과였음

이걸 그래서 어따 쓰냐고 물어본다면 뭐라 답하기는 어렵지만 회로 깊게 파다 보면 이런 비트 연산이 필요해지는 때가 온다ㅋㅋ