Bit String Flicking

Videos

 

About This Topic

    Bit strings (binary numbers) are frequently manipulated using logical operators, shifts, and circulates.  Mastering this topic is essential for systems programming, programming in assembly language and optimizing code. 

    A typical use of bit string is to maintain a set of flags.  Suppose that associated with a data structure in a program are 10 “options”, each of which can be either “on” or “off”.  One could maintain this information using an array of size 10, or one could use a single variable (if it is internally stored using at least 10 bits, which is usually the case) and use 10 bits to record each option.  In addition to saving space - a significant consideration if enough data structures and options are involved  - the program is often cleaner if a single variable is involved rather than an array.  Incidentally, bit strings are usually used to maintain Pascal “sets”.

    The logical operators which will be used are:  AND(&), OR(|), XOR(Å) and NOT(~).  These operators examine the operand(s) on a bit by bit basis.  For example, (10110 AND 01111) has a value of 00110.  The AND, OR and XOR are binary operators; the NOT is a unary operator.  The category description of Boolean Algebra/Digital Electronics has a complete description of each logical function.  The following chart summarizes this information:

 

p

q

p AND q

p OR q

p XOR q

NOT p

0

0

0

0

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

0

 

    Logical shifts (LSHIFT-x and RSHIFT-x) “ripple” the bit string x positions in the indicated direction.  Bits shifted out are lost; zeros are shifted in at the other end.  Circulates (RCIRC-x and LCIRC-x) “ripple” the bit string x positions in the specified direction.  As each bit is shifted out one end, it is shifted in at the other end.  Thus, for this category, the size of a bit string is fixed; it cannot be lengthened or shortened by any of the logical operators, shifts or circulates.  If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length.  The following table gives some examples of these operations:

 

p

LSHIFT-2 p

RSHIFT-2 p

LCIRC-3 p

RCIRC-3 p

01101

10100

00011

01011

10101

10

00

00

01

01

1110

1000

0011

0111

1101

1011011

1101100

0010110

1011101

0111011

 

The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR.  Operators with equal precedence are evaluated left to right; all operators bind from left to right.

 

References

    This topic is an art that is developed through experience.  Most of the references for Boolean Algebra and Assembly Language cover this topic in passing.

 

Sample Problems

 

 

Evaluate the following expression:

 

(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))

 

The expression evaluates as follows:

 

(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))

= (RSHIFT-1 (LCIRC-4 01011))

= (RSHIFT-1 10101)

= 01010

 

 

List all possible values of x (5 bits long) that solve the following equation.

 

(LSHIFT-1 (10110 XOR

  (RCIRC-3 x) AND 11011)) = 01100

 

Since x is a string 5 bits long, represent if by abcde.  (RCIRC-3 x) is cdeab which, when ANDed with 11011 gives cd0ab.  This is XORed to 10110 to yield Cd1Ab (the capital letter is the NOT of its lower case).

 

Now, if (LSHIFT-1 Cd1Ab) has a value of 01100, we must have: d=0, A=1 (hence a=0), b=0.  Thus, the solution must be in the form 00*0*, where * is an “I-don’t-care”.  The four possible values of x are: 00000, 00001, 00100 and 00101.

 

 

Evaluate the following expression:

 

((LCIRC-3 (10110 XOR 11010))

  AND (RSHIFT-1 10111))

 

 

(LC-3 (10110 XOR 11010) AND (RS-1 10111))

= (LCIRC-3 01100 AND 01011)

= (00011 AND 01011)

= 00011 

 

Evaluate the following expression:

 

((RCIRC-14 (LCIRC-23 01101)) |

  (LSHIFT-1 10011) & (RSHIFT-2 10111))

 

The rules of hierarchy must be followed carefully:

A = (RCIRC-14 (LCIRC-23 01101))

        = (LCIRC-9 01101)

        = (LCIRC-4 01101)

        = 10110

B = (LSHIFT-1 10011) = 00110

C = (RSHIFT-2 10111) = 00101

D = B & C = 00100

final answer = A | D = 10110

 

 

Find all possible values of x for which the following expression has a value of 10100.

 

(LSHIFT-2 (RCIRC-3 (NOT x)))

 

Let x=ABCDE and (NOT x)=abcde.  Substitute into the expression:

 

       (RCIRC-3 abcde) = cdeab

and

       (LSHIFT-2 cdeab) = eab00.

 

Since eab00 = 10100 the value of (NOT x) is 01**1 (where the * indicates an “I-don’t-care”), and the value of x is 10**0: 10000, 10010, 10100 and 10110.