How to merge two binary numbers into a ternary number

Question

I have two binary integers, x0 and x1 that are 8 bits (so they span from 0 to 255). This statement is always true about these numbers: x0 & x1 == 0. Here is an example:

bx0 = 100 # represented as 01100100 in binary
bx1 = 129 # represented as 10000001 in binary

So I need to do the following operation on these numbers. First, interpret these binary representations as ternary (base-3) numbers, as follows:

tx0 = ternary(bx0) # becomes  981 represented as 01100100 in ternary
tx1 = ternary(bx1) # becomes 2188 represented as 10000001 in ternary

Then, swap all of the 1 in the ternary representation of tx1 to 2:

tx1_swap = swap(tx1) # becomes 4376, represented as 20000002 in ternary

Then use a ternary version of OR on them to get the final combined number:

result = ternary_or(tx0, tx1_swap) # becomes 5357, represented as 21100102 in ternary

I don't need the ternary representation saved at any point, I only need the result, where for example result=5357. Of course I could code this by converting the numbers to binary, converting to ternary, etc.. but I need this operation to be fast because I am doing this many times in my code. What would a fast way to implement this in python?

Everetteeverglade

Good luck with this, it doesn't sound like anything there would be built-in, optimized operations for. – Younglove

What have you tried so far, and what are the results that you find unsatisfactory? Have you tried your base case (converting and converting again) and timed it? – Osei

Posting an example and the time you need to be under for that example would be useful. – Sheelah

This whole thing sounds very strange. What real-world application is there for replacing all the 1 with 2 in a ternary number? – Younglove

@Younglove Real world application: open-aurec.com/wbforum/viewtopic.php?t=5623 – Everetteeverglade

What do you have in mind when you say "a ternary version of OR"? Can you draw a truth table for this operation? – Schlep

@duskwuff after posting this I found out that swap is just multiplying by two and ternary_or is just addition... oops – Everetteeverglade

@PaulTerwilliger Addition isn't OR-like; it can generate carries. – Schlep

@duskwuff the way that the problem is generated there will never be any carries – Everetteeverglade

tbh doing this operation (just straight as you've described it, no clever optimizations) in C would be blindingly fast. You could use Cython, ctypes, or SWIG if you needed a top level Python function...but it seems like the wrong type of problem for "speed" in Python. – Filiano

I've decided I'm going to use a lookup table for ternary because a list of 255 integers shouldn't be large in memory... and the other two operations are just multiplication by two and addition. Thanks for the comments, I want to give someone credit so if anyone wants to write-up that solution I'll give them the green check mark. If not I'll write it up myself. – Everetteeverglade

Does int(format(bx0, "b"), base=3) + 2 * int(format(bx1, "b"), base=3) achieve what you ask for? – Reminisce

Yep that works as well! @MarkDickinson – Everetteeverglade

Ah, an X-Y problem. I probably wouldn't attack the black/white/both board problem using "ternary" numbers. It's obviously cumbersome and computers don't know how to work in radix 3. Perhaps better would be numbers consisting of 2-bit bit fields where the left bit was white and the right one black, or something like that. Computers like bit fields. – Jeweller

@lurker, one application would be if you want to store a table of values on an embedded device, you'd want to use as little memory as possible. For example, there are only 3^8 = 6561 possible positions for 8 ternary state squares. But if one uses your method, the look up table would have to have 4^8 = 65536 keys, roughly ten times bigger! – Manse

@OhneKleidung yes that is true. Op didn't indicate they were trying to reduce memory footprint. – Jeweller

@lurker, yeah, I don't think it is a concern if one uses Python... But I need a similar solution for C/C++. – Manse

Answer 1

Re-explanation for dummies like me:

A straightforward way to "encode" two binary mutually exclusive numbers (w & b == 0) in ternary would be:

white_black_empty = lambda w, b: int(format(b, 'b'), base=3) + \
                                 int(format(w, 'b').replace('1','2'), base=3)

Here are all possible 2-bit variants:

white_black_empty(0b00, 0b00) == 0
white_black_empty(0b00, 0b01) == 1
white_black_empty(0b01, 0b00) == 2
white_black_empty(0b00, 0b10) == 3
white_black_empty(0b00, 0b11) == 4
white_black_empty(0b01, 0b10) == 5
white_black_empty(0b10, 0b00) == 6
white_black_empty(0b10, 0b01) == 7
white_black_empty(0b11, 0b00) == 8

By observing that int(format(w, 'b').replace('1','2'), base=3) is actually equal to double of int(format(w, 'b'), base=3) (for example, 2022002₃ == 1011001₃*2), we get the solution that @Mark Dickinson posted in the comments above:

white_black_empty = lambda w, b: int(format(b, 'b'), base=3) + \
                                 int(format(w, 'b'), base=3)*2

Manse

Answer 2

The fastest way to do this is probably with decimal addition:

a = 1100100
b = 10000001
result = int(str(a+2*b),3) #5357

You won't find ternary-wise operators in python (or any other language that I know of.) Since you need to go above bitwise operations, your next-fastest option is integer addition, which every computer on Earth is optimized to complete.

Other solutions that convert to ternary to get this done will require you to cast back and forth to strings which takes much longer than decimal addition. This only requires one string cast at the end, assuming you even need the decimal version of the final ternary number.

Kwarteng