Roku Developer Program

Join our online forum to talk to Roku developers and fellow channel creators. Ask questions, share tips with the community, and find helpful resources.
cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
kbenson
Visitor

Suggestion box - more bitwise ops

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).
-- GandK Labs
Check out Reversi! in the channel store!
0 Kudos
5 REPLIES 5
RokuKevin
Visitor

Re: Suggestion box - more bitwise ops

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
0 Kudos
kbenson
Visitor

Re: Suggestion box - more bitwise ops

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
-- GandK Labs
Check out Reversi! in the channel store!
0 Kudos
RokuKevin
Visitor

Re: Suggestion box - more bitwise ops

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
0 Kudos
kbenson
Visitor

Re: Suggestion box - more bitwise ops

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.
-- GandK Labs
Check out Reversi! in the channel store!
0 Kudos
EnTerr
Roku Guru

Re: Suggestion box - more bitwise ops

"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
0 Kudos