Unit 5 — Bit-String Flicking

Slide 1 of 58

The problem: The Stage Light Board

The school play has a row of eight stage lamps, and a light board that controls them. A lit lamp is a 1 and a dark lamp is a 0, so the whole row is one string of eight bits. Right now the board shows:

10110010

The light board has only a few buttons, and the director's cue sheet uses their names:

Button	What it does to the row of lamps
`NOT`	every lamp flips: lit goes dark, dark goes lit
`AND 11110000`	a stencil: only lamps that are lit and under a 1 of the stencil stay lit
`LSHIFT-2`	every light slides 2 places left; the 2 on the far left fall off the end, and 2 dark lamps come in on the right
`RCIRC-3`	every light spins 3 places right; the 3 that fall off the right end come back in on the left

Puzzle 1. Cue 7 says: (RCIRC-3 10110010) AND 11110000. Which lamps are lit after cue 7?

Puzzle 2. During the dress rehearsal the board showed some pattern. Then someone pressed LSHIFT-2, and now the board shows 11001000. What was the pattern before? Be careful: there may be more than one answer, and the director wants all of them.

These buttons are the operators of bit-string flicking, an ACSL Contest 2 category. Lesson 1 answers Puzzle 1 by hand, Lesson 2 teaches every operator and the order they go in, and Lesson 3 solves Puzzle 2 and teaches the computer to solve puzzles like it.
- Apply NOT, AND, OR and XOR bit by bit, padding a shorter string with 0s on the left.
- Shift and circulate bit strings, and evaluate whole expressions in ACSL's order of operations.
- Solve for an unknown bit string x, one operator at a time and, at Intermediate and above, through chains of operators.
- Write the bit-string operations in Python.
Lesson 1 — Bit strings, NOT, AND, OR and XOR

Division: Junior and above.

A bit is a 0 or a 1, and a bit string is a row of bits, such as 10110010. Its length is how many bits it has: 10110010 has length 8. In a bit-string problem, 0101 and 101 are not the same answer: always write every bit, including zeros on the left.

Computers use bit strings everywhere: a row of switches, the pixels of a black-and-white picture, or a set of yes/no settings. Changing them one bit at a time is called bit-string flicking.
NOT

NOT flips every bit. ACSL also writes it as ~.

NOT 10110010 = 01001101
AND, OR and XOR

These three take two bit strings and combine them bit by bit, column by column, like adding two numbers but with no carries.

a b a AND b a OR b a XOR b

0 0 0 0 0

0 1 0 1 1

1 0 0 1 1

1 1 1 1 0
- AND gives 1 only where both bits are 1. ACSL also writes it as &.
- OR gives 1 where at least one bit is 1. ACSL also writes it as |.
- XOR ("exclusive or") gives 1 where the bits are different. ACSL also writes it as ⊕.
Example 1. Line the strings up in columns and do one column at a time.

a	b	a `AND` b	a `OR` b	a `XOR` b
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

     10110101           10110101           10110101
 AND 01101100        OR 01101100       XOR 01101100
     --------           --------           --------
     00100100           11111101           11011001

Example 2. 11001 ⊕ 11001 = 00000: a string XOR itself is all zeros, because every column has two equal bits. And 11001 ⊕ 00000 = 11001: XOR with zeros changes nothing.

Strings of different lengths

If the two strings have different lengths, ACSL pads the shorter one with 0s on the left until they match. The answer has the length of the longer string.

Example 3. 101 AND 11010

The short string 101 becomes 00101:
```
     00101
 AND 11010
     -----
     00000
```
The answer is 00000, five bits. Padding on the left does not change the value of a binary number, just as 007 is still 7.
Stencils: what AND, OR and XOR are used for

The second string in these puzzles is often a mask, a stencil that picks out some bits.
- AND with a mask keeps the bits under the mask's 1s and clears the rest: 10110010 AND 11110000 = 10110000 keeps the left four lamps.
- OR with a mask turns on the bits under the mask's 1s: 10110010 OR 00001111 = 10111111.
- XOR with a mask flips the bits under the mask's 1s: 10110010 XOR 00001111 = 10111101.
Watch out: in OR, two 1s give 1, but in XOR, two 1s give 0.
Bit strings in Python

In Python, a bit string can be kept as text, such as "10110". Then each operator is a loop over the characters. Here is NOT: build a new string, one flipped bit at a time.

def bit_not(bits):
    result = ""
    for bit in bits:
        if bit == "0":
            result = result + "1"
        else:
            result = result + "0"
    return result


print(bit_not("10110010"))
print(bit_not("0000"))

Output

01001101
1111

