Up to Main Index Up to Journal for March, 2015
JOURNAL FOR MONDAY 16TH MARCH, 2015
______________________________________________________________________________
SUBJECT: That's the way to go - with a bit of fun
DATE: Mon 16 Mar 22:34:47 GMT 2015
After much procrastinating and even more umming and erring I have decided to
export some types so that I can provide better documentation[1]. After
refactoring the code I'm back to documenting again. For some reason people
actually *LIKE* reading my comments and documentation, quite often finding it
amusing...
Only a few people have seen the code for WolfMUD-mini so far but one method
seems to confound them - I like leaving little 'gems' for people who actually
read the code to find :) In the exits code I have defined constants for
directions:
const (
North byte = iota
Northeast
East
Southeast
South
Southwest
West
Northwest
Up
Down
)
No surprises there. Later on there is a method that calculates the opposite of
a given direction. Here it is complete with comments:
// Return calculates the opposite/return direction for the direction given.
// This is handy for calculating things like normal exits where if you go
// north you return by going back south for example.
func Return(direction byte) byte {
if direction < Up {
return direction ^ 1<<2
} else {
return direction ^ 1
}
}
This does a little bit of bit twiddling[2]. Sadly a lot of programmers don't
do bit twiddling any more, most of the programmers I know wouldn't even know
what the << and ^ operators do! So for completeness I will start off with an
explanation of those operators - feel free to skim the explanations if you
are already an accomplished bit twiddler :)
Left shift operator '<<'
The left shit operator takes the binary representation of a number and shifts
the bits to the left, the left most bit drops off and zeros are added to the
right. The number to be shifted is on the left and the number of bits to shift
by is on the right. For example:
148 decimal = 10010100 binary
148 << 2 = 10010100 << 2 = 10010100
00101000 (shifted left once)
01010000 (shifted left twice) = 80 decimal
In the code above we have:
1 decimal = 00000001 binary
1 << 2 = 00000001 << 2 = 00000001
00000010 (shifted left once)
00000100 (shifted left twice) = 4 decimal
So in the above code we could have written '4' instead of '1<<2' however when
bit twiddling it is usually easier to write numbers using shifts instead of
decimal, hex or octal.
Bitwise exclusive OR '^'
The bitwsie exclusive OR (XOR )operator compares two numbers. Where the bits
are the same a 0 is returned in the result. If they are different a 1 is
returned. For example:
148 decimal = 10010100 binary
28 decimal = 00011100 binary
148 ^ 28 = 10010100
00011100
--------
10001000 = 136 decimal
One interesting property of XOR is that the number to the right can be used as
a mask to toggle bits on and off in the number to the left. In the number to
the right - the mask - zeros keep their original values while ones indicate
bits to be toggled. Reusing our example from before we can toggle the bits
back again by repeating the operation with the same mask - of 28 decimal or
00011100 binary - on the previous result we got:
136 ^ 28 = 10001000
00011100
--------
10010100 = 148 decimal
In our example go code 'direction ^ 1<<2', simplified as 'direction ^ 4' is
simply taking the value of direction and toggling the 3rd bit - because 4
decimal is 00000100 binary.
But how does this explain how the code calculates the opposite direction!?
Lets create a table representing the decimal and binary values of the
constants:
Constant Decimal Binary
North 0 00000000
Northeast 1 00000001
East 2 00000010
Southeast 3 00000011
South 4 00000100
Southwest 5 00000101
West 6 00000110
Northwest 7 00000111
Up 8 00001000
Down 9 00001001
If you look closely at the table the first four directions (North, Northeast,
East, Southeast) map to the next four directions (South, Southwest, West,
Northwest). If you look at the binary representation the only difference in
the two groups is the 3rd bit - 0 in the first group and 1 in the second. So
if we take any of the first 8 directions we can flip the 3rd bit to get it's
opposite direction! Lets take Southwest as an example:
Southwest ^ 4 = 5 ^ 4
= 00000101
00000100
--------
00000001 = 1 = Northeast
This only works for the first 8 directions - those before Up. This is why we
need the if statement in our original code 'if direction < Up'. If we look at
out table we see that the only difference between Up and Down is the right
most bit. So we can simple flip that bit to toggle between Up and Down. This
is what 'direction ^ 1' does for us.
And there you have it - a 7 line function explained in only 160 odd lines ;)
--
Diddymus
[1] 3.html
[2] Proper programmers twiddle their own bits.
Up to Main Index Up to Journal for March, 2015