A Row of Switches You Can Move Together

Alice has a cardboard stencil above a row of lamps. Each hole lets her touch one lamp. She wants to change a pattern without touching covered lamps. Instead of keeping a separate object for each lamp, she draws one row of marks.

One position, one answer

A bit is a value with two states, zero and one. Here zero means off, and one means on. A bitset stores a fixed number of these answers. In C++, std::bitset<N> lives in the <bitset> header.

Think of positions as labelled boxes rather than digits in a large number. Position 5 can represent lamp 5, seat 5, or total weight 5. The meaning belongs to your program. The stored bit answers one question about that position.

A mask is a pattern used to select or change positions. Alice's holes form a mask. A one permits a press there. Zeroes forbid those presses. Another mask can describe which lamps need changing.

A bitset is useful when many questions share this shape. Each answer is independent, but whole groups can move or combine together. You still choose the meaning of every position. The library only applies the same bit rule across them.

A width fixed before input

The N in bitset<N> is part of its type. It must be a compile-time constant, known before the program runs. bitset<8> and bitset<16> are different types. Reading an integer does not create a new type.

A fixed capacity can still handle a smaller input. Declare bitset<128>, use its low n positions, and keep the other positions zero. This works when the problem guarantees n never exceeds 128. It does not make the actual width change.

When the required capacity comes only from input, consider vector<bool>. It offers a runtime length and packed flags. It does not offer bitset's whole-row shift operators. Lesson 04 compares these choices before you commit to one.

Also check the memory budget before choosing a large constant. Fixed width means the whole capacity exists, including positions currently holding zero. An empty-looking pattern still has that capacity. So a known maximum is a design choice, not free space.

Index from the right

Bit indexes start at zero. Bit 0 appears at the right end of the string representation. Bit N-1 appears at the left. The written order matches ordinary binary numbers.

This matters when your story uses a row read from left to right. Either map its leftmost cell to the highest bit, or reverse the mapping deliberately. Write that rule in the statement. Never let the picture and the input silently disagree.

to_string() keeps the full width, including leading zeroes. A string constructor reads binary characters, not a decimal number disguised as text. Use quoted strings when you want to describe the visible pattern directly.

If a shorter input uses a larger capacity, the constructor puts its bits at the low end. Unused high positions remain zero. Print only the intended n characters when the task asks for n positions. Capacity and display width are separate decisions.

Three ways to combine a row

AND, written &, keeps a position only when both inputs hold one. Use it for overlap or permission checks. It works position by position. There is no carrying between neighbours.

OR, written |, keeps a position when either input holds one. It collects possible positions. Repeating the same one does not increase a counter. A bit still stores only yes or no.

XOR, written ^, keeps a position when the inputs differ. It describes changes between snapshots. Applying the same toggle mask twice restores the original pattern. Complement, written ~, flips every position within the fixed width.

These bitwise operators work on individual bits. They differ from logical operators such as &&, which combine whole truth values. If you want one truth value about a resulting mask, call any() or none() afterward.

Shift positions, keep the width

A left shift moves each one toward a higher index. A right shift moves toward a lower index. New positions receive zeroes. Bits leaving the fixed width disappear.

A shift is not a rotation. A rotation brings departing bits back at the other end. A shift does not remember them. This difference matters for a circular ring or a repeating timetable.

With b << k, the result is a shifted copy. With b <<= k, b itself changes. Use the copy form when several queries start from the same original pattern. Otherwise one query may accidentally depend on earlier queries.

Bitset shifts by N or more produce an all-zero pattern. Integer shifts have different rules about their count. Do not carry one rule across both types. Lesson 02 gives each operation its own small example.

std::bitset<8> lamps("00101100");
bool lit = lamps.test(2);
lamps.set(0);
auto overlap = lamps & std::bitset<8>("00001111");

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<8> lamps("00101100");
    cout << "capacity " << lamps.size() << '\n';
    cout << "lit " << lamps.count() << '\n';
    cout << "position 2 " << lamps.test(2) << '\n';
}

capacity 8
lit 3
position 2 1

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<8> current("00110100"), target("00100101");
    bitset<8> holes("00011111");
    auto change = current ^ target;
    cout << "changes " << change << '\n';
    cout << "forbidden " << (change & ~holes).any() << '\n';
}

changes 00010001
forbidden 0

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<8> marks("00010110");
    for (int d = 0; d <= 3; ++d) {
        cout << "slide " << d << ' ' << (marks << d) << '\n';
    }
    cout << "original " << marks << '\n';
}

slide 0 00010110
slide 1 00101100
slide 2 01011000
slide 3 10110000
original 00010110

Use one step at a time. The subset phase lists choices, including choosing nothing. Without JavaScript, the same steps appear as a table.

These are logical capacities, not measured object sizes. Alignment and library storage can add padding.

#include <bitset>
#include <iostream>
int main() {
    int n; std::cin >> n;
    std::bitset<n> lamps;
    std::cout << lamps.size();
}

#include <bitset>
#include <iostream>
int main() {
    std::bitset<8> lamps;
    std::cout << "lit lamps, wrong measure " << lamps.size() << '\n';
    std::cout << "lit lamps, correct measure " << lamps.count() << '\n';
}

lit lamps, wrong measure 8
lit lamps, correct measure 0

6
010100
011001
001101

001101

#include <bitset>
#include <iostream>
#include <string>
using namespace std;
int main() {
    int n; string a, t, m;
    cin >> n >> a >> t >> m;
    // Find the required presses, then check the stencil permissions.
}

8 2

// Read n and j. Print the matching bit index.

5 1
00100
01100
00100

// Shift a copy of the hole mask, then check required presses.

Next, inspect every operation and its cost.