If your children or students are enrolled for American Computer Science League (ACSL) Junior Division or higher divisions, Contest 2 include Bit-String Flicking. This blog post teaches you how to work on questions with bit-string flicking.
What is Bit-String Flicking?
Bit-string flicking is bitwise operation on bit strings. A bit string is a binary number and essentially maintains a set of flags. The digits allowed in a bit string are 0 and 1. Example for bit string are 1001 (a 4-bit string) and 10011110 (an 8-bit string).
The operations involve these:
- Logical operators such as NOT, OR, AND and XOR
- Shift operators LSHIFT and RSHIFT
- Circular shift (or rotations) operators LCIRC and RCIRC
Logical operators
The logical operators used are NOT, OR, AND and XOR. Let us look at each of them with examples.
NOT operator
The NOT operator is a unary operator which performs negation on each bit in a bit string. Negation is changing 0 to 1 and 1 to 0 for every bit in the bit string.
Examples:
NOT 1001 will evaluate to 0110.
NOT 101010101 will evaluate to 010101010. Remember to include the leading 0 until the very last step. If the final answer includes a leading 0, then you can skip the leading 0s. But for all intermediate steps, include leading 0s.
NOT(NOT 0101) will evaluate to NOT(1010), which will evaluate to 0101. We see that NOT (NOT expression) evaluates to expression.
As NOT is a unary operator, it is performed on only one operand, which is the bit string following the NOT operator.
OR operator
The OR operator is a binary operator and is performed between two operands. Each operand is a bit string. OR operation is applied between every matching corresponding bit based on position.
The way OR works is if at least one bit is 1, the result is 1.
On the whiteboard:
0 OR 0 = 0 0 OR 1 = 1 1 OR 0 = 1 1 OR 1 = 1
Examples
PROBLEM: What is 1001 OR 1010 ?
SOLUTION: 1001 OR 1010 evalutes to 1011.
| # 4 | #3 | #2 | #1 | |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | |
| OR | 1 | 0 | 1 | 0 |
| Answer = | 1 | 0 | 1 | 1 |
When we perform operation on corresponding bits from right to left:
Bits in #1 position: 1 OR 0 = 1
Bits in #2 position: 0 OR 1 = 1
Bits in #3 position: 0 OR 0 = 0
Bits in #4 position: 1 OR 1 = 1
1001
OR
1010
--------
1011
--------
PROBLEM: What is 101 OR 10011 ?
SOLUTION: 101 OR 10011 evaluates to 10111.
| #5 | # 4 | #3 | #2 | #1 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | |||
| OR | 1 | 0 | 0 | 1 | 1 |
| Answer = | 1 | 0 | 1 | 1 | 1 |
On the whiteboard:
101
OR
10011
-----------
10111
-----------
More information about the OR operator
If you want a quicker way to remember the OR operator, think of the OR operator as being analogous to a + operation.
It can also written as v, which comes from the Latin word vel, that stands for or.
AND operator
The AND operator is a binary operator and is performed between two operands. Each operand is a bit string. AND operation is applied between every matching corresponding bit based on position.
The way AND works is if both bits are 1, the result is 1, or else 0.
On the whiteboard:
0 AND 0 = 0 0 AND 1 = 0 1 AND 0 = 0 1 AND 1 = 1
Examples:
PROBLEM: What is 1001 AND 1010?
SOLUTION: 1001 AND 1010 evalutes to 1000.
| # 4 | #3 | #2 | #1 | |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | |
| AND | 1 | 0 | 1 | 0 |
| Answer = | 1 | 0 | 0 | 0 |
When we perform operation on corresponding bits from right to left:
Bits in #1 position: 1 AND 0 = 0
Bits in #2 position: 0 AND 1 = 0
Bits in #3 position: 0 AND 0 = 0
Bits in #4 position: 1 AND 1 = 1
On the whiteboard:
1001
AND
1010
--------
1000
--------
PROBLEM: What is 101 AND 10011 ?
SOLUTION: 101 AND 10011 evaluates to 100. Just for clarity, I padded the first operand with two extra 0s to match the number of bits in each.
| #5 | # 4 | #3 | #2 | #1 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | |
| AND | 1 | 0 | 0 | 1 | 1 |
| Answer = | 0 | 0 | 1 | 0 | 0 |
On the whiteboard:
00101
OR
10011
-----------
00100 = 100
-----------
XOR operator
The XOR operator is a binary operator and is performed between two operands. Each operand is a bit string. XOR operation is applied between every matching corresponding bit based on position.
XOR works similar to the OR operator, the only exception being if both bits are 1, the result is 0. In other words, if ONLY one bit is 1, the result is 1.
On the whiteboard:
0 OR 0 = 0 0 OR 1 = 1 1 OR 0 = 1 1 OR 1 = 1
Examples
PROBLEM: What is 1001 OR 1010 ?
SOLUTION: 1001 OR 1010 evalutes to 1011.
| # 4 | #3 | #2 | #1 | |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | |
| OR | 1 | 0 | 1 | 0 |
| Answer = | 1 | 0 | 1 | 1 |
When we perform operation on corresponding bits from right to left:
Bits in #1 position: 1 OR 0 = 1
Bits in #2 position: 0 OR 1 = 1
Bits in #3 position: 0 OR 0 = 0
Bits in #4 position: 1 OR 1 = 1
1001
OR
1010
--------
1011
--------
PROBLEM: What is 101 OR 10011 ?
SOLUTION: 101 OR 10011 evaluates to 10111.
| #5 | # 4 | #3 | #2 | #1 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | |||
| OR | 1 | 0 | 0 | 1 | 1 |
| Answer = | 1 | 0 | 1 | 1 | 1 |
On the whiteboard:
101
OR
10011
-----------
10111
-----------
More information about the XOR operator
If you want a quicker way to remember the OR operator, think of the OR operator as being analogous to a + operation.
It can also written as v, which comes from the Latin word vel, that stands for or.
Shift operators
There are two kinds of shift operators. They are LSHIFT for left shift and RSHIFT for right shift. Both these shift operators ripple the bit x positions to the left or right, depending on what kind of shift.
LSHIFT-x
LSHIFT-x stands for shift left by x bits.
The syntax of the LSHIFT operator is LSHIFT-x where x is the number of positions to shift left. An equal number of 0s is added to the other end (the right end), so the size of the bit string continues to be the same.
Examples:
PROBLEM: What is LSHIFT-2 11011011?
SOLUTION:
We lose 2 bits on the left of this bit string and add 2 bits to the right of the bit string.
For clarity, we will strike out the shifted bits and print them in red color, like this. We will also display the added bits in green color, like this.
LSHIFT-2 11011011
= 1101101100
= 01101100
= 1101100
PROBLEM: What is LSHIFT-1 1111?
SOLUTION: 1110
RSHIFT-x
RSHIFT-x stands for shift right by x bits.
The syntax of the RSHIFT operator is RSHIFT-x where x is the number of positions to shift right. An equal number of 0s is added to the other end (the left end), so the size of the bit string continues to be the same.
Examples:
PROBLEM: What is RSHIFT-2 11011011?
SOLUTION:
We lose 2 bits on the right of this bit string and add 2 bits to the left of the bit string.
For clarity, we will strike out the shifted bits and print them in red color, like this. We will also display the added bits in green color, like this.
RSHIFT-2 11011011
= 0011011011
= 110110
PROBLEM: What is RSHIFT-1 1111?
SOLUTION: 111
Circular shift operators
Similar to LSHIFT and RSHIFT, there are two operators called LCIRC and RCIRC that ripple the bit x positions to the left or right, but in a slightly different way. These two are circular shift operators. Instead of the bits being shifted and 0s added at the end, the bits are captured and appended to the other end. In this case too, the bit string remains the same size.
LCIRC-x
LCIRC-x stands for circulate left by x bits.
The syntax of the LCIRC operator is LCIRC-x where x is the number of bits on the left to grab and shift to the right. Since no bit is being lost, the size of the bit string continues to be the same.
Examples:
PROBLEM: What is LCIRC-2 11011011?
SOLUTION:
We grab 2 bits on the left of this bit string and move them to the right of the bit string.
For clarity, we will highlight the circulated bits with a box, like this.
LCIRC-2 11011011
= đ 11011011 we will move these two from the left side...
= 01101111 đ ... to the right side
= 1101111
PROBLEM: What is LCIRC-4 11100001 ?
SOLUTION: 00011110
RCIRC-x
RCIRC-x stands for circulate right by x bits.
The syntax of the RCIRC operator is RCIRC-x where x is the number of bits on the right to grab and shift to the left. Since no bit is being lost, the size of the bit string continues to be the same.
Examples:
PROBLEM: What is RCIRC-2 11011011?
SOLUTION:
We grab 2 bits on the right of this bit string and move them to the left of the bit string.
For clarity, we will highlight the circulated bits with a box, like this.
RCIRC-2 11011011 = 11011011 đ we will move these two from the right side... = đ 11110110 ... to the left side = 11110110
PROBLEM: What is RCIRC-4 11100001 ?
SOLUTION: 00011110
Order of operations
Bitwise operations have an order of precendence, similar to regular numbers. The questions will most likely include more than two operands. The order of operations for bitwise operations is:
- Parenthesis ()
- NOT
- LSHIFT, RSHIFT, LCIRC, RCIRC
- AND
- XOR
- OR
Parenthesis takes the highest precedence, while OR takes the lowest precedence.
Evaluate these bitwise expressions
Problem 1
LSHIFT-1 1100 AND RSHIFT-2 1001
Solution
We first evaluate LSHIFT-1 1100, then RSHIFT-2 1001 and then we perform AND operation on the result.
LSHIFT-1 1100 AND RSHIFT-2 1001 = 1000 AND 10 = 0
Problem 2
RSHIFT-1 1100 AND LCIRC-2 1001
Solution
We first evaluate RSHIFT-1 1100, then LCIRC-2 1001 and then we perform AND operation on the result.
RSHIFT-1 1100 AND LCIRC-2 1001 = 110 AND 0110 = 110
Problem 3
RSHIFT-1 1100 AND NOT(LCIRC-2 1001)
Solution
We first evaluate LCIRC-2 1001, then NOT( ) over it, then RSHIFT-1 1100, and then we perform AND operation on the previous result.
RSHIFT-1 1100 AND NOT(LCIRC-2 1001) = RSHIFT-1 1100 AND NOT(0110) = RSHIFT-1 1100 AND 1001 = 110 AND 1001 = 0
Problem 4
NOT(RCIRC-1 1100) AND NOT(LCIRC-2 1011)
Solution
Using the order of operations above, we first evaluate the parenthesis sub-expressions, and then the NOT, and finally the AND.
NOT(RCIRC-1 1100) AND NOT(LCIRC-2 1011) = NOT(0110) AND NOT(0111) = 1001 AND 1000 = 1000
Problem 5
NOT(111011) XOR 11110000 AND 1010101
Solution
Using the order of operations above, we first evaluate the NOT, then the AND and finally the XOR.
NOT(111011) XOR 11110000 AND 1010101 = 000100 XOR 11110000 AND 1010101 = 000100 XOR 1010000 = 10110000
Conclusion
If there is anything you would like me to add to this article, feel free to contact me. Thanks.
Related Posts
If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.
