Bit-String Flicking

Bit strings (strings of binary digits) are frequently manipulated bit-by-bit using the logical operators not, and, or, and xor. Bits strings are manipulated as a unit using shift and circulate operators.

Most high-level languages (e.g., Python, Java, C++), support bit-string operations. Programmers typically use bit string to maintain a set of flags. Suppose that a program supports 8 options, each of which can be either “on” or “off”. One could maintain this information using an array of size 8, or one could use a single variable (if it is internally stored using at least 8 bits or 1 byte, which is usually the case) and use 8 bits to record each option. In addition to saving space, the program is often cleaner if a single variable is involved rather than an array. Bits strings are often used to maintain a set where values are either in the set or not.

Mastering this topic is essential for systems programming, programming in assembly language, optimizing code, and hardware design.

Bitwise Operators

The logical operators are not (~ or $\neg$), and (&), or (|), and xor ($\oplus$). These operators should be familiar to ACSL students from the Boolean Algebra and Digital Electronics categories.

• not is a unary operator that performs logical negation on each bit. Bits that are 0 become 1, and those that are 1 become 0. For example: ~101110 has a value of 010001.

• and is a binary operator that performs the logical and of each bit in each of its operands. For example, 1011011 and 011001 has a value of 001001. The and function is often use to isolate the value of a bit in a bit-string, or to clear the value of a bit.

• or is a binary operator that performs the logical or of each bit in each of its operands. For example, 1011011 or 011001 has a value of 111011. The and function is often use to force the value of a bit in a bit-string to be 1, if it isn't already.

• xor is a binary operator that performs the logical xor of each bit in each of its operands. For example, 1011011 xor 011001 has a value of 110010. The and function is often use to change the value of a particular bit.

If the arguments to and, or, or xor are not the same length, then 0s are added on the left (the most significant bit

• or is a binary operator that performs the logical For example. x and 00010 will extract from x the

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. In other words, all unary operators are performed on a single operator first. Operators with equal precedence are evaluated left to right; all operators bind from right to left.

Sample Problems

Sample Problem 1

Evaluate the following expression:

(0101110 AND NOT 110110 OR (LSHIFT-2 101010))

Solution: The expression evaluates as follows:

(0101110 AND 001001 OR (LSHIFT-2 101010))

(001000 OR (LSHIFT-3 101010))

(001000 OR 010000)

011000

Sample Problem 2

Evaluate the following expression:

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

Solution: The expression evaluates as follows, starting at the innermost parentheses:

(RCIRC-2 01101) => 01011

(LCIRC-4 01011) => 10101

(RSHIFT-1 10101) = 01010

Sample Problem 3

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

(LSHIFT-1 (10110 XOR (RCIRC-3 x) AND 11011)) = 01100

Solution: Since x is a string 5 bits long, represent it 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, (LSHIFT-1 Cd1Ab) = d1Ab0 which 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.

Sample Problem 4

Evaluate the following expression:

((RCIRC-14 (LCIRC-23 01101)) | (LSHIFT-1 10011) & (RSHIFT-2 10111))

Solution: The problem can be rewritten as

A | B & C

The AND has higher precedence than the OR.

The evaluation of expression A can be done in a straightforward way: LCIRC-23 011101) has a value of 01011, and RCIRC-14 01011) has a value of 10110. However, if the value of 23 and 14 were much larger, a more clever strategy is to offset the left and right circulates. For example, (RCIRC-7 (LCIRC-3 x)) would have the same results as (RCIRC-4 x). So, ((RCIRC-14 (LCIRC-23 01101)) has the same value as (LCIRC-9 01101), which has the same value as (LCIRC-4 01101). This is an easy expression to evaluate.

Expressions B and C are pretty easy to evaluate:

B = (LSHIFT-1 10011) = 00110

C = (RSHIFT-2 10111) = 00101

The expression becomes

A | B & C = 10110 | 00110 & 00101 = 10110 | 00100 = 10110

Videos

https://www.youtube.com/watch?v=XNBcO25mgCw

https://www.youtube.com/watch?v=IeMsD3harrE (Basic) https://www.youtube.com/watch?v=jbKw8oYJPs4 (Advanced)