Developers and content creators—a complete solution for growing an audience directly.

Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

- Roku Community
- :
- Developers
- :
- Roku Developer Program
- :
- Suggestion box - more bitwise ops

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

kbenson

Level 7

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

07-19-2010
06:34 PM

Suggestion box - more bitwise ops

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!

Check out Reversi! in the channel store!

5 Replies

RokuKevin

Level 9

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

07-21-2010
05:42 PM

Re: Suggestion box - more bitwise ops

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

Level 7

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

07-21-2010
06:26 PM

Re: Suggestion box - more bitwise ops

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!

Check out Reversi! in the channel store!

RokuKevin

Level 9

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

07-22-2010
10:50 AM

Re: Suggestion box - more bitwise ops

--Kevin

kbenson

Level 7

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

07-22-2010
12:09 PM

Re: Suggestion box - more bitwise ops

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!

Check out Reversi! in the channel store!

EnTerr

Level 11

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

05-31-2014
01:18 PM

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 forNote how all even numbers come true through the ordeal, where all odd numbers come short by 1 (except last one that is bumped +1).

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>

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