String and Boolean Data Types

The string data type. Strings are a type of data structure which is a sequence of symbols (letters, digits, punctuation marks, special characters, ...). The following function computes the reverse of a string and the function ispalindrome checks whether the reverse is the same as the original string.
function reverse(x)
  { var y = "";
    for (k in x) { y = x[k]+y; }
    return(y); }

function isapalindrome(x)
  { if (x == reverse(x))
      { return(1); }
      { return(0); } }
Palindromes are quite famous, as people like symmetries. In Germany, for example, the name "OTTO" is known for being a palindrome as well as for being the name of some emperors in the middle ages. In English, when the Panama Canal was build from 1881 until 1914, the sentence "A man, a plan, a canal - Panama" became famous, also due to being a palindrome. To see this, one would, however, have to remove spaces and punctuation marks and make all letters into the same case. The next program removes these spaces.

The following program is one of the ways to extract the letters from a string and to convert the upper case letters into lower case letters. The command to do this is called a "switch" or "case" command, the wording "switch(x[k])" tells the browser that it should find the matching case for the value of "x[k]" (which is the letter at position k) and then follow the instructions after the wording "case ..." until the wording "break" is found. So in the case that k is 5 and x[k] is "d", the commands between the case for the letter "d" and "break" are done where the case for "D" is ignored and then the lower case letter "d" is appended to the variable y. Here is the program.
function letters(x)
  { var y = ""; var k;
    for (k in x)
      { switch(x[k])
          { case "a": case "A": y = y+"a"; break;
            case "b": case "B": y = y+"b"; break;
            case "c": case "C": y = y+"c"; break;
            case "d": case "D": y = y+"d"; break;
            case "e": case "E": y = y+"e"; break;
            case "f": case "F": y = y+"f"; break;
            case "g": case "G": y = y+"g"; break;
            case "h": case "H": y = y+"h"; break;
            case "i": case "I": y = y+"i"; break;
            case "j": case "J": y = y+"j"; break;
            case "k": case "K": y = y+"k"; break;
            case "l": case "L": y = y+"l"; break;
            case "m": case "M": y = y+"m"; break;
            case "n": case "N": y = y+"n"; break;
            case "o": case "O": y = y+"o"; break;
            case "p": case "P": y = y+"p"; break;
            case "q": case "Q": y = y+"q"; break;
            case "r": case "R": y = y+"r"; break;
            case "s": case "S": y = y+"s"; break;
            case "t": case "T": y = y+"t"; break;
            case "u": case "U": y = y+"u"; break;
            case "v": case "V": y = y+"v"; break;
            case "w": case "W": y = y+"w"; break;
            case "x": case "X": y = y+"x"; break;
            case "y": case "Y": y = y+"y"; break;
            case "z": case "Z": y = y+"z"; break;
            default: break; } }
    return(y); }
All these programs can be tested with the following button.

The Boolean data type. The Boolean data types are named after George Boole who investigated this data type. Boolean data types are in the basic case just a variable which can be take either the value 0 or the value 1; in the more complicated case, it consists of several such digits which all can either take the value 0 or the value 1. One such digit is called "a bit", eight of them are called "a byte". Here a table of the basic operations "not", "and", "or" and "exclusive or".
xynot xx and yx or y x eor y
xy~x / !xx & y / x && y x | y / x || yx ^ y
01011100101001001101 1001
The second row describes how to do the operations on variables representing a series of bits or just on one bit; there are different commands for the two cases in Javascript. So if x represents 0101 and y represents 1100, then ~x, x | y, x & y and x ^ y are done bitwise and give the results in the last row.

One can express all functions from {0,1}n to {0,1} using and, or and not on the inputs. Here some examples.
  1. x eor y is the same as (x or y) and (not(x) or not(y)).
  2. maj(x,y,z) is 1 iff at least two of the inputs are one. So maj(x,y,z) = (x and y) or (x and z) or (y and z).
  3. the function which checks whether vwxy is a binary number being a multiple of 3 is the following: (not(v) and not(w) and not(x) and not(y)) or (not(v) and not(w) and x and y) or (not(v) and w and x and not(y)) or (v and not(w) and not(x) and y) or (v and w and not(x) and not(y)) or (v and w and x and y).
Internally, all the memory and the logic of the computer circuit is organised in Boolean logic. So numbers are stored in binary notation with 10 for two, 11 for three, 100 for four, 101 for five, 110 for six, 111 for seven, 1000 for eight, 1001 for nine, 1010 for ten and so on. The central processing unit of a computer calculates only with numbers up to a given size where leading zeroes are added in for having all numbers of the same length. Then addition of numbers and multiplication and other such operations are organised by Boolean functions which are hardwired into the central processing unit.

Sample Application of Boolean Operations. In most cases, Boolean functions are only auxiliary and used to implement the normal operations on numbers like addition, multiplication, subtraction and so on. However there are some few applications where the Boolean functions between (binary) numbers are directly utilised. One of these applications is the game Nim. In this game, two players alternately reduce one number in a list of numbers by at least one until all numbers are zero. The player who does the last move and reaches 0,0,...,0 wins. For example two players, Anke and Boris, play.
  1. Start Position: 1,128,150,182
  2. Anke moves to: 1,128,55,182
  3. Boris moves to: 1,32,55,55
  4. Anke moves to: 1,1,55,55
  5. Boris moves to: 1,1,1,55
  6. Anke moves to: 1,1,1,1
  7. Boris moves to: 0,1,1,1
  8. Anke moves to: 0,0,1,1
  9. Boris moves to: 0,0,0,1
  10. Anke wins by moving to: 0,0,0,0
It is difficult to see how to do the winning strategy of Anke with decimal numbers. However, if one converts the numbers into binary, one can see that whenever Anke has moved, the bitwise exclusive or of all numbers is 0, that is, x[1] ^ x[2] ^ x[3] ^ x[4] is 0. Boris has now no good move and will break this symmetry; however, when it is broken, Anke can find a move to restore it. When drawn at random, the starting position is unlikely to have the symmetry, therefore Anke can very likely move with the first move into a winning position. Here a computer program which computes the winning move.
function findmove(x)
  { var k; z = 0;
    var y = new Array();
    y = x.split(",");
    for (k in y)
      { z = z ^ y[k]; }
    if (z > 0)
      { for (k in y)
        { if ((z > 0) && ((z ^ y[k]) < y[k]))
          { y[k] = y[k] ^ z; z = -1 } } }
    if (z == -1)
      { return("Recommended move for "+x+" is "+y); }
      { return("No good move for "+x+"; anything is fine"); } } 
In this script, the program uses that the input x is a text consisting of a comma-separated list of inputs (as the user might give it). Thus the first two commands transform this list into an array of numbers. In the first for-loop the program checks whether there is a good move, that is, whether the game is not in a winning position for the opponent. This is done by computing the xor of all numbers in the array y. If a positive value is found then the program searches in the second for-loop which of the array elements can be reduced in order to obtain a symmetric situation where the xor is 0; note that here the new value must be smaller than the old one. Once this is found, the z is set to -1 in order to denote that the adjustment of y has been done. Afterwards the function returns the recommendation for the new move. If there is no winning move, the differences between possible moves is only psychological for the case that at certain moves the opponent has more difficulties to figure out its winning move; however, if the opponent has enough computational abilitiies, the player will eventually lose the game, whatever move it makes.