Bitwise operators

Monkey Forums/Monkey Programming/Bitwise operators

Raz	(Posted 2013) [#1]

I'm going to really show myself up here a bit, but.... I don't use bitwise operators. I understand them, but what I don't understand is how they are considered useful?

Can anyone give me some game development related examples of where they are useful?

Skn3	(Posted 2013) [#2]

The example below is probably one of the more common uses.

Const OPTION_1:= 1
Const OPTION_2:= 2
Const OPTION_3:= 4
Const OPTION_4:= 8
Const OPTION_5:= 16
Const OPTION_6:= 32

Function DoSomething:Void(options:Int)
	If options & OPTION_1
		'do option 1
		Print "Option 1"
	EndIf
	
	If options & OPTION_2
		'do option 2
		Print "Option 2"
	EndIf
	
	If options & OPTION_3
		'do option 3
		Print "Option 3"
	EndIf
	
	If options & OPTION_4
		'do option 4
		Print "Option 4"
	EndIf
	
	If options & OPTION_5
		'do option 5
		Print "Option 5"
	EndIf
	
	If options & OPTION_6
		'do option 6
		Print "Option 6"
	EndIf
End

Function Main:Int()
	DoSomething(OPTION_1 | OPTION_3 | OPTION_6)
	Return 0
End

If you are storing stuff in a database or sending over a network this is very useful. You can pack a lot of options into one integer instead of 1 byte per option.

It's good in object initialization as you can create a generic object create api with a single options or style param. Each object class can then decide how to interpret the options to create an object.

dawlane

(Posted 2013) [#3]

Well one example is to use them for game flags in stead of using bool data types (saves some memory as bool would be 4 bytes in size). Use an int data type and use bitwise OR to set an individual bit and then use a bitwise AND to see if it's set.

You could then do something like use individual bits of a int as a method to determine what direction a player is to move when a button or key has been pressed just by setting it and then checking for it in your programme loop.
You can also use bitwise data for compressing your game level data. Just like it was done on the old 8bit computers where memory was tight. See here for how Alien 8 for the ZX Spectrum was done.

The bit wise shift functions can be used as a fast method for multiplication/division.

If you do a bit of googling you should find plenty of examples for other uses.

Read through skids code here for a another.

Raz	(Posted 2013) [#4]

Thanks you two :D

That data packer looks like it could be useful for level file downloading too :)

Gerry Quinn

(Posted 2013) [#5]

They can be useful for fast AI algorithms as well. For example, most professional chess programs use 'bitfields' for representing board positions. Like with the flags, the object is to get the most value out of an int, and you have the ability to use logical operations which can operate on 32/64 bits at once.

You can have examples of this with the flags, as well. If you had a series of Bools storing flags to mean different things, then if you wanted to know if conditions 1, 4 and 5 are true you have to do three tests. But if they are packed into a single int as bits, you can do all sorts of such tests in one or two operations.

Flags 0..9 = 1, 2, 4, 8, 16, 32, 64, 128, 256. 512

Say I have an int with all these flags set or unset. I want to know if at least one of flags 1, 2 and 4 (values 2, 4, 16) is set. All I need to do is say:

If ( flags & 22 ) <> 0
' At least one is set
End

And if I want to know if all of them are set:

If ( flags & 22 ) = 22
' All three are set
End

dawlane

(Posted 2013) [#6]

That data packer looks like it could be useful for level file downloading too :)

Be careful when using data compressed as strings as Apple OS's don't like custom string encoding.

If ( flags & 22 ) <> 0
' At least one is set
End

Just to point out. You wouldn't need to add <> 0 as any condition other than zero value equates to a bool value of TRUE. So any bit "trapped" would give a value greater than zero. You would only use the equals to check if a specific bit or number of bits are set.

A few things to remember when dealing with binary operations. It's a lot easer representing numbers in hexadecimal format than in decimal (or any other) due to the relationship that each character ( 0-9 with A-F representing 10-15) would be bits or the sum of 4 bits (a nibble) within a byte.
E.G. $FFE61216 is a lot easier to break down than 4293267990 or 11111111111001100001001000010110.

And rather than trying to remember what bit(s) is is meant to do what. You could assign a constant variable to represent it. As if I remember constant variables get hard coded into your code at compile time.

You could check for what bit(s) are set like so

Const bit4=$10 '16
Const bit2=$04 '4
Const bit1=$02 '2
If (flags & (bit4|bit2|bit1)) = $16

But once your program is complete you should add the values together and change (bit4|bit2|bit1) to that added value to do a bit of optimising.

Gerry Quinn

(Posted 2013) [#7]

"Just to point out. You wouldn't need to add <> 0 as any condition other than zero value equates to a bool value of TRUE. So any bit "trapped" would give a value greater than zero. You would only use the equals to check if a specific bit or number of bits are set."

Yeah, I know, but I like to make it explicit. I suppose I should probably write:

If Bool( flags & 22 )

..just to make sure it gets optimised away.

With the flags you can also optimise like:

Const BIT1:Int = 2
Const BIT2:Int = 4
Const BIT4:Int = 16
Const MYCOMBO:Int = BIT1 | BIT2 | BIT4

dawlane

(Posted 2013) [#8]

Const MYCOMBO:Int = BIT1 | BIT2 | BIT4

Only problem with that method is giving it a meaningful name for what it does that you can remember off the top of you head. I tend to stick to a strict naming, ordering and coding method and when I'm happy I let find and replace do all the work.

Yeah, I know, but I like to make it explicit. I suppose I should probably write:

If Bool( flags & 22 )

..just to make sure it gets optimised away.

Yeah know what you mean. But sometimes I find it just too much hard work typing those extra keywords.

Edit:
@RAZ here's a naff demo of what you could do

'Naff level demo
Strict
Import mojo

Function Main:Int()
	New CGame()
	Return 0
End Function

#Rem
	One way to store a level. 
	It's not the best way as there are a number of ways you
	could do it depending on the size of the playing area and the 
	complexity of the level.
	
	A block is 40x30 pixels (as the display is 640x480 pixels)
	and we want to place a block of a certain type in to a 16x16 grid.
	It can be crunched down into 2 bytes (16 bits)
	so we could get 2 blocks into a integer (usually 32 bits on a 32bit CPU)

        Using little-endian hi byte block type, low byte position.
	The first byte would be the X/Y position in the grid
	stored as Y/X. The second would be the block type. Each bit
	represents a colour here with the left most bit as a brighten
	colour flag. This byte could be use as a index to look up a number
	from 0-255 to give you more blocks etc.
	Then use a shift right function to get the other block data.
#End

Class CBlock
	Const BLUE:Int = $01
	Const RED:Int = $02
	Const MAGENTA:Int = $04
	Const GREEN:Int = $08
	Const CYAN:Int = $10
	Const YELLOW:Int = $20
	Const WHITE:Int = $40
	Const BRIGHT:Int = $80
	Field x:Int, y:Int, type:Int
	
	Method New(word:Int)
		Self.type = (word & $FF00)Shr 8
		Self.x = (word & $0F) * 40
		Self.y = ((word & $F0) Shr 4) * 30	
	End Method
	
	Method Draw:Void()
		Local r:Int=0, g:Int=0,b:Int=0
		If (Self.type & BLUE) Then r=0;g=0;b=160
		If (Self.type & RED) Then r=160;g=0;b=0
		If (Self.type & MAGENTA) Then r=160;g=0;b=160
		If (Self.type & GREEN) Then r=0;g=160;b=0
		If (Self.type & YELLOW) Then r=160;g=160;b=0
		If (Self.type & WHITE) Then r=160;g=160;b=160
		If (Self.type & BRIGHT)
			If r>0 Then r+=95
			If g>0 Then g+=95
			If b>0 Then b+=95
		EndIf
		SetColor(r,g,b)
		DrawRect(Self.x,Self.y,40,30)
		SetColor(255,255,255)
	End Method	
End Class

Class CLevel
	Field blocks:CBlock[]
	
	Method ReadLevelData:Void(data:Int[])
		Local current_block:Int = 0
		Self.blocks = Self.blocks.Resize(data.Length()*2)
		For Local i:Int = 0 To data.Length()-1
			Self.blocks[current_block] = New CBlock((data[i] & $FFFF0000) Shr 16)' trap 2 high bytes And shift right 16 bits	
			Self.blocks[current_block+1] = New CBlock(data[i]&$0000FFFF)
			current_block+=2
		Next
	End Method
	
	Method Draw:Void()
		For Local i:Int = 0 To Self.blocks.Length()-1
			Self.blocks[i].Draw()
		Next
	End Method
End Class

Class CGame Extends App
	Field level_data:Int[]
	Field level_control:CLevel
	
	Method OnCreate:Int()
		SetUpdateRate(30)
		Self.level_control = New CLevel
		'Level 26 blocks with colour compressed into 13 ints (13*4) = 52 bytes
		Self.level_data = [$02218222,$08238824,$04770178,$0479847A,$20B2A0BD,$04F004F1,$02F202F3,$20F420F5,$40F682F7,$04F804F9,$08FA08FB,$01FC81FD,$08FE88FF]
		Self.level_control.ReadLevelData(Self.level_data)
		Return 0
	End Method
	
	Method OnRender:Int()
		Cls
		Self.level_control.Draw()
		For Local x:Int = 0 To 640 Step 40
			DrawLine(x,0,x,480)
		Next
		For Local y:Int = 0 To 480 Step 30
			DrawLine(0,y,640,y)
		Next
		Return 0
	End Method
End Class

I could think of a few ways on how to do it for a static platform game (think Manic Miner/Jet Set Willy)
Here's the home page to some of the data formats for old ZX Spectrum games to give you some ideas.

BlitzProg

(Posted 2013) [#9]

Base 64 encoding. I created my own functions to do that, before realizing it was a very common thing and even had a name.

like, in binary (a byte is made of 8 bits): 11100000, 10001000, 10101010
this would become in base 64: 111000, 001000, 100010, 101010

With that you can choose an ASCII character to represent those.

Pro:
Copy-pastable anywhere you want
URL safe

Con:
33% larger (4 characters to represent 3 bytes)
A little processing is needed to pack/unpack data

I use it to save, pack, transfer data without fear a character would cause a mess. :D

BlitzProg

(Posted 2013) [#10]

Also since I'm a big fan of game replays I also use bitwise operation to store and retrieve commands from a particular frame. This way, if you did something really awesome, you can re-watch yourself in action or share it with other people. Example: http://www.youtube.com/watch?v=l3JHfQ3c6HE

That concept works pretty much like Skn3's Function "DoSomething", you pass an integer to the function, and you check which bits are set to determine which keys are being pressed during a particular frame.

---

And if you like encryption you can try the xor bitwise operation too http://en.wikipedia.org/wiki/XOR_cipher