Exclusive Or

Discussion of challenges you have already solved
User avatar
Posts: 22
Joined: Fri Jun 26, 2009 12:01 pm
Location: /dev/null

Post by livinskull »

I did this bit for bit, as for the first thought I had was to print the result in binary...

So my code is kinda big with 115 instructions

Code: Select all

Initially coded that shit in asm to see how it would look like.. unfortunately my assembler still has its problems with jumps etc... so I translated the asm to hvm by hand

Code: Select all

preserve 2
var divisor 1073741824
var result

	push [0]
	push divisor
	jl skip_sub
	sub [0],divisor
	mov [2],1
	jmp second_number

	mov [2],0

	push [1]
	push divisor
	jl skip_sub2:
	sub [1],divisor
	mov [3],1
	jmp numbers_done
	mov [3],0
	push [2]
	push [3]
	je dont_add
	add result,divisor
	push 2
	push divisor
	je last_one
	div divisor,2
	jmp start
	push [0]
	push [1]
	je nothing
	add result,1

	pi result
Urgently need to resume working on my hvm assembler :3
Posts: 43
Joined: Mon Aug 31, 2009 6:18 pm
Location: Prague

Post by jonik555 »

LoL. Maybe I'm just too young for codes like these posted there... :D

Code: Select all

There are 10 types of people, those who understand ternary, those who think that this joke is about binary and the others.
Posts: 106
Joined: Thu Oct 29, 2009 9:21 pm

Post by DaymItzJack »

Code: Select all

03>1            # push the total into memory cell 3, keep the 'counter' on 
                # the stack starting at 1
0<1<            # take both numbers off memory
0^2/0^2*2v1v-   # divide the number by 2 and find the remainder and get
                # the bit
2v              # move number 2 up to the top
0^2/0^2*2v1v-   # divide the number by 2 and find the remainder and get
                # the bit
2v              # move number 1 up to the top
-7?             # if they are the same (0-0=0, 1-1=0), skip 
                #"adding counter to total"
3<3^+3>         # take memory cell out to the stack, add counter to it
2v2*            # increase counter, it goes in the order 1, 2, 4, 8...
1v2v            # put num1 and num2 back on top
1^1^-8?088*1--g # check if both num1 and num2 are 0, terminate if they are
Posts: 33
Joined: Sat Aug 13, 2011 2:13 pm

Post by compudemon »


fairly straight forward solution
Posts: 113
Joined: Sun Oct 26, 2008 10:38 am
Location: Germany

Post by rmplpmpl »


...good thing hacker.org is up again, I'll need to analyze the much shorter solutions for this...
User avatar
Posts: 29
Joined: Thu Jun 07, 2012 12:07 pm
Location: Germany

Post by TheBigBoss »

Okay, here's the shortest one:


It works with all integers of any size, does not corrupt the memory and cleans both its stack and call stack!
Posts: 9
Joined: Sun Apr 08, 2012 6:41 am

Post by wischi »

I wrote a little hvm-compiler (quick and dirty, at the moment only basic features) which support some inline functions (like mod) and calculates the jumps ;-)

My MetaHVM_0.0.1 Code

Code: Select all

#x = M0 (initialized)
#y = M1 (initialized)
#s = M2
#r = M3

12>						#s=1
03>						#r=0

	0<1<+[!end]?            #Condition (break if x = 0 And y=0) (load x,load y,add,jump if zero)
	0<2(mod)                #push x mod 2 to Stack
	1<2(mod)                #push y mod 2 to Stack
	-[!skip]?               #if equal then skip
		3<2<+3>              #r += s (load r, load s, add, write r)
	0<2/0>				#x /= 2;
	1<2/1>				#y /= 2;
	2<2*2>				#s *= 2;


Code: Select all