For the two-string operators, first pad the shorter string with "0"s on the front, then walk both strings with one index i. The three operators differ only in the test that decides whether the new bit is a 1.

def pad_left(bits, width):
    while len(bits) < width:
        bits = "0" + bits
    return bits


def combine(a, op, b):
    width = max(len(a), len(b))
    a = pad_left(a, width)
    b = pad_left(b, width)
    result = ""
    for i in range(width):
        if op == "AND":
            one = a[i] == "1" and b[i] == "1"
        elif op == "OR":
            one = a[i] == "1" or b[i] == "1"
        else:
            one = a[i] != b[i]
        if one:
            result = result + "1"
        else:
            result = result + "0"
    return result


print(combine("10110101", "AND", "01101100"))
print(combine("10110101", "OR", "01101100"))
print(combine("10110101", "XOR", "01101100"))
print(combine("101", "AND", "11010"))

Output

The four lines match Examples 1 and 3. XOR needs no if of its own: "the bits are different" is exactly a[i] != b[i].

Put it together: this program reads one line, A OP B, where OP is AND, OR or XOR, and prints the answer at full width. It is saved as assets/l1.py.

Try it

def pad_left(bits, width):
    while len(bits) < width:
        bits = "0" + bits
    return bits


def combine(a, op, b):
    width = max(len(a), len(b))
    a = pad_left(a, width)
    b = pad_left(b, width)
    result = ""
    for i in range(width):
        if op == "AND":
            one = a[i] == "1" and b[i] == "1"
        elif op == "OR":
            one = a[i] == "1" or b[i] == "1"
        else:
            one = a[i] != b[i]
        if one:
            result = result + "1"
        else:
            result = result + "0"
    return result


parts = input().split()
print(combine(parts[0], parts[1], parts[2]))

Run it from this unit's folder:
```
python assets/l1.py < assets/l1/1.in
```
The input 1101 OR 1010011 prints 1011111: the short string was padded to 0001101 first. Use it to check your hand work in Lesson 1, but do every problem by hand first: the short-answer test has no computer.
Lesson 2 — Shifts, circulates and whole expressions

Division: Junior and above.
Shifts: bits fall off

LSHIFT-x moves every bit x places to the left. The x bits on the far left fall off and are lost, and x zeros come in on the right. RSHIFT-x does the same to the right: the x bits on the far right are lost, and x zeros come in on the left. The length never changes.

Example 1.
```
LSHIFT-2 10110010  =  110010 00  =  11001000
RSHIFT-3 10110010  =  000 10110  =  00010110
```
For LSHIFT-2, cross out the first 2 bits and add 2 zeros at the end. For RSHIFT-3, cross out the last 3 bits and add 3 zeros at the front. If you shift by the whole length or more, every bit falls off and the answer is all zeros.
Circulates: bits wrap around

LCIRC-x ("left circulate") also moves every bit x places left, but the bits that fall off the left end come back in on the right, in the same order. Nothing is lost: think of the bits written around a circle and turning. RCIRC-x turns the other way: the bits that fall off the right end come back on the left.

Example 2.
```
LCIRC-3 10110010  =  10010 + 101  =  10010101
RCIRC-3 10110010  =  010 + 10110  =  01010110
```
For LCIRC-3, move the first 3 bits to the end. For RCIRC-3, move the last 3 bits to the front.

Big circulate counts. Circulating a string of length n by n places turns it all the way round, back to where it started. So only the remainder after dividing by the length matters.

Example 3. LCIRC-11 1011001: the length is 7, and 11 % 7 = 4, so this is LCIRC-4 1011001 = 001 + 1011 = 0011011.
Another handy fact: on a string of length n, RCIRC-x is the same as LCIRC-(n − x). RCIRC-3 on 8 bits is LCIRC-5.

That answers Puzzle 1: RCIRC-3 10110010 = 01010110, and 01010110 AND 11110000 = 01010000. After cue 7, lamps 2 and 4 (counting from the left) are lit.
Shifts and circulates in Python

Python can cut a piece out of a string with a slice: bits[k:] is everything from index k to the end, and bits[:k] is the first k characters. Each shift or circulate is two slices joined together. The helper zeros(k) builds a string of k zeros with a loop.

def zeros(k):
    text = ""
    for i in range(k):
        text = text + "0"
    return text


def lshift(bits, k):
    if k > len(bits):
        k = len(bits)
    return bits[k:] + zeros(k)


def rshift(bits, k):
    if k > len(bits):
        k = len(bits)
    return zeros(k) + bits[:len(bits) - k]


def lcirc(bits, k):
    k = k % len(bits)
    return bits[k:] + bits[:k]


