Bitwise operations - what the heck is going on?

Question

I've got the following JavaScript script for generating a 2D maze:

/*
 * 3 June 2003, [[:en:User:Cyp]]:
 *     Maze, generated by my algorithm
 * 24 October 2006, [[:en:User:quin]]:
 *     Source edited for clarity
 * 25 January 2009, [[:en:User:DebateG]]:
 *     Source edited again for clarity and reusability
 * 1 June 2009, [[:en:User:Nandhp]]:
 *     Source edited to produce SVG file when run from the command-line
 * 7 January, 2011 [[:en:User:SharkD]]:
 *     Source converted to JavaScript
 *
 * This program was originally written by [[:en:User:Cyp]], who
 * attached it to the image description page for an image generated by
 * it on en.wikipedia. The image was licensed under CC-BY-SA-3.0/GFDL.
 */

/* Recreate a math function that exists in Java but not JavaScript. */
Math.nextInt = function (number) {
    return Math.floor(Math.random() * number)
}

/* Recreate a system function that exists in Java but not JavaScript.
 * Uncomment either WScript.Echo() or alert() depending on whether you are
 * running the script from the Windows command-line or a Web page.
 */
function println(string)
{
    // if inside Windows Scripting Host
    WScript.Echo(string)
    // if inside a Web page
//  alert(string)
}

/* Define the bit masks */
var Constants =
{
    WALL_ABOVE : 1,
    WALL_BELOW : 2,
    WALL_LEFT : 4,
    WALL_RIGHT : 8,
    QUEUED : 16,
    IN_MAZE : 32
}