12>03>0<1<+397*+    ?0<21^1^/*-1<21^1^/*--7        ?3<2<+3>0<2/0>1<2/1>2<2*2>099*-    g3<p
Of course not the shortest way, and the gaps for the jumps are a bit annoying (each "Address" is 9 chars long and supports relative jumps from -820 to +828 - maybe i will make it dynamic in the future)

And maybe there will be structures and blocks (like if,for,while,...) in later MetaHVM versions ;-)
Posts: 17
Joined: Wed Feb 05, 2014 12:21 pm

Post by Tabun »

I'm also writing a HVM compiler that turns a C-like script language (which I call PreHVM) into a working HVM program. Kinda like witschi, only I went overboard: I made it track 'variables' on the stack, evaluate complex expressions with almost all operators C uses, with if/elseif/else and while structures and so on. It also does do fairly efficient overlapping jump resolution, so it doesn't rely on whitespace room.

Solution for this one was generated from:

Code: Select all

var val_a = mget(0);
var val_b = mget(1);

// find the highest factor of 2
var x = 1;
while (x < val_a || x < val_b) {
    x = x * 2;

// for each factor of two, add up the ones that are only present for one of the two
var val_c;
while (x > 0) {
    if (val_a >= x ^ val_b >= x) {
        val_c = val_c + x;

    if (val_a >= x) {
        val_a = val_a - x;
    if (val_b >= x) {
        val_b = val_b - x;

    x = x / 2;

print val_c;
Very fun project, though it doesn't exactly generate optimal HVM yet. This generated a 240 command program. I know that's HUGE still, and it only uses relative jumps.
It should be a bit smaller once I optimize comparison/condition checks for the ifs/loops and some tricks. For now, though, I'm just having fun making it work -- and I do like keeping memory 'clean' by default, if I can.
Posts: 3
Joined: Mon Nov 13, 2017 7:57 pm
Location: NULL

Post by _romanchick_ »

This is my code. Not too short, but it uses no :. So it can be usefull later...
0 13> 0<0<2/2*-1<1<2/2*-+5>5<5<2/2*- 3<*+ 0<2/0>1<2/1> 3<2*3> 0<1<+3?6c p
Posts: 9
Joined: Fri Nov 20, 2015 2:04 pm

Re: Exclusive Or

Post by adark »

I went about this totally by hand, and boy was that a pain in the butt. Definitely need to build myself a debugger for HVM + SuperHack! Wrote this to be agnostic about the size of the operands!

A slight optimization would be to swap the memory cells if M[0] < M[1], saving a handful of cycles on the later iterations once the smaller value reaches 0 during the first loop. An even better optimization that I *should* have done is storing the result value on the stack instead of using M[2], saving 8 cycles *every* iteration of the first loop! This also leaves a "garbage" value on the call stack, so I'd have to rewrite Loop 1 some to embed this in another HVM program.

Code: Select all

07c06-g 0<0:3?7g 1<0:3?6g 68*g 1+0<0^2/0^0>2*- 1<0^2/0^1>2*- 2<2*2v2v:2?1+2> $ 02<2v0^0:1-4?ddp!1-1^0^2/2*-3v2*+2v2/05-7*7-g

Code: Select all

0             # initialize bit counter to 0

# Loop 1:
7c06-g        # call-based loop header
0<0:3?7g      # if M_0 is 0, go to M_1 check, else enter loop body (jumps to M_1 check's `6g`)
1<0:3?6g 68*g # if M_1 is 0, go to the bit-reversal routine, else enter loop body

              # LOOP BODY:
1+            # increment bit counter

0<0^2/0^0>2*- # Compute the LSB of M_0 + store M_0 /= 2
1<0^2/0^1>2*- # Compute the LSB of M_1 + store M_1 /= 2

# explained:
# n<          # load M_n
# 0^          # duplicate it
# 2/          # integer divide duplicate by 2
# 0^n>        # duplicate and store result back into M_n
# 2*-         # double result and subtract this from original
              # By integer division, this computes the LSB of M_n

# stack is now [n+1, (original M_0 >> n)&1, (original M_1 >> n)&1]

2<2*          # load result from M_2 (initially 0 by default) and left-shift it 1 bit
2v2v:2?       # pull out the 2 bits of M_0 and M_1 and compare them
1+            # if they're *not* equal, add 1 to result
2>            # store result back into M_2
$             # GOTO Loop 1

# bit-reversal routine
02<           # initialize "correct" result, and load reversed result from M_2

# Loop 2:
# stack is now [n, result, reversed], where `n` bits still need to be copied from `reversed` to `result`
2v0^0:        # move n to top of stack, duplicate and compare to 0
1-4?          # if n > 0, skip over the exit
ddp!          # exit, drop `n` and `reversed`, print `result`!
1-            # decrement n
1^0^          # duplicate `reversed` twice
2/2*-         # extract its current LSB
3v2*+         # move `result` to top of the stack, << 1 and add `reversed`'s LSB
2v2/          # move `reversed` to top of the stack, >> 1
05-7*7-g      # GOTO Loop 2
Post Reply