def rcirc(bits, k):
    k = k % len(bits)
    return bits[len(bits) - k:] + bits[:len(bits) - k]


print(lshift("10110010", 2))
print(rshift("10110010", 3))
print(lcirc("10110010", 3))
print(rcirc("10110010", 3))
print(lcirc("1011001", 11))

Output

The output matches Examples 1 to 3. k % len(bits) handles big circulate counts, and in lshift and rshift a count bigger than the length is cut down to the length, so the answer is all zeros.

Put it together: this program reads a bit string and a count k, and prints all four moves. It is saved as assets/l2.py.

Try it

def zeros(k):
    text = ""
    for i in range(k):
        text = text + "0"
    return text


def lshift(bits, k):
    if k > len(bits):
        k = len(bits)
    return bits[k:] + zeros(k)


def rshift(bits, k):
    if k > len(bits):
        k = len(bits)
    return zeros(k) + bits[:len(bits) - k]


def lcirc(bits, k):
    k = k % len(bits)
    return bits[k:] + bits[:k]


def rcirc(bits, k):
    k = k % len(bits)
    return bits[len(bits) - k:] + bits[:len(bits) - k]


parts = input().split()
bits = parts[0]
k = int(parts[1])
print("LSHIFT-" + str(k) + " " + lshift(bits, k))
print("RSHIFT-" + str(k) + " " + rshift(bits, k))
print("LCIRC-" + str(k) + " " + lcirc(bits, k))
print("RCIRC-" + str(k) + " " + rcirc(bits, k))

Run it from this unit's folder:
```
python assets/l2.py < assets/l2/3.in
```
The input 10110010 3 is the hook's light board; the last line, RCIRC-3 01010110, is the first step of Puzzle 1. assets/l2/2.in holds 1011001 11, which checks big counts.
Order of operations

An ACSL expression can use many operators at once, like NOT 10110 AND 01110 OR 10001. Just as × comes before + in arithmetic, bit-string operators have an order, from first to last:

Order Operators

1 (first) NOT (~)

2 LSHIFT, RSHIFT, LCIRC, RCIRC

3 AND (&)

4 XOR (⊕)

5 (last) OR

The symbols in brackets are other ways to write the same operators, and OR is also written |. Parentheses come before everything, as in arithmetic. Two more rules settle ties:
- Two-string operators of the same level go from left to right. A AND B AND C means (A AND B) AND C.
- One-string operators go from right to left. In NOT RSHIFT-1 1100, the operator nearest the string goes first: it means NOT (RSHIFT-1 1100) = NOT 0110 = 1001.
A way to remember the order: operators that touch only one string (NOT, shifts, circulates) always go before operators that join two; among those, AND, then XOR, then OR.

Example 4. NOT 10110 AND 01110 OR 10001
1. NOT first: NOT 10110 = 01001. The expression is now 01001 AND 01110 OR 10001.
1. AND next: 01001 AND 01110 = 01000. Now it is 01000 OR 10001.
2. OR last: 01000 OR 10001 = 11001.
Example 5. LSHIFT-1 10011 XOR 11100 AND 01010
1. The shift: LSHIFT-1 10011 = 00110.
2. AND before XOR: 11100 AND 01010 = 01000.
3. Then XOR: 00110 XOR 01000 = 01110.
Going left to right and doing the XOR first would give 00110 XOR 11100 = 11010, then AND 01010 = 01010, which is wrong.

Example 6. RCIRC-2 LSHIFT-1 NOT 110100 (one-string operators, right to left)
1. NOT 110100 = 001011.
2. LSHIFT-1 001011 = 010110.
3. RCIRC-2 010110 = 100101.
Example 7. (RSHIFT-1 (LCIRC-2 10011)) OR 01000, with parentheses from the inside out.
1. LCIRC-2 10011 = 01110.
2. RSHIFT-1 01110 = 00111.
3. 00111 OR 01000 = 01111.
Tip: on paper, write each step on its own line, and rewrite the whole expression with the part you just worked out replaced by its answer.
Lesson 3 — Solving for x

Division: Junior and above.

Some ACSL questions give you the answer and ask for the bit string x that produced it, as in Puzzle 2. There may be no answer, one answer, or many.
The letters method
1. Write x as letters, one per bit: for 5 bits, x = abcde.
2. Work the expression out with the letters, exactly as with bits.
3. Line the result up with the given answer and read off what each letter must be.
4. A letter that never meets the answer is free: it can be 0 or 1.
Example 1 (Puzzle 2). Find all 8-bit x with LSHIFT-2 x = 11001000.
Let x = abcdefgh. Then LSHIFT-2 x = cdefgh00. Line it up with 11001000: c = 1, d = 1, e = 0, f = 0, g = 1, h = 0, and the last two 0s match the zeros that came in. The letters a and b fell off the end, so they are free. That gives four patterns, **110010, where each * can be 0 or 1:

