ScratchData LogoScratchData
Back to gtoal's profile

optimised 32-bit bitwise AND (4x4-bit cache)

GTgtoal•Created October 11, 2014
optimised 32-bit bitwise AND (4x4-bit cache)
13
9
250 views
View on Scratch

Instructions

This AND uses divide-and-conquer to recursively keep splitting the bits in a word into smaller groups. If any of the groups is all zeroes, it returns quickly. Once the parameters are 4 bits or less, it will use a lookup table which it builds on the fly to reuse a previous result. (This is called 'memoization') A less optimised but much prettier implementation of both AND and OR can be seen at http://scratch.mit.edu/projects/29513876/

Description

Inspired by dcpu-16's code to implement efficient 8-bit bitwise operations. This doesn't improve on that for speed, but does handle 32-bit ints. Or change the mask from 65536 to 4294967296 to handle numbers larger than 32 bits. [Currently may be buggy if inputs are 4294967296 and 4294967295]

Project Details

Project ID29358020
CreatedOctober 11, 2014
Last ModifiedOctober 26, 2014
SharedOctober 13, 2014
Visibilityvisible
CommentsAllowed

Remix Information

Parent ProjectView Parent
Root ProjectView Root