Bit-String Flicking

Bit-string flicking combines bitwise logic with shift/rotate operations. ACSL problems give you an expression with bit-strings and ask you to evaluate it, or give you an equation and ask you to find the unknown string. Once you memorize the operation rules, this is fast and systematic.

Bitwise operations

All bitwise operations work position by position (column by column).

NOT (~)

Flips every bit: 0 becomes 1, 1 becomes 0.

$\text{NOT }10110=01001$

AND (&)

Both must be 1 to get 1. Think of it as multiplication.

  10110
& 11010
-------
  10010

Quick rule: AND keeps only the bits that are 1 in both strings.

OR (|)

Either (or both) must be 1 to get 1.

  10110
| 11010
-------
  11110

Quick rule: OR turns on any bit that is 1 in either string.

XOR (^)

Bits must be different to get 1. Same bits give 0.

  10110
^ 11010
-------
  01100

Quick rule: XOR is like a “difference detector.” Same = 0, different = 1.

Useful XOR properties:

• $A\oplus 0=A$ (XOR with 0 does nothing)
• $A\oplus A=0$ (XOR with itself gives all zeros)
• $A\oplus \overline{A}=11\dots 1$

Shift operations

Shifts move bits left or right. Vacated positions are filled with 0. Bits that fall off the end are lost.

LSHIFT-n (left shift by n positions)

LSHIFT-2  10110

  Before:   1 0 1 1 0
            _dropped_/
  Shift:        1 1 0 _ _
  Fill 0s:      1 1 0 0 0

  Result: 11000

RSHIFT-n (right shift by n positions)

RSHIFT-2  10110

  Before:   1 0 1 1 0
                  _dropped_/
  Shift:    _ _ 1 0 1
  Fill 0s:  0 0 1 0 1

  Result: 00101

The rightmost bits ($10$) are lost - they fall off the end.

Circular shift (rotate) operations

Like shifts, but bits that fall off one end wrap around to the other end. No bits are lost.

LCIRC-n (left circular shift by n)

LCIRC-2  10110

  Take leftmost 2 bits: [10] 110
  Move them to the right end: 110 [10]
  Result: 11010

RCIRC-n (right circular shift by n)

RCIRC-2  10110

  Take rightmost 2 bits: 101 [10]
  Move them to the left end: [10] 101
  Result: 10101

Shortcut for large shifts: If the string has length $L$, then $\text{LCIRC-}n$ is the same as $\text{LCIRC-}(n\mathrm{mod}L)$. So $\text{LCIRC-}23$ on a 5-bit string is $\text{LCIRC-}3$ (since $23\mathrm{mod}5=3$). Same for RCIRC.

Also: $\text{LCIRC-}n=\text{RCIRC-}(L-n)$. So $\text{LCIRC-}3$ on 5 bits $=\text{RCIRC-}2$.

Order of operations

ACSL uses this precedence (highest first):

1. Parentheses (innermost first)
2. NOT, SHIFT, CIRC (unary/prefix operators)
3. AND
4. XOR
5. OR

Padding rule: When two strings in a binary operation have different lengths, pad the shorter string with leading zeros to match the longer one.

Example: Evaluate $10110\text{ AND }\text{NOT }11010\text{ OR }\text{LSHIFT-}3101010$

Step 1 - Apply NOT and LSHIFT first:

NOT 11010 = 00101
LSHIFT-3 101010 = 010000

Step 2 - AND (higher precedence than OR). The operands are $10110$ (5 bits) and $00101$ (5 bits), so no padding needed:

  10110
& 00101
-------
  00100

Step 3 - OR. The operands are $00100$ (5 bits) and $010000$ (6 bits). Pad the shorter one to 6 bits: $00100$ becomes $000100$.

  000100
| 010000
--------
  010100

Answer: 010100

Try it: trace a bit-string expression

Step through the evaluation of $\text{NOT }11001\text{ AND }10110\text{ OR }\text{LSHIFT-1 }00110$.

1Expression: NOT 11001 AND 10110 OR LSHIFT-1 001102Step 1: Apply NOT and LSHIFT (highest precedence)3  NOT 11001 = 001104  LSHIFT-1 00110 = 011005Step 2: Apply AND (next precedence)6  00110 AND 10110 = 001107Step 3: Apply OR (lowest precedence)8  00110 OR 01100 = 011109Result: 01110

Solving for unknown strings

ACSL sometimes gives an equation like $\text{LSHIFT-1 }(10110\text{ XOR }(\text{RCIRC-3 }x))=01100$ and asks you to find all values of $x$.

Strategy: work backwards from the result, undoing each operation from the outside in.

To undo a shift, think about what it does: a left shift pushes every bit one position to the left, fills the rightmost position with $0$, and discards the leftmost bit. So when you reverse it, you know every bit except the one that was lost.

Example: Undo $\text{LSHIFT-1 }Y=01100$ (where $Y$ is 5 bits).

The shift moved every bit of $Y$ one position left, filled the right end with $0$, and discarded the original leftmost bit. Reading the result $01100$:

• Bits 2 through 5 of $Y$ became the output $0110$, and the trailing $0$ was filled in by the shift.
• The original leftmost bit of $Y$ was lost.

So $Y=?0110$, where $?$ is $0$ or $1$. This gives two candidates: $00110$ and $10110$.

Step 2 - Continue working inward with each candidate, undoing the next operation (XOR, RCIRC, etc.) the same way. Each step may split into more possibilities or eliminate some.

This type of problem requires patience. Enumerate the possibilities systematically, and verify each final answer by plugging it back into the original expression.

Common mistakes

1. SHIFT vs CIRC confusion. Shifts fill with 0, circular shifts wrap bits around. Know which one you’re doing.
2. Forgetting that bits are lost in shifts. $\text{LSHIFT-}2$ on $10110$ gives $11000$, not $1011000$.
3. Wrong precedence. NOT and SHIFT bind tighter than AND. AND binds tighter than OR.
4. Large circular shifts. Always reduce with mod first: $\text{LCIRC-}14$ on 5 bits $=\text{LCIRC-}4$.

Contest strategy

• Evaluate expressions: ~45 seconds (apply operations in precedence order)
• Find unknowns: ~90 seconds (work backwards, enumerate possibilities)
• Double-check by plugging your answer back into the original expression