comp09 wrote:

I'm trying to port a JavaScript library to Scratch, and it looks like a mess to me!

comp09 wrote:

Is there a fast way to perform bitwise operations in Scratch without converting the number in binary and using string operations? I need bitwise AND, OR, XOR, shift left (<<), shift right (>>), and logical shift right (>>>) on 32-bit integers. NOT would also be nice. It should behave the same way as it does in JavaScript. I'm trying to port a JavaScript library to Scratch, and it looks like a mess to me!

This Stack Overflow question may be helpful: https://stackoverflow.com/questions/2982729/is-it-possible-to-implement-bitwise-operators-using-integer-arithmetic

If none of you can come up with an answer, I will post a question on Stack Overflow, at the risk of downvotes.

define push: and (v1) (v2) (mask)
if <(mask) < [2]> then
    add ((v1) * (v2)) to [stack v]
else
    push: and ((v1) mod (mask)) ((v2) mod (mask)) ([sqrt v] of (mask))
    push: and ([floor v] of ((v1) / (mask))) ([floor v] of ((v2) / (mask))) ([sqrt v] of (mask))
    set [result v] to (item (last v) of [stack v])
    delete (last v) of [stack v]
    replace item (last v) of [stack v] with (((result) * (mask)) + (item (last v) of [stack v]))
end


define push: or (v1) (v2) (mask)
if <(mask) < [2]> then
    add (<<(v1) = [1]> or <(v2) = [1]>> mod (2)) to [stack v]
else
    push: or ((v1) mod (mask)) ((v2) mod (mask)) ([sqrt v] of (mask))
    push: or ([floor v] of ((v1) / (mask))) ([floor v] of ((v2) / (mask))) ([sqrt v] of (mask))
    set [result v] to (item (last v) of [stack v])
    delete (last v) of [stack v]
    replace item (last v) of [stack v] with (((result) * (mask)) + (item (last v) of [stack v]))
end


define (v1) | (v2)
push: or (v1) (v2) (4294967296)
set [result v] to (item (last v) of [stack v])
delete (last v) of [stack v]


define (v1) & (v2)
push: and (v1) (v2) (4294967296)
set [result v] to (item (last v) of [stack v])
delete (last v) of [stack v]


define ~ (x)
set [result v] to ((-1) - (x))

define push: and (v1) (v2) (mask)
if <<(mask) < [5]> and <(item (((v1) * (16)) + (v2)) of [cache v]) > [-1]>> then
    push (item (((v1) * (16)) + (v2)) of [cache v])
else
    if <<(v1) = [0]> or <(v2) = [0]>> then
        push (0)
    else
        if <(mask) < [2]> then
            push ((v1) * (v2))
        else
            push: and ((v1) mod (mask)) ((v2) mod (mask)) ([sqrt v] of (mask))
            push: and ([floor v] of ((v1) / (mask))) ([floor v] of ((v2) / (mask))) ([sqrt v] of (mask))
            pop
            set [and v1 high v] to (pop)
            pop
            set [and v1 high v] to (((and v1 high) * (mask)) + (pop))
            push (and v1 high)
            if <(mask) < [5]> then
                set [cache index v] to (((v1) * (16)) + (v2))
                repeat until <not <(length of [cache v]) < (cache index)>>
                    add [-1] to [cache v]
                end
                replace item (cache index) of [cache v] with (and v1 high)
                set [cache index v] to (((v2) * (16)) + (v1))
                repeat until <not <(length of [cache v]) < (cache index)>>
                    add [-1] to [cache v]
                end
                replace item (cache index) of [cache v] with (and v1 high)
            end
        end
    end
end

gtoal wrote:

comp09 wrote:

Is there a fast way to perform bitwise operations in Scratch without converting the number in binary and using string operations? I need bitwise AND, OR, XOR, shift left (<<), shift right (>>), and logical shift right (>>>) on 32-bit integers. NOT would also be nice. It should behave the same way as it does in JavaScript. I'm trying to port a JavaScript library to Scratch, and it looks like a mess to me!

This Stack Overflow question may be helpful: https://stackoverflow.com/questions/2982729/is-it-possible-to-implement-bitwise-operators-using-integer-arithmetic

If none of you can come up with an answer, I will post a question on Stack Overflow, at the risk of downvotes.

Do you prefer simple or fast?

You'll need to add xor and arithmetic right shift (aka signed divide by 2, watch out for round up/round down)

btw old assembly programmers trick… ~x is -x-1

simple:

--snip--

fast:

--snip--

MegaApuTurkUltra wrote:

comp09 wrote:

I'm trying to port a JavaScript library to Scratch, and it looks like a mess to me!

+1

Shifts are easy, just multiply and divide by 2, then floor or discard the top bit (by subtraction) if necessary.

For other stuff, I think Zro's code works

A left arithmetic shift by n is equivalent to multiplying by 2ⁿ (provided the value does not overflow), while a right arithmetic shift by n of a two's complement value is equivalent to dividing by 2ⁿ and rounding toward negative infinity. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2ⁿ and rounding toward zero.

