binary arithmatic

BlitzMax Forums/BlitzMax Beginners Area/binary arithmatic

Ghost Dancer

(Posted 2006) [#1]

Hi

I'm trying to do some simple binary arithamtic, but in addition to the fact that my binary is a little rusty, I can not find out the Blitz Max syntax/commands for doing what I need.

Bascially I have 2 variables that consist of 4 bits each (each bit represents the edge of a tile) and I am doing a logical And to determine whether the tile will "fit" inside the other. This bit is fine, e.g.

var1 = %1110
var2 = %0110

If var1 & var2 = var2 then
 'do stuff
end if

This works just fine. However, I also need to do a "bitwise rotate" on these values. By rotate, I mean similar to a bitwise shift, but the bits wrap around, so rotating %1000 left by one would result in %0001, %1100 would be %1001 etc.

I thought I might be able to do it by converting the binary to a string, rotating it, then converting back. There are two problems with this - first, it does not seem a very effcient way of doing it, and second, I can not find a way of converting the binary string back to an integer value.

I'm sure this is simple to do but my brain refuses to cooperate with me ;-) Any help would be greatly appreciated.

Dreamora

(Posted 2006) [#2]

Here are functions for this shift in variable bitlength including a short sample:

b=%1010
For i=1 To 33
	Print Bin(b)
	b=whr(b,4)
Next
b=%1010
For i=1 To 33
	Print Bin(b)
	b=whl(b,4)
Next


Function WHR:Int(number:Int, bitlength:Int=32)
	If number & 1
		Return ( (number Shr 1) | (%1 Shl (bitlength-1)))
	Else
		Return (number Shr 1)
	EndIf
End Function

Function WHL:Int(number:Int, bitlength:Int=32)
	If number & (1 Shl (bitlength-1))
		Return ( ((number Shl 1) ~ (1 Shl (bitlength)) )| 1 )
	Else
		Return (number Shl 1)
	EndIf
End Function

Ghost Dancer

(Posted 2006) [#3]

I knew there was an elegant solution. Thanks Dreamora :-)

ImaginaryHuman

(Posted 2006) [#4]

Seems longwinded. Do the whole thing at once.

Local b:Int=%1100
Local BitsToShift:Int=1
Local Mask:Int=%00001111
Local Mask2:Int=%11110000
If BitsToShift>0
   b:Shl BitsToShift
Else
   b:Shl 4-Abs(BitsToShift)
EndIf
b=((b & Mask2) Shr 4) | (b & Mask)
Print b

Should print %1001. You can only reliably rotate by up to the number of bits in the number, no more. You need to do the shifting of a value within a variable that is twice the number of bits of how many bits you are working with. With an int you can handle up to 16 bits binary. The masks contain set bits for how many bits you're working with. 16 bit would be %11111111111111110000000000000000 and vice versa.

Ghost Dancer

(Posted 2006) [#5]

I've been adapting Dreamoras functions (I need the flexibility) so I can rotate by a variable number of bits. The rotate right (WHR) seems to be working, but I'm having trouble with the left (WHL). Here is the code:

Function WHL:Int(number:Int, bitlength:Int=32, roll=1)
	If number & (1 Shl (bitlength-roll))
		Return ( ((number Shl roll) ~ (1 Shl (bitlength)) )| 1 )
	Else
		Return (number Shl roll)
	EndIf
End Function

Function WHR:Int(number:Int, bitlength:Int=32, roll=1)
	If number & 1
		Return ( (number Shr roll) | (%1 Shl (bitlength-1)))
	Else
		Return (number Shr roll)
	EndIf
End Function

Any ideas?

ImaginaryHuman

(Posted 2006) [#6]

You can rotate by a variable number of bits with my code also.... that's what the BitsToShift variable is for. If it's a positive number it will rotate left, otherwise it rotates right.

Ghost Dancer

(Posted 2006) [#7]

Ah nice, but I was thinking it would be good to have some general purpose functions that would work for any bit length as well. Isn't your code limited to only 4 bits? I'm sure it could be modified but I'm don't know how to dynamically change the masks for other bit lengths?

I'm sure this would be of use to others, and would probably make a nice addition to the code archives.

ImaginaryHuman

(Posted 2006) [#8]

The code is not limited to 4 bits. It is limited to however many bits you are working with. You gave a 4-bit binary in the example so I showed you how to do it with 4 bits. You can fit 16 bits into an Int or use a Long to store 32 bit data.

ImaginaryHuman

(Posted 2006) [#9]

Here's how you would handle a 32-bit binary number and rotate it:

Local b:Long=%11000100100110000111111000010100:Long
Local BitsToRotate:Int=-19
Local Mask:Long=$00000000FFFFFFFF:Long
Local Mask2:Long=$FFFFFFFF00000000:Long
If BitsToShift>0
   b:Shl BitsToRotate
Else
   b:Shl 32-Abs(BitsToRotate)
EndIf
b=((b & Mask2) Shr 32) | (b & Mask)
Print Hex$(Int(b))

You can rotate up to 32 bits in either direction. Well, maybe 31, as 32 doesn't make sense. Just adjust the BitsToRotate variable.

Dreamora

(Posted 2006) [#10]

Still, it is not dynamic.

It does only work for 32bit. If you want to wrap a 14bit number, it will break.
*thats why I did mine the way I did. It might not look like the cleanest solution, but the only way I could think that is efficient on variable bitlength. First I thought of a similar solution as you. But the loops needed to dynamically create the flag would break any use of bitoperations*

ImaginaryHuman

(Posted 2006) [#11]

Flexibleized:

Local b:Long=%1111000010100:Long 'Whatever amount of bits 
you like up to 32
Local BitsIntNumber:Int=13 'How many bits are in your number, up to 32
Local BitsToRotate:Int=-7 'From -BitsInNumber to +BitsInNumber
Local Mask:Long=$00000000FFFFFFFF:Long Shr 32-BitsInNumber
Local Mask2:Long=$FFFFFFFF00000000:Long Shr 32-BitsInNumber
If BitsToShift>0
   b:Shl BitsToRotate
Else
   b:Shl BitsInNumber-Abs(BitsToRotate)
EndIf
b=((b & Mask2) Shr BitsInNumber) | (b & Mask)
Print Hex$(Int(b))

Should be easy enough to put it into a function.

Dreamora

(Posted 2006) [#12]

If you replace

Local Mask2:Long=$FFFFFFFF00000000:Long Shr 32-BitsInNumber

with

Local Mask2:Long=$FFFFFFFF00000000:Long Sar 32-BitsInNumber

the mask will even stay F all on the left.

*sadly there is no sal for some reason*

Ghost Dancer

(Posted 2006) [#13]

Thanks guys, I'm at work at tho mo, but when I get home I should be able to functionise that.

BTW, what's the difference between Shr and Sar?

ImaginaryHuman

(Posted 2006) [#14]

I agree about the mask, Dreamora, except that it is not needed. It only needs to cover the number of bits in the number.

Shr shifts the number right and inserts 0's at the top end of the variable. Sar looks at the highest bit - which represents whether the number is positive or negative, and then if you shift right it reproduces the state of that bit in any bits that would've become zero's, at the top end of the variable. You don't need to use it in my code.

Ghost Dancer

(Posted 2006) [#15]

OK, we're looking good. I've made it into a function (see below). It seems to work with just about everything I throw at it, except it doesn't always work with 32 bit values (I think it's only when the most significant bit is 1).

It's fine for what I need it for, but it would be nice to get it fully working should anyone else require it.

Thanks again for your help, it's been about 10 years since I've done stuff like this!


Print Bin(rotateBits(%1100, 4, -1)) 'rotate right by 1 bit

Function rotateBits:Int(number:Long, bitLength:Int = 32, rotate:Int = 1)
	Local mask1:Long = $00000000FFFFFFFF:Long Shr (32-bitLength)
	Local mask2:Long = $FFFFFFFF00000000:Long Shr (32-bitLength)

	If rotate > 0
	   number:Shl rotate
	Else
	   number:Shl bitLength - Abs(rotate)
	EndIf
	
	number = ((number & mask2) Shr bitLength) | (number & mask1)
	
	Return number
End Function

ImaginaryHuman

(Posted 2006) [#16]

You could do

Local mask2:Long=Mask1 Shl bitLength

to make the second mask.

What problem do you get with 32-bit numbers? It should work from what I can tell.

Ghost Dancer

(Posted 2006) [#17]

if you do the following:

Print Bin(rotateBits(%10000000000000000000000000000000, 32, -1))

you get:
11000000000000000000000000000000

instead of
01000000000000000000000000000000

ImaginaryHuman

(Posted 2006) [#18]

I think it's to do with conversion from Int to long, because you actually are passing an Int to the function rather than a long, and yet it's taking a Long parameter. That might well extend the sign bit of the int through to 64-bit, not sure.

Either way, try:

Function rotateBits:Int(num:Int, bitLength:Int = 32, rotate:Int = 1)
'create masks
Local number:Long=Long(num) & mask1

see if that helps.

Alternatively, if you are specifying a literal constant in the parameter you are passing as a number, which you are, you should really put :Long at the end of it to specify that it is a Long value not an Int, if your function says it should be a Long.

ie

Print Bin$(RotateBits(%10000000000000000000000000000000:Long,32,-1))

Maybe those two things will help.

Does it work ok with a 31-bit number?

Ghost Dancer

(Posted 2006) [#19]

Ah, I see what you are gettig at. I (wrongly) assumed it would be cast as a long since that was the function parameter was. (BTW, 31 bits was fine)

Problem solved, thanks. The complete function is now:

Function rotateBits:Int(num:Int, bitLength:Int = 32, rotate:Int = 1)
'bitLength can be anything up to 32
'if rotate > 0 then rotates left, < 0 rotates right
	Local mask1:Long = $00000000FFFFFFFF:Long Shr (32-bitLength)
	Local mask2:Long=mask1 Shl bitLength
	
	Local number:Long = Long(num) & mask1	'force number to a long to avoid probs with bit 32

	If rotate > 0
	   number:Shl rotate
	Else
	   number:Shl bitLength - Abs(rotate)
	EndIf
	
	number = ((number & mask2) Shr bitLength) | (number & mask1)
	
	Return number
End Function

Thanks for all your help :) Hopefully others will find this useful too...

ImaginaryHuman

(Posted 2006) [#20]

Ahh, good, glad it works right now. I didn't realize for a long time that you had to put :Long on the end to make things work right, but it does help, otherwise Blitz internally thinks of it as a signed Int or something.

I personally think it would help if BRL added Ror and Rol as commands to complement Shl and Shr.

Dreamora

(Posted 2006) [#21]

Definitely :-)
And Sal as Sar is in already.

Ghost Dancer

(Posted 2006) [#22]

Yes, that would be nice, but at least (thanks to you guys) we now have an alternative :-)

ImaginaryHuman

(Posted 2006) [#23]

Here is an unsigned 64-bit version! You can rotate up to a 64-bit number, by any number of bits, even more than +- 64.

It doesn't matter if your number is signed or unsigned, it will just rotate all bits. If your number is signed, be prepared for it to change from + to - unpredictably. This code is untested but I *think* it's right.

Since a rotate left by a given number of bits gives the same result as a rotate right by the bitLength minus the given number of bits, both routines for left and right rotates use basically the same code shifting in the same direction. I've made it so they share the last few steps because they are the same. There are only minor differences to do with using rotate or bitLength-rotate etc.

The routine basically is doing a two cut-and-paste operations, one on the lower group of bits which are shifted to the top of the number, and one for the top group of bits that are shifted to the bottom of the number. The two groups basically just swap with each other.

Let me know if it works.

Function rotateBits:Long(number:Long, bitLength:Int = 64, rotate:Int = 1)
'bitLength can be anything from 1 to 64
'rotate can be anything, even more than the number of bits
'if rotate > 0 then rotates left, < 0 rotates right

        bitlength=Min(bitLength,64) 'Errorcheck, not too many!
        rotate:mod bitLength 'Errorcheck/wrap - supports rotate>bitLength

	Local mask1:Long = $FFFFFFFFFFFFFFFF:Long Shr (64-bitLength) 'all relevant bits only
	
	number:& mask1	'make sure number complies with how
'many bits we said it has - allows you ignore upper bits if
'bitLength < actual number of bits in number. This is just
'errorchecking and could be removed.

        Local mask2,number2,number3:Long
        If rotate > 0 Then rotate = bitLength-rotate else rotate = Abs(rotate) 'Adjust based on left or right
	'Create mask for cutting bottom part
        mask2 = mask1 shr (bitLength-rotate)
        'Cut bottom, shift to top
        If rotate > 0 Then number2 =(number & mask2) shl (rotate)) Else number2 =(number & mask2) shl (bitLength-rotate))
	'Create mask for cutting top part
        mask2 = (~mask2) & mask1
        'Cut top, shift to bottom
        number3 =((number & mask2) shr rotate)
        Return number2:| number 3 'combine top and bottom and return it 64-bit rotated!
End Function

Here's the bare code with no comments:

Function rotateBits:Long(number:Long, bitLength:Int = 64, rotate:Int = 1)
        bitlength=Min(bitLength,64)
        rotate:mod bitLength
	Local mask1:Long = $FFFFFFFFFFFFFFFF:Long Shr (64-bitLength)
	number:& mask1
        Local mask2,number2,number3:Long
        If rotate > 0 Then rotate = bitLength-rotate else rotate = Abs(rotate)
        mask2 = mask1 shr (bitLength-rotate)
        If rotate > 0 Then number2 =(number & mask2) shl (rotate)) Else number2 =(number & mask2) shl (bitLength-rotate))
        mask2 = (~mask2) & mask1
        number3 =((number & mask2) shr rotate)
        Return number2:| number 3
End Function