10
\$\begingroup\$

NDos' Numeral System

NDos' numeral system is a numeral system invented by me. It represents every nonnegative integer by a binary tree. Given a nonnegative integer \$n\$:

  • If \$n=0\$, it is represented as the empty tree.

  • Otherwise, the tree has a root. With the binary expansion of \$n\$:

    • The left sub-tree of the root recursively represents the length of least significant consecutive 0s of \$n\$ (trailing 0s).

    • The right sub-tree of the root recursively represents the more significant side of \$n\$ split right before its least significant 1. In other words, the right side is the number with its trailing 0s and their leading 1 stripped off.

For example, if \$n = 1100100_2\$, there are two trailing 0s, so the left sub-tree will be \$2_{10} = 10_2\$. Without the trailing 0s and their leading 1, \$ n \$ becomes \$1100_2\$, so the right sub-tree has that value.

For illustrative purposes, here are the full representation of the trees for \$n=1_2\$ through \$n=1110_2\$:

NDos' numeral system

Note that the numbers of nodes is not monotone. The smallest counterexample is \$10010_2\$ and \$11000_2\$.

Here's a Haskell implementation of conversion between binary and NDos':

import Data.Bits

data NDosNat = Zero | Push1 !NDosNat !NDosNat deriving (Eq, Show)

intToNDos :: Int -> NDosNat
intToNDos x
  | x < 0 = error "intToNDos: Negative input"
  | x == 0 = Zero
  | otherwise = let
    lSZN = countTrailingZeros x
    in Push1 (intToNDos lSZN) (intToNDos (shiftR x (lSZN + 1)))

nDosToInt :: NDosNat -> Int
nDosToInt Zero = 0
nDosToInt (Push1 lSZN mBS) = shiftL (shiftL (nDosToInt mBS) 1 .|. 1) (nDosToInt lSZN)

(I couldn't convert from nor to Integer because of Haskell's poor bit manipulation API.)

Objective

Given a nonnegative integer, treat it as represented in NDos' numeral system, and output its horizontal mirror image.

Examples

Here are some mappings. All numbers are in binary:

0 ↔ 0
1 ↔ 1
10 ↔ 11
100 ↔ 111
101 ↔ 1000
110 ↔ 110
1001 ↔ 10000000
1010 ↔ 11000
1011 ↔ 100000000
1100 ↔ 1110
1101 ↔ 1000000

Rule

The input and the output must be integers natively supported by your language.

\$\endgroup\$
15
  • \$\begingroup\$ I can use non-binary numbers? \$\endgroup\$
    – Fmbalbuena
    Jan 17 at 23:28
  • 1
    \$\begingroup\$ "output its horizontal mirror image" Can you elaborate? How does one go from the tree pictures to this? \$\endgroup\$
    – Jonah
    Jan 17 at 23:39
  • 1
    \$\begingroup\$ The part I'm confused about is how do you go from a tree structure to a flat list? \$\endgroup\$
    – Jonah
    Jan 17 at 23:43
  • 2
    \$\begingroup\$ Why must I/O be arbitrary sized integers? This immediately rules out a large number of languages. Why not just go with our default rules? \$\endgroup\$
    – pxeger
    Jan 18 at 6:42
  • 1
    \$\begingroup\$ Integers are commonly stored in JS as IEEE-754 numbers with 52 bits of mantissa. But bitwise operations are limited to 32 bits. But JS also supports BigInts with unlimited size. So how should integers natively supported by your language be interpreted in that case? Is that 32 bits, 52 bits, or unbounded? (And that's why you should just rely on default I/O rules.) \$\endgroup\$
    – Arnauld
    Jan 18 at 10:14

6 Answers 6

5
\$\begingroup\$

Python 2, 54 bytes

f=lambda n,b=0:n and[f(n/2,b+1),f(b)*2+1<<f(n/2)][n%2]

Try it online!

Takes in a non-negative integer and outputs the "mirrored" integer.

Use the recursive relation: If the left and right subtrees are a and b respectively, then the mirrored number will have f(b) and f(a) as left and right subtrees. To calculate a and b, I simply divide n by 2, then increment b by 1 until n is odd.

\$\endgroup\$
5
\$\begingroup\$

Pari/GP, 50 bytes

-5 bytes borrowing some tricks from @Arnauld's JavaScript answer.

f(n,t=valuation(n,2))=if(n,(2*f(t)+1)*2^f(n>>t++))

Try it online!

\$\endgroup\$
3
\$\begingroup\$

x86 32-bit machine code, 29 27 bytes

51 0F BC C8 74 13 D3 E8 D1 E8 E8 F1 FF FF FF 91 E8 EB FF FF FF 41 F9 D3 D0 59 C3

Try it online!

Uses the regparm(1) calling convention – argument in EAX, result in EAX.

-2 by making the function preserve ECX, removing the need to save it for the recursive calls.

Assembly:

.global f
f:  push ecx        # Save ECX onto the stack.
    bsf ecx, eax    # ECX := position of lowest 1 bit in EAX (= left subtree number).
    jz e            # Jump to the end if EAX was 0, which will return 0.
    shr eax, cl     # Shift EAX right by the number from above, removing the trailing 0s.
    shr eax, 1      # Shift EAX right by 1 more, removing the first 1.
                    #  (Now EAX holds the right subtree number.)
    call f          # Recursive call; apply the function to the right subtree number.
    xchg ecx, eax   # Exchange the value in ECX (the left subtree number)
                    #  with the value in EAX (which is f(the right subtree number)).
    call f          # Recursive call; apply the function to the left subtree number.
    inc ecx         # Add 1 to f(the right subtree number).
    stc             # Set the carry flag to 1.
    rcl eax, cl     # Rotate EAX together with the carry flag left by CL,
                    #  which is 1+f(the right subtree number).
                    # This appends to EAX a 1 and f(the right subtree number) 0s.
e:  pop ecx         # Restore the value of ECX from the stack.
    ret             # Return.
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

-4 bytes thanks to @att.

f@0=0
f@n_:=(2f@#+1)2^f[(n/2^#-1)/2]&[n~IntegerExponent~2]

Try it online!

\$\endgroup\$
2
3
\$\begingroup\$

JavaScript (ES6), 45 bytes

A port of Surculose Sputum's Python answer.

f=(n,b=0)=>n&1?f(b)*2+1<<f(n/2):n&&f(n/2,b+1)

Try it online!


JavaScript (Node.js), 50 bytes

It is unclear what the arbitrary-length integers natively supported by JS exactly are. Here is a version assuming that's BigInts.

f=(n,b=0n)=>x=n&1n?f(b)-~x<<f(n/2n):n&&f(n/2n,-~b)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 35 bytes

UME⊕N&ι±ι⊞Oυ∧ι×⊕⊗§υ⊖L↨ι²X²§υ÷κ⊗ιI⊟υ

Try it online! Link is to verbose version of code. Explanation: Calculates all of the mirror images from 0 to n inclusive and outputs the last one.

UME⊕N&ι±ι⊞Oυ∧ι

For each integer 0 to n, calculate the maximal power of 2 that is a factor of it, or 0 for 0. For each of those powers of 2, if the value is 0 then just push that, otherwise push...

×⊕⊗§υ⊖L↨ι²X²§υ÷κ⊗ιI⊟υ

... the result of looking up the number of trailing zeros, doubled and incremented and multiplied by 2 to the power the result of looking up the original value integer divided by the doubled power of 2.

I⊟υ

Output the last of the calculated values.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.