Discuss Scratch

comp09
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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.



Visit the website of Andrew Sun!


Zro716
Scratcher
1000+ posts

Bitwise operations with arithmetic?

I know it converts them to binary but my bitwise calculator may be useful…

anyways, what you're looking to do is addition/multiplication in conjunction with the values of the bits. So let's take a look at the AND operator
  11100010
& 00101110
= 00100010
so in decimal, this appears as
  (128*1) + (64*1) + (32*1) + (16*0) + (8*0) + (4*0) + (2*1) + (1*0) [= 226]
& (128*0) + (64*0) + (32*1) + (16*0) + (8*1) + (4*1) + (2*1) + (1*0) [= 46]
= (128*0) + (64*0) + (32*1) + (16*0) + (8*0) + (4*0) + (2*1) + (1*0) [= 34]
to make this work, you would have to employ part of the conversion to binary in order to get the values for the AND comparison. some pseudocode to help with the process:
/*
1.  start with the result = 0 and byteVal = 1
2.  while both numbers > 0
  2a.  Check that the rightmost bit of each number is 1.
  2b.  If so, increase result by byteVal.
  2c.  Halve each number and round down.  This discards the
       rightmost bit and shifts all the other bits to the right.
  2d.  Double byteVal
3.  return result
*/
function AND(n1,n2) {
  var byteVal = 1;
  var result = 0;
  while (n1 > 0 || n2 > 0) {
    if (n1 % 2 == 1 && n2 % 2 == 1) { result+=byteVal; }
    n1 = Math.floor(n1 / 2);
    n2 = Math.floor(n2 / 2);
    byteVal *= 2;
  }
  return result;
}
// and here's code for OR, XOR, and NOT
function OR(n1,n2) {
  var byteVal = 1;
  var result = 0;
  while (n1 > 0 || n2 > 0) {
    if (n1 % 2 == 1 || n2 % 2 == 1) { result+=byteVal; }
    n1 = Math.floor(n1 / 2);
    n2 = Math.floor(n2 / 2);
    byteVal *= 2;
  }
  return result;
}
function XOR(n1,n2) {
  var byteVal = 1;
  var result = 0;
  while (n1 > 0 || n2 > 0) {
    if (n1 % 2 != n2 % 2) { result+=byteVal; }
    n1 = Math.floor(n1 / 2);
    n2 = Math.floor(n2 / 2);
    byteVal *= 2;
  }
  return result;
}
function NOT(n1) {
    var byteVal = 1;
    while (byteVal < n1) { byteVal *= 2; }
    return (byteVal - n1);
}

Last edited by Zro716 (March 10, 2015 07:13:45)

Zro716
Scratcher
1000+ posts

Bitwise operations with arithmetic?

here's my fiddling http://jsfiddle.net/r21pc9s2/


edit: in hindsight, dang I'm such a nerd.

Last edited by Zro716 (March 10, 2015 08:35:05)

MegaApuTurkUltra
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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

cute cute cute cute cute

rip in pizza ATs
gtoal
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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:

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))

fast:

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

Last edited by gtoal (March 10, 2015 18:54:19)

comp09
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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

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



Visit the website of Andrew Sun!


bobbybee
Scratcher
1000+ posts

Bitwise operations with arithmetic?

http://scratch.mit.edu/projects/43693078/

(see inside, there is a lot of valuable tricks in there even if you don't use the high level blocks)

Last edited by bobbybee (March 10, 2015 19:19:01)


“Ooo, can I call you Señorita Bee?” ~Chibi-Matoran
comp09
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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
From Wikipedia:
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.

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

Last edited by comp09 (March 10, 2015 19:20:28)




Visit the website of Andrew Sun!


gtoal
Scratcher
1000+ posts

Bitwise operations with arithmetic?

comp09 wrote:

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

Yes. (And Pop removes from stack and places in a variable called “pop”) 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/ )

Another solution is to keep a 256x256 precomputed 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))

Since Scratch doesn't have actual functions, the easier way to implement something like this is via a stack. As in the example above, or a bit better developed in http://scratch.mit.edu/projects/30342314/

eg Push(Y) Push(Y) NAND() Push(X) NAND() Push(X) Push(X) NAND() Push(Y) NAND() NAND() POP() -> Result.
G

Last edited by gtoal (March 10, 2015 21:43:52)

comp09
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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…



Visit the website of Andrew Sun!


bobbybee
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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

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.

“Ooo, can I call you Señorita Bee?” ~Chibi-Matoran
comp09
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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.
Here's a more simplified way: https://en.wikipedia.org/wiki/NAND_logic#XOR

( A NAND ( A NAND B ) ) NAND ( B NAND ( A NAND B ) )

Or in Scratch:
<<A::variables> nand <<A::variables> nand <B::variables>::operators>::operators> nand <<B::variables> nand <<A::variables> nand <B::variables> ::operators>::operators>::operators reporter

Last edited by comp09 (March 10, 2015 21:51:19)




Visit the website of Andrew Sun!


gtoal
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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.
gtoal
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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

Except Scratch doesn't support functions, so you would have to do all those subcalls into temporaries - or use a stack…
comp09
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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.
I found the answer in a Lua library named LuaBit. I'm just going to paste the whole thing here…
--[[---------------
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
--]]
EDIT Oh wait never mind I found it somewhere else

Last edited by comp09 (March 16, 2015 02:08:57)




Visit the website of Andrew Sun!


MrSherlockHolmes
Scratcher
500+ posts

Bitwise operations with arithmetic?

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…
Maybe you should try remixing it. I have the same problem.

Last edited by MrSherlockHolmes (March 16, 2015 17:47:38)


Centred signature.
comp09
Scratcher
1000+ posts

Bitwise operations with arithmetic?

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.
The Scratch team finally noticed it. It was an issue with HTTPS. Try using plain HTTP instead.



Visit the website of Andrew Sun!


robowiko123
Scratcher
19 posts

Bitwise operations with arithmetic?

I have a way to turn decimals into n-bit binary number (array of decimals).

Here's the implementation for 4 bits:

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]

This design is extendable.
Here's one for 8-bits:

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]

play sound [ Hello! v]
wait (2) s
say [A random signature.] for (-1) secs

Powered by DjangoBB

Standard | Mobile