Hello there!
So, I'm working on some train network and agreed that I need some encoding for the reservation system, when I remembered these magic number displays from years ago ... I decided to dig into it and understand them and see, if I can use them in other ways. Explaining is the last step of understanding, so I will use this thread to give some explanation how the magic-bits work.
32-bit signed integers
First of all, the numbers of the signals in factorio's circuit network are 32-bit signed integers. This is important to understand, because we want to manipulate these numbers on a bit level.
32-bit just means, that we have 32 zeroes and ones to encode a number. Signed means (in the standard) that the highest bit denotes whether the number is positive or negative:
Code: Select all
0000 0000 0000 0000 0000 0000 0000 0011
The highest bit (on the left) is 0, denoting a positive number. The rest is a bunch of zeroes, ending with 0011, which encodes 3. So, above is the bit representation of the number 3.
Wait, why 3? Well, according to standard. Ignoring positive and negative numbers for a second, how we usually encode numbers into binary is switching the base of a positional system
https://en.wikipedia.org/wiki/Positional_notation. I.e. from a base-10 to a base-2.
So, e.g. the number 0011 in base-2 is 2^3 *
0 + 2^2 *
0 + 2^1*
1 + 2^0 *
1 = 2 + 1 = 3 in base-10.
Since we have bits here, I also say "the bit is set" for "the bit is 1" or "the bit is not set" for "the bit is 0". Think of it like a switch. Switch on: set. Switch off: not set.
Negative representation
As I said, the highest bit decides whether the number is positive or negative. But don't get fooled. Since almost forever, just flipping the highest bit to 1 does not invert the number to its negative. E.g.
Code: Select all
1000 0000 0000 0000 0000 0000 0000 0011
is not -3 but actually -2^31 *
1 + ... + 2^1 *
1 + 2^0 *
1 = -2147483645 following what is called
two's complement.
How and why is open for you to explore; here it is only important to understand (or accept) that having a bit representation with the bits numbered from 31 to 0, i.e.
can be turned into (the common) base-10 by the formula
Code: Select all
-2^31*b31 + 2^30*b30 + 2^29*b29 + ... + 2^2*b2+ 2^1*b1 + 2^0*b0
Notice the negative -2^31 at the beginning and how it's still true that if and only if this bit (bit b31) is 1, the number is negative, since 2^31 is bigger then all other positions summed up. It is just another negative number then the one you would get when following the naive approach.
Bit shifting
We have everything here to explain the bit manipulation we need for the display magic: bit shifting. Bit shifting shifts all bits of a number for a given amount to the left or right. We stick to left bit shifting here. An example (with less then 32 bits, but it is all the same):
Bit shifting 0010101 for two positions to the left just moves all the bits two to the left and fills
0 from the right: 101011
00.
This is completely independent of the "actual" number which is represented here. While bit shifting, we pretend there is no number, there are just bits we manipulate. Of course, after bit shifting, we can just decode a number out of the new bit representation again, since its just another 32-bits, it has to be a number!
A single lamp
Let's say we want a lamp (in factorio) which is turned on whenever :A: is either 1 or 3. The brute-force approach would be probably having two decider combinators, each outputs :Green: = 1, first if :A: = 1, second if :A: = 3. Lamp then is on, whenever :Green: = 1.
But hey, we learned about bit shifting and bit representation and all that ... and a number has 32 bits. What info do we need?
- A is 1
- A is 3
- A is neither 1 nor 3
Not so much information, right? Should fit into 32 bits?
The marker bit
The highest bit in the signed integer representation decides whether the number is < 0 or >= 0. We saw that. But this is something we can check in a decider combinator! If :A: < 0 then the highest bit of the bit representation of signal :A: is set. If :A: >= 0, then it is not set.
To state it again: With a decider combinator, we can check whether the highest bit is set or not.
Putting it together
Now, add bit shifting to the mix. Say, we want to check whether bit 20 is set, e.g. on the following 32-bit signed integer:
Code: Select all
0000 0010 0001 0000 0100 0000 0000 0000
^--- bit 20
We shift this such that bit 20 is the highest bit, i.e. shift it 31 - 20 = 11 times to the left:
Code: Select all
1000 0010 0000 0000 0000 0000 0000 0000
^--- was bit 20, now bit 31
If the resulting number is < 0, then bit 20 was set in the original number!
Or in general: having a number, bit shifting by 1 and checking whether the number is < 0 tells us if bit 30 was set, bit shifting by 2 and checking tells us if bit 29 was set, etc.
So, with our single lamp, we want to notice if :A: = 1 or :A: = 3.
Here is the idea: Let's craft a bit representation which has the highest bit set if and only if we bit shift it with 1 or with 3. Hence, when we bit shift by :A: and it is 1 or 3, we have a number < 0. Otherwise the number is >= 0 and therefore we can decide whether :A: was 1 or 3!
As we bit shift to the left, we need the following representation:
Code: Select all
0101 0000 0000 0000 0000 0000 0000 0000
Bit shifting by 1 puts bit 30, which is set, to bit 31, which is then set and hence: a negative number.
Bit shifting by 3 puts bit 28, which is set, to bit 31, which is then set and hence: a negative number.
Every other shift just puts a 0 to the highest bit. Non-negative! ( ... well, what about any :A: > 31? ... see below)
This is the bit representation we are looking for. The final step is, to translate this into a number, since we cannot enter a bit representation in factorio's combinators. Well, we know already how: the sum of the positions. Which is, leaving all the 0s out:
This is our magic number, which gets < 0 if and only if bit shifting by 1 or by 3.
Finally: Set the lamp to activate on :Green: < 0. Input is on :A:, have a constant combinator with :Green: = 1342177280, and an arithmetic combinator which bit shifts :Green: << :A: into :Green:. Output of this arithmetic combinator goes to the lamp.
Wait! :A: = 33 make the lamp go on as well. Yes, I lied about the if and only if. Bit shifting in factorio works "in rounds". Going 33 to the left takes the bits one full round to their original position (shifting 32 times) and then one more. Hence, it is like shifting it by 1. (I know, modulo etc. pp. But the "rounds" picture is more helpful if one does not know modulo.)
You promised less combinators then the brute-force approach! But here we have two as well.
Did I? Well, anyways, the thing to notice here is, that the brute-force approach needs as much combinators as you want numbers the lamp has to go on for. Lamp on for 1, 3, and 5? Three combinators. With the bit-shifting approach, only the magic number changes.
Test your understanding: Can you work out the circuits such that the lamp goes on for :A: = 1, 3, 21 or 30?
From lamp to lamps
Let's focus on the number 0 to 9. We want a display which correctly displays each of these numbers, whenever :A: is that number. With the explanations so far, this is pretty close. Maybe you can work it out already ... ?
Our display is made out of lamps, 3x5, and I write A for "lamp on" and O for "lamp off". For :A: = 9 we want:
and for :A: = 8 we want
with the idea from above, we can work out for each lamp a magic number, such that for any possible :A: = 0 to 9, it is either on, when part of the symbol of the digit, or off otherwise, using bit shifting. We just look at the numbers, 0 to 9, if the lamp has to be on. If so, we have to set the respective bit in our magic number, resulting in a magic number which is negative whenever it was bit shifted by any of the respective numbers.
But how do we implement this in factorio's circuits? If we just output everything into :Green:, the signals overlap and the information is lost. The idea is to use a different channel for every lamp. Starting from left to right, top to bottom, we can use the channels :0:, :1:, ... :B:, :C:, ... or which ever we like, such that each lamp has its own channel, i.e. the condition :0: < 0, :1: < 0 etc.
For each channel (and lamp) the constant combinator needs to output the respective magic number.
Hence, we have on :0: a magic number, which gets < 0 whenever it is bit shifted by any number the lamp has to go on for. The same with all the other channels and their lamps respectively.
And that's it. That is all the magic.
Less channels
If you work out the patterns for each lamp on each of the digits 0 to 9, you will notice that some lamps share the same pattern. They go on or off for exactly the same digits. If we use the approach from above, we will have some channels with the same magic numbers, yielding the same results. So, what we can do, we can just let them use the same channel.
Not every lamp needs its own channel; but every unique pattern needs its own channel.
Numbers and digits
The rest of the circuitry you see in the magic-bit solution of displays takes care of the position of the digits you want to display. Say, we have the number 123 as input on :A: and three displays, where the first should display 1, the second 2 and the third 3. We already have the logic for displaying the digits themselves, 1, 2 and 3 (see above). What we need is to extract the hundreds, tens and singles out of 123 and feed it into our display logic.
Well, this is just some integer division foo and using, what is called
modulo operation.
Having an integer we can get the the hundreds by dividing by 100 and taking modulo 10. For example:
123 / 100 = 1
1 % 10 = 1
The tens, by dividing by 10 and taking modulo 10:
123 / 10 = 12
12 % 10 = 2
The singles by dividing by 1 and taking modulo 10:
123 / 1 = 123
123 % 10 = 3
I.e. the dividing puts the digit we want to extract to the right-most position, modulo 10 then extracts that right-most position (since we are in base-10 ... but it is okay to just accept that fact).
The end.
I hope that this provides you with the knowledge (or at least some basic grasp) of how to implement such displays on your own. With 32 bit integers, this method can be used to encode 32 different states. So add some letters as well! Or maybe extend it somehow to more states with other channels and a combinator or two? I, for myself, use it, to make train reservations, where each station gets a unique number. Setting the respective bit says: Hey! I'm station 21 and I need a train! And with some bit shifting, I can work out which stations need a train.
Thanks a lot for the cool ideas, for the blueprints and excel spreadsheets. Credits to them! Especially DaveMcW.