1283. Sixty-Four Flags in One Word
Sixty-four flags, numbered 0 to 63, all start off. They are held in ONE integer,
flag i in bit i. Answer q instructions:
set i turn flag i on
clear i turn flag i off
flip i invert flag i
test i print 1 if flag i is on, 0 otherwise
count print how many flags are on
set 0, test 0, set 63, test 63, count, test 1 -> 1, 1, 2, 0
## What most people try first
An array of 64 booleans, which is correct, obvious, and the right choice when
clarity matters more than anything else. A single word is the right choice when
the whole flag set has to be copied, compared, hashed or stored as one value,
which is what a packed representation buys: == compares all 64 flags in one
instruction, and count is one popcount.
The instinct that causes trouble is writing 1 << i and moving on.
## The four operations
set i w |= (1 << i)
clear i w &= ~(1 << i)
flip i w ^= (1 << i)
test i (w >> i) & 1
set is idempotent, because OR with a bit already present changes nothing.
clear is idempotent for the same reason in reverse. flip is NOT idempotent,
and doing it twice restores the original, which is the property #1269 uses.
test could also be written (w & (1 << i)) != 0. Both are fine; what is not
fine is w & (1 << i) used directly as the answer, which prints 2^i instead
of 1.
## The shift is where every language disagrees
1 << i with i up to 63 is wrong in four of the five languages, each
differently, and all four were run:
C and C++ 1 << 63 undefined: the literal 1 is an int, and shifting an int
by 63 is past its width
Java 1 << 63 silently uses i mod 32, so 1 << 63 equals 1 << 31
JavaScript 1 << 63 evaluates to -2147483648, and 1 << 32 evaluates to 1
Python 1 << 63 correct, because its integers have no width
The fixes are 1ULL << i in C and C++, 1L << i in Java, and BigInt in
JavaScript with 1n << BigInt(i). This is the hazard #1297 exists to teach,
and it is unavoidable here because the problem genuinely needs bit 63.
## Counting the set flags
count is popcount, which #1246 computes with Kernighan's loop,
while (w) { w &= w - 1; c++; }, taking as many steps as there are flags on.
__builtin_popcountll in C and C++ and Long.bitCount in Java do it in one
instruction. The reference solutions use the loop so that all five agree without
depending on a builtin.
## Width
Exactly 64 bits, with bit 63 in use. In C and C++ the word is
unsigned long long, which avoids every question about the sign bit; in Java it
is a long, where setting bit 63 makes the value NEGATIVE, and that is harmless
here because the value is never printed or compared by size, only tested bit by
bit and counted. Had the problem asked to print the word, Java and C would
disagree on the sign and the statement would have to pick one.
In JavaScript the word is a BigInt, since bit 63 is far past the 31 value bits
<< offers.
Constraints - `1 ≤ q ≤ 200000` - `0 ≤ i ≤ 63` - every flag starts off
Input
The first line contains an integer q.
Each of the next q lines is set i, clear i, flip i, test i, or the single word count.
Output
Print one integer on its own line for each test and each count, in the order the instructions arrive. A test prints 1 or 0; a count prints how many flags are on. The other instructions print nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.