00110010, 01110010, 10110010, 11110010
The board could have shown any of these four before the rehearsal; the director needs all of them.

How ACSL wants the answer.
- A list of solutions is written in increasing order, as binary numbers, separated by a comma and a space, every string at full length.
- If the question asks how many solutions there are, write just the number. With k free bits there are 2 × 2 × … × 2 = 2^k solutions: 4 for Puzzle 2.
- Only if the question asks for it, write all the solutions as one pattern with * for each free bit, as in **110010.
No solution at all. Find all 4-bit x with LSHIFT-1 x = 0111. With x = abcd, LSHIFT-1 x = bcd0, but the answer ends in 1, and the last bit of a left shift is always 0. There is no solution.
One operator at a time

For the Junior division, the unknown meets just one operator. Each operator gives its own kind of answer.
- NOT, circulates and XOR lose nothing, so they can be undone, and there is exactly one answer. NOT is undone by NOT, LCIRC-k by RCIRC-k, and x XOR m by XOR with m again. Example 2. x XOR 1100 = 1010 gives x = 1010 XOR 1100 = 0110. Check: 0110 XOR 1100 = 1010.
- Shifts lose bits, and the lost bits are free (Example 1).
- AND with a mask: where the mask has a 1, x's bit must equal the answer's bit. Where the mask has a 0, the answer's bit must be 0 (otherwise there is no solution), and x's bit is free. Example 3. x AND 1100 = 0100 with x = abcd: a = 0, b = 1, and c, d are free: 0100, 0101, 0110, 0111, or the pattern 01**.
- OR with a mask: where the mask has a 0, x's bit must equal the answer's bit. Where the mask has a 1, the answer's bit must be 1 (otherwise no solution), and x's bit is free.
Chains of operators

Division: Intermediate and above.

Intermediate and Senior questions put two or more operators on x. The letters method still works: push the letters through one operator at a time.

Example 4. Find all 5-bit x with RSHIFT-1 LCIRC-3 x = 01010.
Let x = abcde. One-string operators go right to left, so the circulate is first: LCIRC-3 abcde = deabc. Then RSHIFT-1 deabc = 0deab. Line it up with 01010: the 0 on the left matches, and d = 1, e = 0, a = 1, b = 0. Only c is free, so the solutions are 10010, 10110.

Example 5. Find all 4-bit x with (LSHIFT-1 x) OR x = 1110.
Let x = abcd, so LSHIFT-1 x = bcd0. Column by column: b OR a = 1, c OR b = 1, d OR c = 1, and 0 OR d = 0. From the last column, d = 0. Then d OR c = 1 gives c = 1, which makes c OR b = 1 true whatever b is. Finally b OR a = 1: (a, b) is 01, 10 or 11. The solutions are 0110, 1010, 1110.
Example 6. Find all 4-bit x with (RSHIFT-1 x) XOR x = 0110.

Let x = abcd, so RSHIFT-1 x = 0abc. Column by column: 0 XOR a = 0, a XOR b = 1, b XOR c = 1, c XOR d = 0. So a = 0, then b = 1, then c = 0, then d = 0: x = 0100. Work from the column you know for sure, and each column tells you the next letter.
Checking every x by computer

The letters method is what you use on the short-answer test. A program has a simpler plan: there are only 2^n bit strings of length n, so try them all (complete search), and keep the ones that give the answer.
To list every n-bit string, count x from 0 to 2^n − 1 and write each number in binary at full width. to_bits does it by repeated division by 2 (as in Unit 1): each remainder value % 2 is the next bit from the right, and value // 2 drops that bit. It runs exactly width times, so small numbers get their zeros on the left.

Order	Operators
1 (first)	`NOT` (`~`)
2	`LSHIFT`, `RSHIFT`, `LCIRC`, `RCIRC`
3	`AND` (`&`)
4	`XOR` (`⊕`)
5 (last)	`OR`

def to_bits(value, width):
    text = ""
    for i in range(width):
        text = str(value % 2) + text
        value = value // 2
    return text


for x in range(2 ** 3):
    print(to_bits(x, 3))

Output

The strings come out in increasing order, which is exactly the order ACSL wants.

The fast way: Python's bitwise operators

Python has the bit-string operators built in, working on the binary form of whole numbers:

ACSL Python Note

a AND b a & b

a XOR b a ^ b ^ is XOR in Python, not a power

