## Discuss Scratch

- Discussion Forums
- » Advanced Topics
- » Bitwise operations with arithmetic?

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

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.

- 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

so in decimal, this appears as

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:

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

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

/* 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?

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

- MegaApuTurkUltra
- Scratcher

1000+ posts

### Bitwise operations with arithmetic?

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?

I'm trying to port a JavaScript library to Scratch, and it looks like a mess to me!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.

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?

I'm trying to port a JavaScript library to Scratch, and it looks like a mess to me!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.

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?

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

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

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

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

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

- gtoal
- Scratcher

1000+ posts

### Bitwise operations with arithmetic?

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?

As a side note, the backpack is currently broken.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/ )

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

Someone please bug the Scratch team…

- bobbybee
- Scratcher

1000+ posts

### Bitwise operations with arithmetic?

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?

Here's a more simplified way: I got:https://en.wikipedia.org/wiki/NAND_logic#XOR

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

- gtoal
- Scratcher

1000+ posts

### Bitwise operations with arithmetic?

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?

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

I found the answer in a Lua library named LuaBit. I'm just going to paste the whole thing here…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 --]]

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

- MrSherlockHolmes
- Scratcher

500+ posts

### Bitwise operations with arithmetic?

Maybe you should try remixing it. I have the same problem.As a side note, the backpack is currently broken.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/ )

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

Someone please bug the Scratch team…

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

Centred signature.

- comp09
- Scratcher

1000+ posts

### Bitwise operations with arithmetic?

The Scratch team finally noticed it. It was an issue with HTTPS. Try using plain HTTP instead.Maybe you should try remixing it. I have the same problem.As a side note, the backpack is currently broken.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/ )

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

-snip-

Someone please bug the Scratch team…

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

This design is extendable.

Here's one for 8-bits:

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

- Discussion Forums
- » Advanced Topics
- » Bitwise operations with arithmetic?