## 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:
```/*
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]))enddefine 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]))enddefine (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    endend`

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
-------------------
--]]---------------
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
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) ssay [A random signature.] for (-1) secs`