Please assist with bit operations.

Hello,

Recently I've begun work on a maze generator for adults and children alike. Basically the algorithm calls for a 2d array with multiple values for each index in that array. Each index represents a square in the maze and each square has a value for whether it has been visited and which of the 4 possible walls is up.

Since this is a binary set of variables (wall standing vs wall removed) and (visited vs unvisited) I was hoping to implement a sort of single byte value. I'm told that a byte has 8 bits to work with and those 8 bits seem like more than enough possible boolean variables.

I need to store the following variables in a single bit value inside the Byte.

1 Has a North Wall (true or false)
2 Has an East Wall (true or false)
3 Has a South Wall (true or false)
4 Has a West Wall (true or false)
5 Has been visited (true or false)

So would it be possible to have a single 8 bit value to match?

North East South West Visited unused unused unused

I'm fairly green to the notion of using bits.

A. Given this format, how would I set the bits in the byte?

B. Given this format, how would I check the values in the byte for each boolean variable using "if" loops or "case" loops?

Initially I got an algorithm working using objects to hold the cell data but it became memory intensive and sluggish. I was told that bit operations are extremely fast and using a single byte to describe all 5 boolean values seems to be memory efficient too.

Please assist me. I'm very new to this level of memory manipulation.

Here's an example I knocked up from a previous module I wrote (unsure where I figured out how to do this).
EDIT: BAM! use the ~ operation to remove flags.

SuperStrict

'unsure if adding last value to new value is necessary
'though using 1-5 (in this example) outputs "Flags contains sq_EAST" 
'so theres something to this standard
'you can use bytes or ints for flag values
Const sq_NORTH:Int = 1, sq_SOUTH:Int = 2
Const sq_EAST:Int = 4, sq_WEST:Byte = 8
Const sq_VISITED:Byte = 16

'check if values exist in Flags
Local Flags:Byte = sq_NORTH | sq_WEST | sq_VISITED
testflags(Flags)
Print

Flags = flags ~ sq_NORTH
testflags(Flags)

Function testflags(Flags:Byte)
	If (sq_NORTH & Flags)
		Print "Flags contains sq_NORTH"
	Else
		Print "Flags does not contain sq_NORTH"
	EndIf
		
	If (sq_SOUTH & Flags)
		Print "Flags contains sq_SOUTH"
	Else
		Print "Flags does not contain sq_SOUTH"
	EndIf
	
	If (sq_EAST & Flags)
		Print "Flags contains sq_EAST"
	Else
		Print "Flags does not contain sq_EAST"
	EndIf
	
	If (sq_WEST & Flags)
		Print "Flags contains sq_WEST"
	Else
		Print "Flags does not contain sq_WEST"
	EndIf
	
	If (sq_VISITED & Flags)
		Print "Flags contains sq_VISITED"
	Else
		Print "Flags does not contain sq_VISITED"
	EndIf
End Function

EDIT: Ah weird, I did this using an integer, I'll play with a byte and post it soon.

Thanks for your time I look forward to your help.

SuperStrict

Const WALL_NORTH:Int = $01
Const WALL_EAST:Int = $02
Const WALL_SOUTH:Int = $04
Const WALL_WEST:Int = $08
Const LOC_VISITED:Int = $10
Const LOC_SPARE1:Int = $20
Const LOC_SPARE2:Int = $40
Const LOC_SPARE3:Int = $80


Local mypos:Int = WALL_EAST

Print "Exits are : " + Exits(mypos)

If Not IsVisited(mypos) Then
	Print "Not visited yet"
End If

Visit(mypos)

If IsVisited(mypos) Then
	Print "We've been here before!"
End If



Function Visit(pos:Int Var)
	pos:| LOC_VISITED
End Function

Function IsVisited:Int(pos:Int)
	Return pos & LOC_VISITED
End Function

Function Exits:String(pos:Int)
	Local s:String
	
	' invert bits
	pos = ~pos
	
	If pos & WALL_NORTH Then
		s:+ "North "
	End If

	If pos & WALL_EAST Then
		s:+ "East "
	End If

	If pos & WALL_SOUTH Then
		s:+ "South "
	End If

	If pos & WALL_WEST Then
		s:+ "West "
	End If

	Return s
End Function

Edited my post, seems I was on Brucey's tail.
EDIT: Clever exits function Brucey :)

Thank you very much gentlemen. I'll divine the code a "bit" tomorrow. (Yes that was a pun) I appreciate your prompt information.

How many flags can we store in a byte?

8 (8 bits in a byte)

How many bytes are in an integer?

I know maxgui uses integers for flags, how many flags can an integer hold?

Print SizeOf(a)

:-p

So 32 flags? Kewl.

Yah and a Long has 64.

You simply `set` a bit with:

Flags:| BitMask

and you clear it with

Flags:& ~BitMask

BitMask is a binary number with a 1 where you want the flag to be, so for the 4th bit it's %00000000000000000000000000010000:Int

Very helpful, thanks all.

EDIT: Question: is %00000000000000000000000000000001 correct for the *first* value? Or should I always start from %00000000000000000000000000000010?

Yes - that's a value of 1. I think ImaginaryHuman has confused you by saying the 4th bit, when his example has the 5th bit set.

%00000010 is 2, %00000011 is 3 (bits 2+1), %00000100 is 4, %00000101 is 5 (bits 4+1) and so on.

You can use Print Bin(value) to show a binary representation of an integer.

Also you don't need all those leading zeros. %00000000000000000000000000000001 is the same as %1. Everything to the left of the 1 is implied as zero.

Isn't it easier to read Hex?

$0001
$0002
$0004
$0008
$0010
...

Less figures...

I have no clue how you continue adding in hex, at first it looks like your adding the last value to itself.. then it changes to $0010..

..and so on..
$0010
$0020
$0040
$0080
$0100
$0200
$0400
$0800
$1000
...

That's exactly right. $0010 expressed as decimal, is 16. The sequence would be $0009, $000A, $000B, $000C, $000D, $000E, $000F, $0010, $0011..... etc.

I prefer using binary as I find it more readable. Each to their own.

So basically its easier to write just as an integer - I mean your just using more complicated ways of writing lastval*2 = nextflag..

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, etc.. (the individual flag is going to be stored in an integer anyways, so what's the point of using hexadecimal/binary?)

Hex is easier to remember than a big integer value - well, it is for me.

Depends where you are coming from, I suppose :-)

I notice you shift to the left once you reach the 4th (an 8) in the hexidecimal number, restarting with '1'.
Do you continue to do that after $1000? ($2000, $4000, $8000, $10000??)

yes and no, it works like this:

Local h:Int = 1

For i:Int = 0 To 31
	n:Int = h Shl i
	Print RSet(String(n),16)+ " "+ Hex(n) + "  "+ Bin(n)
Next

I hope the negative doesn't throw you off. The thirty second bit is used by blitzmaxt to represent negative numbers.

In your code, Jesse, you skip over the first possible value (i = 0, 1 00000001 00000000000000000000000000000001), should we not be using #1, or is that just a flaw with your listing?

EDIT:
But we can still use it as a flag?

just a flaw. and yes you can use the last bit as a flag.

[edited]
fixed my previous post.