bit shifting

[Seb McClouth]

I now how I can do the C

Code: Select all

val >> 4

in QB which is

Code: Select all

INT(val / 16)  'Thanks to Moneo

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

[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&

[Seb McClouth]

thx this is really usefull!!!

grtz
Seb

[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

[moneo]

Seb, down near the end of your posted code, you have:

Code: Select all

BitShift = INT(x * 2 ^ value2) 

The multiply should be a divide, like:

Code: Select all

BitShift = INT(x / 2 ^ value2)

To make sure that the exponentiation is performed first, which it should be, but just for clarity, I would do:

Code: Select all

BitShift = INT(x * (2 ^ value2))

*****

[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.

[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

[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]

[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.
*****

[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.

[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

[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.
*****