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 (LSHIFTx and RSHIFTx) “ripple” the bit string x positions in the indicated direction. Bits shifted out are lost; zeros are shifted in at the other end. Circulates (RCIRCx and LCIRCx) “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 
LSHIFT2 p 
RSHIFT2 p 
LCIRC3 p 
RCIRC3 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:
(RSHIFT1 (LCIRC4 (RCIRC2 01101))) 
The expression evaluates as follows:
(RSHIFT1 (LCIRC4 (RCIRC2 01101))) = (RSHIFT1 (LCIRC4 01011)) = (RSHIFT1 10101) = 01010

List all possible values of x (5 bits long) that solve the following equation.
(LSHIFT1 (10110 XOR (RCIRC3 x) AND 11011)) = 01100 
Since x is a string 5 bits long, represent if by abcde. (RCIRC3 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 (LSHIFT1 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 “Idon’tcare”. The four possible values of x are: 00000, 00001, 00100 and 00101.

Evaluate the following expression:
((LCIRC3 (10110 XOR 11010)) AND (RSHIFT1 10111))

(LC3 (10110 XOR 11010) AND (RS1 10111)) = (LCIRC3 01100 AND 01011) = (00011 AND 01011) = 00011 
Evaluate the following expression:
((RCIRC14 (LCIRC23 01101))  (LSHIFT1 10011) & (RSHIFT2 10111)) 
The rules of hierarchy must be followed carefully: A = (RCIRC14 (LCIRC23 01101)) = (LCIRC9 01101) = (LCIRC4 01101) = 10110 B = (LSHIFT1 10011) = 00110 C = (RSHIFT2 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.
(LSHIFT2 (RCIRC3 (NOT x))) 
Let x=ABCDE and (NOT x)=abcde. Substitute into the expression:
(RCIRC3 abcde) = cdeab and (LSHIFT2 cdeab) = eab00.
Since eab00 = 10100 the value of (NOT x) is 01**1 (where the * indicates an “Idon’tcare”), and the value of x is 10**0: 10000, 10010, 10100 and 10110.
