Bit-String Flicking
Bitwise operators, shifts, and circulates on strings of binary digits.
Overview
Bit string flicking involves manipulating strings of binary digits (0s and 1s) using various operators. This concept is fundamental in systems programming, assembly language, code optimization, and hardware design.
Importance in Modern Programming
- Most high-level languages like Python, Java, C++, etc. use bit-string operations.
- Bit strings use less memory than other data structures (ex. arrays) for certain operations.
- Shift operations can compute multiplication/division by powers of 2
- Bit string flicking can be used to manipulate binary data in databases, files, and other storage systems.
Key Concepts
Bitwise Operators (Changes a single bit)
NOT (~)
Flips the value of a bit (0→1, 1→0)
| x | NOT x |
|---|---|
| 0 | 1 |
| 1 | 0 |
Example: ~100 = 011
AND (&)
Both input bits must be 1 for output to be 1
| x | y | x AND y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Example: 110 & 011 = 010
OR (|)
Output is 1 if either input bit is 1
| x | y | x OR y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Example: 110 | 011 = 111
XOR (⊕)
Output is 1 if input bits are different values
| x | y | x XOR y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Example: 110 ⊕ 011 = 101
Shift Operators (Changes a bit string)
- LSHIFT-n: Shifts left n places, adds zeros on right
- RSHIFT-n: Shifts right n places, adds zeros on left
- LCIRC-n: Circular left shift (bits that fall off the left end reappear on the right)
- RCIRC-n: Circular right shift (bits that fall off the right end reappear on the left)
Order of Precedence
- NOT (~)
- SHIFT and CIRC operations
- AND (&)
- XOR (⊕)
- OR (|)
* Equal precedence operators are evaluated left to right
Examples
Shift and Circulate Examples
LSHIFT
Example: LSHIFT-2 01101
- Original:
01101 - Shift left 2 spaces:
101__ - Fill with zeros:
10100
Result: 10100
RSHIFT
Example: RSHIFT-3 01101
- Original:
01101 - Shift right 3 spaces:
___01 - Fill with zeros:
00001
Result: 00001
LCIRC
Example: LCIRC-3 01101
- Original:
01101 - Take first 3 bits:
011|01 - Move to end:
01|011
Result: 01011
RCIRC
Example: RCIRC-1 01101
- Original:
01101 - Take last bit:
0110|1 - Move to front:
1|0110
Result: 10110
Combining Operators
NOT 10110 AND LCIRC-2 01101 OR 00011Follow the order of precedence: NOT first, then shifts, then AND, then OR.
- NOT 10110 =
01001 - LCIRC-2 01101 =
10101(move the first two bits, 01, to the end) - AND the two results:
01001 AND 10101 = 00001 - OR with 00011:
00001 OR 00011 = 00011
Result: 00011
Practice Problems
Problem 1 Junior
Evaluate the following expression:
(10111 XOR NOT 10100 AND 11101)
Note: Keep in mind the order of operations
Solution
The order of operations in this problem is as follows:
- NOT
- AND
- XOR
Now, let's evaluate the expression step by step:
- First, evaluate NOT 10100:
NOT 10100 = 01011 - Then, AND with 11101:
01011 AND 11101 = 01001 - Finally, XOR with 10111:
10111 XOR 01001 = 11110
Therefore, (10111 XOR NOT 10100 AND 11101) = 11110
Problem 2 Intermediate
Simplify the following expression:
(LCIRC-2 (NOT 10111) OR (RSHIFT-2 (LCIRC-1 10010 AND NOT 00010)))
Solution
- First, evaluate NOT 10111:
NOT 10111 = 01000 - Next, evaluate NOT 00010:
NOT 00010 = 11101 - Evaluate LCIRC-1 10010:
LCIRC-1 10010 = 00101 - Apply AND operation:
00101 AND 11101 = 00101 - Apply RSHIFT-2:
RSHIFT-2 00101 = 00001 - Apply LCIRC-2 to first part:
LCIRC-2 01000 = 00001 - Finally, apply OR:
00001 OR 00001 = 00001
Therefore, the final result is 00001
Problem 3 Intermediate
Evaluate the following:
D2316 XOR 9F216
Both numbers are 12-bit hexadecimal values. Express your answer as a 3-digit hexadecimal string.
Tip: To convert hexadecimal to binary, you can convert each hex digit to a 4-digit binary number and then combine them.
Solution
- Convert D2316 to binary:
D2316 = 1101001000112 - Convert 9F216 to binary:
9F216 = 1001111100102 - Perform XOR operation:
110100100011100111110010010011010001 - Convert result back to hexadecimal:
0100110100012 = 4D116
Therefore, D2316 XOR 9F216 = 4D116
Problem 4 Senior
Solve for X (5-bits) in the following equation:
01101 XOR (RCIRC-2 X) = 01111
Solution
- Given equation:
01101 XOR (RCIRC-2 X) = 01111 - For any XOR operation to equal 1, at exactly one operand must be 1:
01101 (first operand)01111 (result)To put a 1 in the result, the answer bit must be opposite of the first operand; to put a 0 in the result, the answer bit must be the same as the first operand.
- Required bits in RCIRC-2 X:
00010 - Working backwards through RCIRC-2:
- Original:
????? - After RCIRC-2:
00010 - Therefore X must be:
01000
- Original:
- Verify:
- RCIRC-2 01000 = 00010
- 01101 XOR 00010 = 01111, which matches the given result
Therefore, X = 01000
Problem 5 Senior
Evaluate the following expression:
(NOT 10101 OR LCIRC-2 01100 OR LCIRC-1 00111 AND RSHIFT-2 10010)
Solution
- NOT 10101:
01010 - LCIRC-2 01100:
10001 - RSHIFT-2 10010:
00100 - LCIRC-1 00111:
01110 - 01110 AND 00100:
01110 AND 00100 = 00100 - Combining with OR operations:
01010 (NOT result)10001 (LCIRC-2 result)00100 (AND result)11111 (final OR result)
Therefore, the final result is 11111