comp09 wrote:

In your fast example, do the push and pop blocks just add/remove things to/from the stack list?

gtoal wrote:

comp09 wrote:

In your fast example, do the push and pop blocks just add/remove things to/from the stack list?

Yes. If you want to take it via the backpack, it's here: http://scratch.mit.edu/projects/29358020/
(the simpler one is http://scratch.mit.edu/projects/29513876/ )

gtoal wrote:

comp09 wrote:

In your fast example, do the push and pop blocks just add/remove things to/from the stack list?

Yes. If you want to take it via the backpack, it's here: http://scratch.mit.edu/projects/29513876/

Another solution is to keep a 256x256 table of the NAND function, and chop your arguments up into 8-bit bytes. Every logic function can be implemented in terms of NAND:

\x => x \& x

x | y => (x \& x) \& (y \& y)

x & y => (x \& y) \& (x \& y)

I'm not 100% sure of exor, but this is what I came up with…

x || y => (x \& (y \& y)) \& (y \& (x \& x))

G

bobbybee wrote:

I got:

x ^ y = ( (NAND(A, A) NAND NAND(B, B)) NAND (A NAND B) ) NAND ( (NAND(A, A) NAND NAND(B, B)) NAND (A NAND B) )

It occurs to me it probably can be simplified a bunch lol.

<<A::variables> nand <<A::variables> nand <B::variables>::operators>::operators> nand <<B::variables> nand <<A::variables> nand <B::variables> ::operators>::operators>::operators reporter

comp09 wrote:

Anything about logical right shifts? I'm currently stuck on those.

comp09 wrote:

<<A::variables> nand <<A::variables> nand <B::variables>::operators>::operators> nand <<B::variables> nand <<A::variables> nand <B::variables> ::operators>::operators>::operators reporter

gtoal wrote:

comp09 wrote:

Anything about logical right shifts? I'm currently stuck on those.

I haven't worked this out but I have a gut feeling the solution will involve the negative number represented by a single bit in the leftmost position (-maxint-1 ?) - if you shift that right by dividing, I think it can be used as a mask to remove the top bits that get pulled in when you right-shift a negative number by dividing by powers of two. Either adding or subtracting that mask ought to remove those bits. As long as overflow isn't detected etc.

--[[---------------
LuaBit v0.4
-------------------
a bitwise operation lib for lua.
http://luaforge.net/projects/bit/
How to use:
-------------------
 bit.bnot(n) -- bitwise not (~n)
 bit.band(m, n) -- bitwise and (m & n)
 bit.bor(m, n) -- bitwise or (m | n)
 bit.bxor(m, n) -- bitwise xor (m ^ n)
 bit.brshift(n, bits) -- right shift (n >> bits)
 bit.blshift(n, bits) -- left shift (n << bits)
 bit.blogic_rshift(n, bits) -- logic right shift(zero fill >>>)
 
Please note that bit.brshift and bit.blshift only support number within
32 bits.
2 utility functions are provided too:
 bit.tobits(n) -- convert n into a bit table(which is a 1/0 sequence)
               -- high bits first
 bit.tonumb(bit_tbl) -- convert a bit table into a number 
-------------------
Under the MIT license.
copyright(c) 2006~2007 hanzhao (abrash_han@hotmail.com)
--]]---------------
do
------------------------
-- bit lib implementions
local function check_int(n)
 -- checking not float
 if(n - math.floor(n) > 0) then
  error("trying to use bitwise operation on non-integer!")
 end
end
local function to_bits(n)
 check_int(n)
 if(n < 0) then
  -- negative
  return to_bits(bit.bnot(math.abs(n)) + 1)
 end
 -- to bits table
 local tbl = {}
 local cnt = 1
 while (n > 0) do
  local last = math.mod(n,2)
  if(last == 1) then
   tbl[cnt] = 1
  else
   tbl[cnt] = 0
  end
  n = (n-last)/2
  cnt = cnt + 1
 end
 return tbl
end
local function tbl_to_number(tbl)
 local n = table.getn(tbl)
 local rslt = 0
 local power = 1
 for i = 1, n do
  rslt = rslt + tbl[i]*power
  power = power*2
 end
 
 return rslt
end
local function expand(tbl_m, tbl_n)
 local big = {}
 local small = {}
 if(table.getn(tbl_m) > table.getn(tbl_n)) then
  big = tbl_m
  small = tbl_n
 else
  big = tbl_n
  small = tbl_m
 end
 -- expand small
 for i = table.getn(small) + 1, table.getn(big) do
  small[i] = 0
 end
end
local function bit_or(m, n)
 local tbl_m = to_bits(m)
 local tbl_n = to_bits(n)
 expand(tbl_m, tbl_n)
 local tbl = {}
 local rslt = math.max(table.getn(tbl_m), table.getn(tbl_n))
 for i = 1, rslt do
  if(tbl_m[i]== 0 and tbl_n[i] == 0) then
   tbl[i] = 0
  else
   tbl[i] = 1
  end
 end
 
 return tbl_to_number(tbl)
end
local function bit_and(m, n)
 local tbl_m = to_bits(m)
 local tbl_n = to_bits(n)
 expand(tbl_m, tbl_n) 
 local tbl = {}
 local rslt = math.max(table.getn(tbl_m), table.getn(tbl_n))
 for i = 1, rslt do
  if(tbl_m[i]== 0 or tbl_n[i] == 0) then
   tbl[i] = 0
  else
   tbl[i] = 1
  end
 end
 return tbl_to_number(tbl)
end
local function bit_not(n)
 
 local tbl = to_bits(n)
 local size = math.max(table.getn(tbl), 32)
 for i = 1, size do
  if(tbl[i] == 1) then 
   tbl[i] = 0
  else
   tbl[i] = 1
  end
 end
 return tbl_to_number(tbl)
end
local function bit_xor(m, n)
 local tbl_m = to_bits(m)
 local tbl_n = to_bits(n)
 expand(tbl_m, tbl_n) 
 local tbl = {}
 local rslt = math.max(table.getn(tbl_m), table.getn(tbl_n))
 for i = 1, rslt do
  if(tbl_m[i] ~= tbl_n[i]) then
   tbl[i] = 1
  else
   tbl[i] = 0
  end
 end
 
 --table.foreach(tbl, print)
 return tbl_to_number(tbl)
end
local function bit_rshift(n, bits)
 check_int(n)
 
 local high_bit = 0
 if(n < 0) then
  -- negative
  n = bit_not(math.abs(n)) + 1
  high_bit = 2147483648 -- 0x80000000
 end
 for i=1, bits do
  n = n/2
  n = bit_or(math.floor(n), high_bit)
 end
 return math.floor(n)
end
-- logic rightshift assures zero filling shift
local function bit_logic_rshift(n, bits)
 check_int(n)
 if(n < 0) then
  -- negative
  n = bit_not(math.abs(n)) + 1
 end
 for i=1, bits do
  n = n/2
 end
 return math.floor(n)
end
local function bit_lshift(n, bits)
 check_int(n)
 
 if(n < 0) then
  -- negative
  n = bit_not(math.abs(n)) + 1
 end
 for i=1, bits do
  n = n*2
 end
 return bit_and(n, 4294967295) -- 0xFFFFFFFF
end
local function bit_xor2(m, n)
 local rhs = bit_or(bit_not(m), bit_not(n))
 local lhs = bit_or(m, n)
 local rslt = bit_and(lhs, rhs)
 return rslt
end
--------------------
-- bit lib interface
bit = {
 -- bit operations
 bnot = bit_not,
 band = bit_and,
 bor  = bit_or,
 bxor = bit_xor,
 brshift = bit_rshift,
 blshift = bit_lshift,
 bxor2 = bit_xor2,
 blogic_rshift = bit_logic_rshift,
 -- utility func
 tobits = to_bits,
 tonumb = tbl_to_number,
}
end
--[[
for i = 1, 100 do
 for j = 1, 100 do
  if(bit.bxor(i, j) ~= bit.bxor2(i, j)) then
   error("bit.xor failed.")
  end
 end
end
--]]

comp09 wrote:

gtoal wrote:

comp09 wrote:

In your fast example, do the push and pop blocks just add/remove things to/from the stack list?

Yes. If you want to take it via the backpack, it's here: http://scratch.mit.edu/projects/29358020/
(the simpler one is http://scratch.mit.edu/projects/29513876/ )

As a side note, the backpack is currently broken.

This is what happens when I try to add stuff to it:


Someone please bug the Scratch team…

MrSherlockHolmes wrote:

comp09 wrote:

gtoal wrote:

comp09 wrote:

In your fast example, do the push and pop blocks just add/remove things to/from the stack list?

Yes. If you want to take it via the backpack, it's here: http://scratch.mit.edu/projects/29358020/
(the simpler one is http://scratch.mit.edu/projects/29513876/ )

As a side note, the backpack is currently broken.

This is what happens when I try to add stuff to it:
-snip-

Someone please bug the Scratch team…

Maybe you should try remixing it. I have the same problem.

define bin1 = DEC to 4-bit bin (x)
delete (all v) of [BIN1 v]
add (([floor v] of ((x) / (8))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (4))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (2))) mod (2)) to [BIN1 v]
add (([floor v] of (x)) mod (2)) to [BIN1 v]

define bin1 = DEC to 4-bit bin (x)
delete (all v) of [BIN1 v]
add (([floor v] of ((x) / (128))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (64))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (32))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (16))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (8))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (4))) mod (2)) to [BIN1 v]
add (([floor v] of ((x) / (2))) mod (2)) to [BIN1 v]
add (([floor v] of (x)) mod (2)) to [BIN1 v]