LSHIFT-k a (a << k) & mask << never loses bits, so cut back to n bits

RSHIFT-k a a >> k

NOT a a ^ mask

And a OR b is written a | b in Python. Here mask is the n-bit string of all 1s, which is the number 2^n − 1: for 5 bits, 11111 = 31.

Two operators need the mask because a Python number has no fixed length:
- a << k puts k zeros on the right and keeps every bit, so & mask throws away the bits that should fall off the left.
- Python's own ~a gives a negative number, so this book writes NOT as a ^ mask: XOR with all 1s flips every bit (Lesson 1's stencils).
To turn a bit string into a number, give int a second value, the base: int("10011", 2) reads the text as a base-2 number, 19 (you met this in Unit 1). To turn the answer back into text, use to_bits.

ACSL	Python	Note
`a AND b`	`a & b`
`a XOR b`	`a ^ b`	`^` is XOR in Python, not a power
`LSHIFT-k a`	`(a << k) & mask`	`<<` never loses bits, so cut back to n bits
`RSHIFT-k a`	`a >> k`
`NOT a`	`a ^ mask`

def to_bits(value, width):
    text = ""
    for i in range(width):
        text = str(value % 2) + text
        value = value // 2
    return text


width = 5
mask = 2 ** width - 1
a = int("10011", 2)
b = int("01010", 2)
print(to_bits(a & b, width))
print(to_bits(a | b, width))
print(to_bits(a ^ b, width))
print(to_bits(a ^ mask, width))
print(to_bits((a << 1) & mask, width))
print(to_bits(a >> 1, width))

Output

Check each line by hand: 10011 AND 01010 = 00010, and so on down to RSHIFT-1 10011 = 01001. Leave out & mask in the << line and the answer has 6 bits, not 5.

A circulate is two shifts joined with |: the bits that fall off one end are shifted in from the other. For n bits and 0 < k < n, LCIRC-k a is ((a << k) | (a >> (n - k))) & mask.

def to_bits(value, width):
    text = ""
    for i in range(width):
        text = str(value % 2) + text
        value = value // 2
    return text


width = 8
mask = 2 ** width - 1
a = int("10110010", 2)
k = 3
print(to_bits(((a << k) | (a >> (width - k))) & mask, width))

Output

10010101

It prints 10010101, the same as LCIRC-3 10110010 in Lesson 2. In Python, & | ^ << >> follow almost the same order as ACSL, but + and - come before << and >>, so a << n - k means a << (n - k). Always use parentheses in bit expressions: they cost nothing and prevent surprises.
Put it together: this program solves (RSHIFT-1 x) XOR x = T by complete search. It reads the answer T, tries every x of the same length, and prints each solution on its own line, in increasing order, or NONE. It is saved as assets/l3.py.

Try it

def to_bits(value, width):
    text = ""
    for i in range(width):
        text = str(value % 2) + text
        value = value // 2
    return text


target_text = input()
width = len(target_text)
target = int(target_text, 2)
mask = 2 ** width - 1
found = 0
for x in range(2 ** width):
    if ((x >> 1) ^ x) & mask == target:
        print(to_bits(x, width))
        found = found + 1
if found == 0:
    print("NONE")

Run it from this unit's folder:
```
python assets/l3.py < assets/l3/2.in
```
The input 1011 prints 1101. Try the other inputs in assets/l3: every answer T has exactly one solution, which the column-by-column reasoning of Example 6 explains. (Changing one bit to the XOR of it and its left neighbour, as this expression does, turns a binary number into a Gray code, used in dials that must never misread two bits at once.)
- With a mask, AND keeps bits, OR turns them on, and XOR flips them.
- A shift loses bits off one end and brings in 0s; a circulate wraps them round to the other end.
- The order is NOT, then shifts and circulates, then AND, then XOR, then OR; equal operators go left to right.
- To solve for x, write its bits as letters, work the expression out, and read off each letter; a free letter can be 0 or 1.
- A program can check every possible x, which is a good way to test your hand answer.
You can now evaluate a bit-string expression and find every x that fits.

Unit 5 — Bit-String Flicking

The problem: The Stage Light Board

Lesson 1 — Bit strings, NOT, AND, OR and XOR

NOT

AND, OR and XOR

Strings of different lengths

Stencils: what AND, OR and XOR are used for

Bit strings in Python

Lesson 2 — Shifts, circulates and whole expressions

Shifts: bits fall off

Circulates: bits wrap around

Shifts and circulates in Python

Order of operations

Lesson 3 — Solving for x

The letters method

One operator at a time

Chains of operators

Checking every x by computer

The fast way: Python's bitwise operators