Bitweise Operationen - was zum Teufel ist los?

Question

Ich habe den folgenden JavaScript-Skript bekomme für ein 2D-Labyrinth zu erzeugen:

/* 
* 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("<svg width=\"" + (width * cell_width) + "\" height=\"" + (height*cell_width) + "\" version=\"1.1\" xmlns=\"http://www.w3.org/2000/svg\">\n" 
       + " <g stroke=\"black\" stroke-width=\"1\" stroke-linecap=\"round\">\n" + this.drawMaze() + " </g>\n</svg>\n"); 
    } 
    /* 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 " <line x1=\"" + x1 + "\" y1=\"" + y1 + "\" x2=\"" + x2 + "\" y2=\"" + y2 + "\" />\n"; 
    } 
} 

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

Ich mag würde das Skript erweitern, so dass es ein 3D-Labyrinth sechs Achsen erzeugt. Um dies zu tun, muss ich jedoch die bitweisen Operationen verstehen und wofür sie verwendet werden. Könnte mir bitte jemand erklären, warum der ursprüngliche Autor bitweise Operationen gewählt hat und was genau er im Skript macht?

Danke!

[Bearbeiten - Schlussfolgerung] Da das Problem nun gelöst ist, ist FYI hier die 3D-Version des Skripts:

/* 
* 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("<svg lenx=\"" + (lenx * cell_width) + "\" leny=\"" + (leny * lenz * cell_width) + "\" version=\"1.1\" xmlns=\"http://www.w3.org/2000/svg\">\n" 
       + " <g stroke=\"black\" stroke-lenx=\"1\" stroke-linecap=\"round\">\n" + this.drawMaze() + " </g>\n</svg>\n"); 
    } 
    /* 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 " <line x1=\"" + x1 + "\" y1=\"" + y1 + "\" x2=\"" + x2 + "\" y2=\"" + y2 + "\" />\n"; 
    } 
} 

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

Answer 1

Der häufigste Grund bitweise Operationen zu verwenden, weil sie für kompakte schnell und ermöglichen es sind Speicherung von Informationen in ganzen Zahlen.

Das heißt, dieses Skript scheint sie als Flags auf jedem Quadrat im Raster zu verwenden.

Werfen Sie einen Blick auf den folgenden Code:

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

Jede dieser Konstanten belegt ein Bit in einer ganzen Zahl. Um überprüfen Sie, wenn das Flag festgelegt ist, alles, was Sie tun müssen, ist festzustellen, ob seine Bitposition auf 1 festgelegt ist (in der Regel durch AND mit dieser Nummer und Vergleich mit 0). Um gesetzt ein Flag, Sie einfach diesen Bit-Wert (in der Regel durch ORing mit der Nummer). Dies tun die bitweisen Operatoren.