Page 1 of 1
bit shifting
Posted: Fri Mar 10, 2006 9:07 am
by Seb McClouth
I now how I can do the C
in QB which is
Now I need to know can I can do
Code: Select all
val >> 1
val >> 2
val >> 3
val << 1
val << 2
val << 3
val << 4
I haven't been able that out yet.
thx
Grtz
Posted: Fri Mar 10, 2006 9:46 am
by RyanKelly
The important thing to remember is that shifting right by one bit position has the same effect as dividing an UNSIGNED integer by two. Shifting left one position has the same effect as multiplying an UNSIGNED integer by two.
So, shifting right 4 positions can be done by dividing by 2*2*2*2= 2^4=16. Shifting right two positions : 2*2 =2^2=4.
Shifting left is practically the same, but you have to account for the sign bit. With 16 bit signed integers, bit 15 is the sign bit, so should you try to shift the binary integer 0100000000000000 left one position by using multiplication, you'll wind up with an overflow error. The avoid this, store your initial bit field in a 32 bit long integer, perform the multiplication, then mask out the high 16 bits.
Code: Select all
Example:
x = x << 3
x = x *2*2*2=x*2^3=x*8
temp&= x%
temp&=(temp&*8) and &hffff
x%=temp&
Posted: Fri Mar 10, 2006 10:04 am
by Seb McClouth
thx this is really usefull!!!
grtz
Seb
Posted: Sat Mar 11, 2006 8:35 pm
by Seb McClouth
I have developed a tiny FUNCTION (which I gonna use in Qbinux).
Code: Select all
DECLARE FUNCTION BitShift(value1, cmd$, value2)
x = 87
x = BitShift(x,">>", 3)
FUNCTION BitShift (value1, cmd$, value2)
IF cmd$ = "<<" THEN
'"value1" has to be shifted "value2" bit(s) to the left.
'formula: x = x * 2 ^ y
x = value1 * 2 ^ value2
temp& = x%
temp& = (temp& * x ^ value2) AND &HFFFF
BitShift = temp&
ELSEIF cmd$ = ">>" THEN
'"value1" has to be shifted "value2" bit(s) to the right.
'formula: x = x / 2 ^ y
BitShift = INT(x * 2 ^ value2)
END IF
END FUNCTION
grtz
Posted: Mon Mar 13, 2006 9:30 pm
by moneo
Seb, down near the end of your posted code, you have:
The multiply should be a divide, like:
To make sure that the exponentiation is performed first, which it should be, but just for clarity, I would do:
*****
Posted: Mon Mar 13, 2006 10:35 pm
by RyanKelly
Seb, this function should work. You can drop the "%" suffix of the variable x if you've used the DEF INT statement at the module level.
There might be a few ways you could speed this up, though. First, using QB's exponentiation operator "^" is pretty slow. Since this function only works for 16 bit positive integers (negative integers will give you a problem because the sign bit won't move), you could use a precalculated look up table. You could declare a global array BSHIFTVALUES(0 to 15) and initialize BSHIFTVALUE(i)=2^i before any call to your function is ever made. Then simply replace any occurence of 2^X with BSHIFTVALUE(value2) This way the calculation only needs to be performed once and at a time when speed isn't significant, and the only trade off is 32 bytes of memory plus the array descriptor and the need to ensure that value2 < 16, which could be done with the statement "value2=value2 AND &hF" at the top of your function since any bit shift beyond 15 bits will have the same result as when value2=0.
Posted: Tue Mar 14, 2006 4:32 am
by Seb McClouth
THx Moneo... that would have given some mayor crap output, hahaha.
Thx Ryan for you explanation. I'm trying to 'shift' this in.
grtz
Seb
Posted: Tue Mar 14, 2006 6:53 am
by Seb McClouth
I did a little work.
Code: Select all
DECLARE FUNCTION BitShift(value1, cmd$, value2)
COMMON SHARED BSHIFTVALUES() AS INTEGER
DIM SHARED BSHIFTVALUES(0 TO 15 AS INTEGER)
FOR A = 0 TO 14 '15 is kinda 2much
BSHIFTVALUES(A) = 2 ^A
NEXT
x = 87
x = BitShift(x,">>", 3)
FUNCTION BitShift (value1, cmd$, value2)
value2 = value2 AND &HF
IF cmd$ = "<<" THEN
'"value1" has to be shifted "value2" bit(s) to the left.
'formula: x = x * 2 ^ y
temp1 = value1 * BSHIFTValues(value2)
temp2& = temp1
temp2& = (temp2& * BSHIFTValues(value2) AND &HFFFF
BitShift = temp&
ELSEIF cmd$ = ">>" THEN
'"value1" has to be shifted "value2" bit(s) to the right.
'formula: x = x / 2 ^ y
BitShift = value1 / BSHIFTValues(value2)
END IF
END FUNCTION
I only have one problem, I get a **divided by zero** error when running, whilst I didn't get this with the old way.
Can someone help me out on this one?
thx
[corrected source code]
Posted: Tue Mar 14, 2006 8:08 pm
by moneo
You just made a spelling error, that's all. The array is called BSHIFTVALUES, and near the end of the function, you divided by BITSHIFTvalues, which doesn't exist, so you're dividing by zero.
Don't use such long variable names, looks like Cobol.
*****
Posted: Tue Mar 14, 2006 8:19 pm
by RyanKelly
Seb, I have to apologize for an error of mine in my last response. I said that shifting over 15 bits would have the same result as shifting 0 bits, and that's really really wrong. Shifting by over fifteen bits should set the variable to 0, whereas shifting by no bits should leave the variable unchanged.
I suggest adding a conditional after the AND statement at the top of the function. Test if the result of the AND is zero, and if so, just return zero, otherwise proceed. As for the look up table, you'll need to be able to reference array elements up to 15 because 15 is the largest possible result of value2=value2 AND &HF
I'll never understand why QB didn't have built in bit manipulation. All this code to accomplish the equivalent of one machine instruction is insane.
Posted: Wed Mar 15, 2006 9:23 am
by Seb McClouth
That's why I'm writing a library... So it will just exist and be usable.
You're suggesting to add a simple IF...THEN...ELSE to check if value2 = 0 after the AND &HF?
Code: Select all
IF value2 = 0 THEN BitShift = 0: EXIT FUNCTION
I added but I still get the division by zero error...
grtz
Posted: Wed Mar 15, 2006 9:13 pm
by moneo
Seb,
If you're going to validate "value2", the number of bit positions to be shifted, then you need to keep the following in mind.
1) It's possible that the user could set "value2" to zero, meaning, in this case, that the number in "value1" does not get shifted but stays the same. Note that 2^0 is 1. This zero should be considered as valid, and the shifting logic will handle it correctly as is. Remember that when the user specifies "value2" he doesn't necessarily hard-code it into your function parameters. He may have done a calculation to derive the value, in which case, he could specify a zero.
2) If you want to validate "value2", then you should make sure that it's not negative, and that it's not greater than 16. If you shift a 16 bit number either left or right 16 bit positions, the result should be zero. WATCH OUT, if "value2" can be 16, then your array must go from 0 to 16.
If "value2" is invalid, you can't just exit with "value1" equal to zero, since "value1" can be zero in many cases. You need another parameter to indicate valid/invalid. To add this parameter, you may have to convert your Function into a Sub, so that the user can call the Sub, test the valid/invalid parameter, and then, if valid, use the result in "value1".
3) Another validation you need is making sure that "value1" is a 16 bit number, that is, an integer. Otherwise, if "value1" is single, double or long, the logic won't work at all. You could use the same valid/invalid parameter for this.
*****