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 `0`

s. But for all intermediate steps, include leading `0`

s.

`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 `0`

s 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 `0`

s 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 `0`

s 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 = đ 11011011we 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.