Roku Developer Program

[kbenson]

Yeah, me again. I promise this time it's easier and more feasible

Any chance of getting bitwise xor, left shift and right shift ops? I've implemented my own, but it's nowhere near as fast. At least the shifts aren't. Xor is easy, but does require combining 5 other ops (and a function call, if you want it pretty).

[RokuKevin]

I don't think we'll have these language primitive ops in the near future.... However, the logical operators or,and, and not are also bitwise operators.... So the operations you are asking for can be implemented in terms of those base bitwise operations.

Example:

    a% = 6
    b% = 10
    print "a = ";a% ;" b = "; b%

    bitwiseAnd% = a% and b%
    bitwiseOr% = a% or b%
    bitwiseXOr% = bitwiseOr% and not bitwiseAnd%

    print "a xor b  = "; bitwiseXOr%

    bitwiseLeftShift% = a% * 2

    print "a << 1 = "; bitwiseLeftShift%
    
    bitwiseRightShift% = a% / 2

    print "a >> 1 = "; bitwiseRightShift%

--Kevin

[kbenson]

Understood about the xor, it just seems that since there are the bitwise operations for AND, OR, and NOT, an XOR would be trivial to add and complete the offering.

As for shift, left shifting is easy, because it's multiplication. Right shift is division, which results in a float. It's not as ideal. The following is what I have, and it works without division (which is key), but it's obviously nowhere near as fast as a native implementation would be:

function rshift(num as integer, n=1 as integer) as integer
        mult = 2^n
        sumand = 1
        total = 0
        for i = n to 31
                if (num and sumand * mult)
                        total = total + sumand
                end if
                sumand = sumand * 2
        end for

        return total
end function

[RokuKevin]

That's why I used the '%' character at the end of all my variables. That forces the types to be integers, and then the division to be integer division rather than floating point.

--Kevin

[kbenson]

Actually, that's not how I'm seeing it work, so won'y help my problem.

From the BrigthtScript 2.0 Reference, section 3.5 Type Conversion (Promotion)

"Division follows the same rules as +, * and -, except that it is never done at the integer level: when
both operators are integers, the operation is done as float with a float result."

And heres code to illustrate the actual problem:

print "float division (default)"
n = -306674914
print "n: "; n
print "n/2: "; (n/2)
print "int(n/2): "; int(n/2)
r% = n/2
print "r% = n/2, r%: "; r%

print "integer division"
n% = -306674914
print "n%: "; n%
print "n%/2: "; (n%/2)
print "int(n%/2): "; int(n%/2)
r% = n%/2
print "r% = n%/2, r%: "; r%
d% = 2
print "d%: "; d%
r% = n%/d%
print "r% = n%/d%, r%: "; r%

print "double division"
n# = -306674914
print "n#: "; n#
print "n#/2: "; (n#/2)
print "int(n#/2): "; int(n#/2)
r# = n#/2
print "r# = n#/2, r#: "; r#
d# = 2
print "d#: "; d#
r# = n#/d#
print "r# = n#/d#, r#: "; r#

And here's the output. Keep in mind that -306674914/2 is -153337457, NOT -153337456

float division (default)
n: -306674914
n/2: -1.53337e+08 
int(n/2): -153337456
r% = n/2, r%: -153337456
integer division
n%: -306674914
n%/2: -1.53337e+08 
int(n%/2): -153337456
r% = n%/2, r%: -153337456
d%:  2
r% = n%/d%, r%: -153337456
double division
n#: -306674914 
n#/2: -153337457 
int(n#/2): -153337456
r# = n#/2, r#: -153337457 
d#:  2 
r# = n#/d#, r#: -153337457 

As you can see, division can be somewhat problematic due to floating point rounding errors. You CAN get around it, but only by going explicitly to double precision. You will experience the same rounding errors in double precision if your numbers are large enough. I'm not sure how to force integer division.

[EnTerr]

"kbenson" wrote:
"Division [...] is never done at the integer level: when both operators are integers, the operation is done as float with a float result."
[...] can be somewhat problematic due to floating point rounding errors. You CAN get around it, but only by going explicitly to double precision. You will experience the same rounding errors in double precision if your numbers are large enough. I'm not sure how to force integer division.

Yes, quite right you are - in B/S division of integers is always done as floats. So was the case four years ago and so it is today (and likely forever). It's been so long, you likely moved to better pastures and don't care about bitwise operations in BS no more - but i was looking for discussion of right shift in the forum and this is about the only relevant post, so i will drop my note here.

Some right shifts can be done using float division - we just have to be vewy vewy careful. First, how much precision does a float have? An educated guess (confirmed by experiments) would be that a B/S float is an IEEE-754 "single", which is stored in 4 bytes and has 24 bits of precision.

Here is a demonstration - i am starting with &h1000000, which is the 25-bit number 0b1,00000000,00000000,00000000 - so one bit of precision is bound to be lost if we store it in float - and i also divide by 1 (extreme case that shouldn't have changed the number but forces it into float):

BrightScript Debugger>for i = 0 to 255: x = &h01000000 or i: y = int(x / 1):  ? i, y and &hFF, x, y: end for
 0               0               16777216        16777216
 1               0               16777217        16777216
 2               2               16777218        16777218
 3               4               16777219        16777220
 4               4               16777220        16777220
 5               4               16777221        16777220
 6               6               16777222        16777222
 7               8               16777223        16777224
 8               8               16777224        16777224
 9               8               16777225        16777224
 10              10              16777226        16777226
 11              12              16777227        16777228
 12              12              16777228        16777228
 13              12              16777229        16777228
 14              14              16777230        16777230
 15              16              16777231        16777232
 16              16              16777232        16777232
...
 250             250             16777466        16777466
 251             252             16777467        16777468
 252             252             16777468        16777468
 253             252             16777469        16777468
 254             254             16777470        16777470
 255             0               16777471        16777472
BrightScript Debugger> 

Note how all even numbers come true through the ordeal, where all odd numbers come short by 1 (except last one that is bumped +1).

What are the practical implications of this? Well, if i need 24 or less bits from the number after shifting - then division is the right operation. For example, if i need to shift right by 8 bits - "/ &h100"; by 16 - "/ &h10000" and so on. And i bet division will be faster to do than a loop bit by bit. Or you can just use double and rely that its 53 bits of precision will truthfully handle the 32 bits of an int.

One more thing - a new operator MOD was added for Brightscript 3 (sometime in 2011 i believe), it is the "modulo" operation - "x mod y" returns the remainder of dividing x by y; e.g. 8 mod 3 = 2. You can take advantage of that by adding the following two lines near the beginning of your routine - in a way that is "did i get the right result by dividing? if yes - great, if no - let's use alternative way":

total = int(num / mult)
if total * mult + num mod mult = num then return total