/* Construct a Maze with specified width, height, and cell_width */
function Maze(width, height, cell_width) {
    if (width)
        this.width = width;
    else
        this.width = 20;
    if (height)
        this.height = height;
    else
        this.height = 20;
    if (cell_width)
        this.cell_width = cell_width;
    else
        this.cell_width = 10;
    this.maze = []

    /* The maze generation algorithm. */
    this.createMaze = function()  {
        var width = this.width
        var height = this.height
        var maze = this.maze
        var x, y, n, d;
        var dx = [ 0, 0, -1, 1 ];
        var dy = [ -1, 1, 0, 0 ];

        var todo = new Array(height * width);
        var todonum = 0;

        /* We want to create a maze on a grid. */
        /* We start with a grid full of walls. */
        for (x = 0; x < width; ++x) {
            maze[x] = []
            for (y = 0; y < height; ++y) {
                if (x == 0 || x == width - 1 || y == 0 || y == height - 1) {
                    maze[x][y] = Constants.IN_MAZE;
                }
                else {
                    maze[x][y] = 63;
                }
            }
        }

        /* Select any square of the grid, to start with. */
        x = 1 + Math.nextInt(width - 2);
        y = 1 + Math.nextInt(height - 2);

        /* Mark this square as connected to the maze. */
        maze[x][y] &= ~48;

        /* Remember the surrounding squares, as we will */
        for (d = 0; d < 4; ++d) {
            if ((maze[x + dx[d]][y + dy[d]] & Constants.QUEUED) != 0) {
                /* want to connect them to the maze. */              
                todo[todonum++] = ((x + dx[d]) << Constants.QUEUED) | (y + dy[d]);
                maze[x + dx[d]][y + dy[d]] &= ~Constants.QUEUED;
            }
        }

        /* We won't be finished until all is connected. */
        while (todonum > 0) {
            /* We select one of the squares next to the maze. */
            n = Math.nextInt(todonum);
            x = todo[n] >> 16; /* the top 2 bytes of the data */
            y = todo[n] & 65535; /* the bottom 2 bytes of the data */

            /* We will connect it, so remove it from the queue. */
            todo[n] = todo[--todonum];

            /* Select a direction, which leads to the maze. */
            do {
                d = Math.nextInt(4);
            }
            while ((maze[x + dx[d]][y + dy[d]] & Constants.IN_MAZE) != 0);

            /* Connect this square to the maze. */
            maze[x][y] &= ~((1 << d) | Constants.IN_MAZE);
            maze[x + dx[d]][y + dy[d]] &= ~(1 << (d ^ 1));

            /* Remember the surrounding squares, which aren't */
            for (d = 0; d < 4; ++d) {
                if ((maze[x + dx[d]][y + dy[d]] & Constants.QUEUED) != 0) {      
                    /* connected to the maze, and aren't yet queued to be. */
                    todo[todonum++] = ((x + dx[d]) << Constants.QUEUED) | (y + dy[d]);
                    maze[x + dx[d]][y + dy[d]] &= ~Constants.QUEUED;
                }
            }
            /* Repeat until finished. */
        }

        /* Add an entrance and exit. */
        maze[1][1] &= ~Constants.WALL_ABOVE; 
        maze[width - 2][height - 2] &= ~Constants.WALL_BELOW;
    }
    /* Called to write the maze to an SVG file. */
    this.printSVG = function () {
        println("
");
    }
    /* Main maze-drawing loop. */
    this.drawMaze = function () {
        var x, y;
        var width = this.width;
        var height = this.height;
        var cell_width = this.cell_width
        var outstring = ""
        for (x = 1; x < width - 1; ++x) {
            for (y = 1; y < height - 1; ++y) {
                if ((this.maze[x][y] & Constants.WALL_ABOVE) != 0)
                    outstring += this.drawLine(x * cell_width, y * cell_width, (x + 1) * cell_width, y * cell_width);
                if ((this.maze[x][y] & Constants.WALL_BELOW) != 0)
                    outstring += this.drawLine(x * cell_width, (y + 1) * cell_width, (x + 1) * cell_width, (y + 1) * cell_width);
                if ((this.maze[x][y] & Constants.WALL_LEFT) != 0)
                    outstring += this.drawLine(x * cell_width, y * cell_width, x * cell_width, (y + 1) * cell_width);
                if ((this.maze[x][y] & Constants.WALL_RIGHT) != 0)
                    outstring += this.drawLine((x + 1) * cell_width, y * cell_width, (x + 1) * cell_width, (y + 1) * cell_width);
            }
        }
        return outstring
    }
    /* Draw a line, either in the SVG file or on the screen. */
    this.drawLine = function (x1, y1, x2, y2) {
        return "    
";
    }
}

/* Initialization method that will be called when the program is
* run from the command-line. Maze will be written as SVG file. */
function main(args) {
    var m = new Maze();
    m.createMaze();
    m.printSVG();
}

/* execute the program */
main()

I would like to extend the script such that it creates a six axis 3D maze. However, in order to do so I have to understand the bitwise operations and what they are being used for. Could someone please explain to me why the original author chose to use bitwise operations, and what it is exactly they are doing in the script?

Thanks!

[edit - conclusion] Since the problem is now solved, FYI here's the 3D version of the script:

/*
 * 3 June 2003, [[:en:User:Cyp]]:
 *     Maze, generated by my algorithm
 * 24 October 2006, [[:en:User:quin]]:
 *     Source edited for clarity
 * 25 January 2009, [[:en:User:DebateG]]:
 *     Source edited again for clarity and reusability
 * 1 June 2009, [[:en:User:Nandhp]]:
 *     Source edited to produce SVG file when run from the command-line
 * 7 January, 2011 [[:en:User:SharkD]]:
 *     Source converted to JavaScript and third axis added
 *
 * This program was originally written by [[:en:User:Cyp]], who
 * attached it to the image description page for an image generated by
 * it on en.wikipedia. The image was licensed under CC-BY-SA-3.0/GFDL.
 */

/* Recreate a math function that exists in Java but not JavaScript. */
Math.nextInt = function (number) {
    return Math.floor(Math.random() * number)
}

/* Recreate a system function that exists in Java but not JavaScript.
 * Uncomment either WScript.Echo() or alert() depending on whether you are
 * running the script from the Windows command-line or a Web page.
 */
function println(string)
{
    // if inside Windows Scripting Host
    WScript.Echo(string)
    // if inside a Web page
//  alert(string)
}

/* Define the bit masks */
var WALL_ABOVE = 1;
var WALL_BELOW = 2;
var WALL_LEFT = 4;
var WALL_RIGHT = 8;
var WALL_FRONT = 16;
var WALL_BACK = 32;
var QUEUED = 64;
var IN_MAZE = 128;

/* Construct a Maze with specified lenx, leny, and cell_width */
function Maze(lenx, leny, lenz, cell_width) {
    if (lenx)
        this.lenx = lenx;
    else
        this.lenx = 20;
    if (leny)
        this.leny = leny;
    else
        this.leny = 20;
    if (lenz)
        this.lenz = lenz;
    else
        this.lenz = 8;
    if (cell_width)
        this.cell_width = cell_width;
    else
        this.cell_width = 10;
    this.maze = []

    /* The maze generation algorithm. */
    this.createMaze = function()  {
        var lenx = this.lenx
        var leny = this.leny
        var lenz = this.lenz
        var maze = this.maze
        var x, y, z, n, d;
        var dx = [ 0, 0, -1, 1, 0, 0 ];
        var dy = [ -1, 1, 0, 0, 0, 0 ];
        var dz = [ 0, 0, 0, 0, -1, 1 ];

        var todo = new Array(leny * lenx * lenz);
        var todonum = 0;

        /* We want to create a maze on a grid. */
        /* We start with a grid full of walls. */
        /* Except for the outer walls which are left open? */
        for (x = 0; x < lenx; ++x) {
            maze[x] = []
            for (y = 0; y < leny; ++y) {
                maze[x][y] = []
                for (z = 0; z < lenz; ++z)
                {
                    if (x == 0 || x == lenx - 1 || y == 0 || y == leny - 1 || z == 0 || z == lenz - 1) {
                        maze[x][y][z] = IN_MAZE;
                    }
                    else {
                        maze[x][y][z] = WALL_ABOVE + WALL_BELOW + WALL_LEFT + WALL_RIGHT + WALL_FRONT + WALL_BACK + QUEUED + IN_MAZE;           // DUNNO!!!! 255
                    }
                }
            }
        }

        /* Select random square of the grid, to start with. */
        x = 1 + Math.nextInt(lenx - 2);
        y = 1 + Math.nextInt(leny - 2);
        z = 1 + Math.nextInt(lenz - 2);

        /* Mark this square as connected to the maze. */
        maze[x][y][z] &= ~(QUEUED + IN_MAZE);

        /* Remember the surrounding squares, as we will... */
        for (d = 0; d < 6; ++d) {
            if ((maze[x + dx[d]][y + dy[d]][z + dz[d]] & QUEUED) != 0) {
                /* ...want to connect them to the maze. */              
                todo[todonum++] = [x + dx[d], y + dy[d], z + dz[d]];
                maze[x + dx[d]][y + dy[d]][z + dz[d]] &= ~QUEUED;
            }
        }

        /* We won't be finished until all is connected. */
        while (todonum > 0) {
            /* We select one of the squares next to the maze. */
            n = Math.nextInt(todonum);
            x = todo[n][0];
            y = todo[n][1];
            z = todo[n][2];

            /* We will connect it, so remove it from the queue. */
            todo[n] = todo[--todonum];

            /* Select a random direction, which leads to the maze. */
            do {
                d = Math.nextInt(6);
            }
            while ((maze[x + dx[d]][y + dy[d]][z + dz[d]] & IN_MAZE) != 0);

            /* Connect this square to the maze. */
            maze[x][y][z] &= ~((1 << d) | IN_MAZE);
            maze[x + dx[d]][y + dy[d]][z + dz[d]] &= ~(1 << (d ^ 1));

            /* Remember the surrounding squares, which aren't... */
            for (d = 0; d < 6; ++d) {
                if ((maze[x + dx[d]][y + dy[d]][z + dz[d]] & QUEUED) != 0) {
                    /* ...connected to the maze, and aren't yet queued to be. */
                    todo[todonum++] = [x + dx[d], y + dy[d], z + dz[d]];
                    maze[x + dx[d]][y + dy[d]][z + dz[d]] &= ~QUEUED;
                }
            }
            /* Repeat until finished. */
        }

        /* Add an entrance and exit. */
        maze[1][1][1] &= ~WALL_ABOVE;
        maze[lenx - 2][leny - 2][lenz - 2] &= ~WALL_BELOW;
    }
    /* Called to write the maze to an SVG file. */
    this.printSVG = function () {
        println("
");
    }
    /* Main maze-drawing loop. */
    this.drawMaze = function () {
        var x, y, z;
        var lenx = this.lenx;
        var leny = this.leny;
        var lenz = this.lenz;
        var cell_width = this.cell_width
        var outstring = ""
        for (x = 1; x < lenx - 1; ++x) {
            for (y = 1; y < leny - 1; ++y) {
                for (z = 1; z < lenz - 1; ++z) {
                    var z_pos = z * leny * cell_width;
                    if ((this.maze[x][y][z] & WALL_ABOVE) != 0)
                        outstring += this.drawLine
                        (
                            x * cell_width,
                            y * cell_width + z_pos,
                            (x + 1) * cell_width,
                            y * cell_width + z_pos
                        );
                    if ((this.maze[x][y][z] & WALL_BELOW) != 0)
                        outstring += this.drawLine
                        (
                            x * cell_width,
                            (y + 1) * cell_width + z_pos,
                            (x + 1) * cell_width,
                            (y + 1) * cell_width + z_pos
                        );
                    if ((this.maze[x][y][z] & WALL_LEFT) != 0)
                        outstring += this.drawLine
                        (
                            x * cell_width,
                            y * cell_width + z_pos,
                            x * cell_width,
                            (y + 1) * cell_width + z_pos
                        );
                    if ((this.maze[x][y][z] & WALL_RIGHT) != 0)
                        outstring += this.drawLine
                        (
                            (x + 1) * cell_width,
                            y * cell_width + z_pos,
                            (x + 1) * cell_width,
                            (y + 1) * cell_width + z_pos
                        );
                    if ((this.maze[x][y][z] & WALL_FRONT) != 0)
                        outstring += this.drawLine
                        (
                            x * cell_width + cell_width/3,
                            (y + 1) * cell_width - cell_width/3 + z_pos,
                            (x + 1) * cell_width - cell_width/3,
                            y * cell_width + cell_width/3 + z_pos
                        );
                    if ((this.maze[x][y][z] & WALL_BACK) != 0)
                        outstring += this.drawLine
                        (
                            x * cell_width + cell_width/3,
                            y * cell_width + cell_width/3 + z_pos,
                            (x + 1) * cell_width - cell_width/3,
                            (y + 1) * cell_width - cell_width/3 + z_pos
                        );
                }
            }
        }
        return outstring
    }
    /* Draw a line, either in the SVG file or on the screen. */
    this.drawLine = function (x1, y1, x2, y2) {
        return "    
";
    }
}

/* Initialization method that will be called when the program is
* run from the command-line. Maze will be written as SVG file. */
function main(args) {
    var m = new Maze();
    m.createMaze();
    m.printSVG();
}

/* execute the program */
main()

Fragsworth · Accepted Answer

The most common reason to use bitwise operations is because they are fast and allow for compact storage of information in integers.

That said, this script appears to be using them as flags on each square in the grid.

Take a look at the following code:

/* Define the bit masks */
var Constants =
{
    WALL_ABOVE : 1,
    WALL_BELOW : 2,
    WALL_LEFT : 4,
    WALL_RIGHT : 8,
    QUEUED : 16,
    IN_MAZE : 32
}

Each of these constants occupies one bit in an integer. To check if the flag is set, all you need to do is determine if its bit location is set to 1 (typically by ANDing with that number and comparing to 0). To set a flag, you simply set that bit value (typically by ORing with the number). This is what the bitwise operators are doing.

Bitwise operations - what the heck is going on?

Answers (1)

Related Questions