Helpful Information For Competitive Programming.
Bit strings are essentially just strings of binary digits (so, for example,
011010) that can be manipulated in a variety of ways by operators (see Operators below). They can also be represented by
the binary form of many data types, such as integers, strings, etc.
Most high-level languages support such operations. Bit strings can be used to represent data in the form of binary sets. If you were to have a program with 8 different options that all have the choice of "Yes" or "No", one way to store this information would be with an array of size 8. However, an easier and less space-consuming way would be to use a bit string, with each option choice taking up one bit.
Understanding how bit strings work is very helpful in systems programming, assembly language programming, code optimization, and hardware design.
The order of precedence (the order in which they are executed) for the operators goes as follows:
Continue reading this section for more information on what each of these operators do.
All of these operators (except NOT) are binary operators,
meaning that they must take in two operands, which must be the same length.
If the two bit strings are different lengths,
zeros will be added to the left of the shorter operand until it is the same length
as the other operand. So, for example, if we had the operands
3 zeros would need to be added to
101 to make it
Since not is a unary operator (meaning that it only takes in one operand), this condition does not apply.
All of these operators are also bitwise, meaning that they work bit-by-bit. They do an operation on every single bit of the string individually, not the whole bit string as one.
||Logical negation is performed on each bit in the bit strings. 0s turn into 1s, and vice versa.||
|and||&||A comparison is made between a bit and its corresponding bit (based on position) in the other bit string. If both bits are 1s, then the resultant bit will be a 1; otherwise, it will be 0. This is done for each bit in the bit strings.||
|or|||||Similar to and, bits are compared with the bits in the other bit string. If at least one bit is a 1, then the resultant bit will be a 1. This is done for each bit in the bit strings.||
||Again, this involves bit comparison. If one bit has a value of 0 while the other has a value of 1, then the resultant bit is 1, otherwise it is
Note: There is a shortcut for xor specifically - you can think of it like this:
For each bit, instead of comparing them individually, just look at the bits in the 2nd bit string with a
1. Toggle (perform the NOT operation on) the bits corresponding to those
1s in the first string to get your final bit string.
So for this example, we're toggling
1. After flipping the red bits, we have
$110010$, which is exactly what the answer should be.
This works because of the truth table for XOR:
We can see that the
$X \oplus Y$ bit is equal to
$0$, and equal to
$\neg X$ when
$Y$ is 1.
For more details on truth tables, or if you're confused about what a truth table is, check out our page on Boolean Algebra.
As their name indicates, "shift" operators are unary operators that involve shifting bits around in a bit string. The direction in which they shift as well as how many positions they shift over by varies based on the operator. For the operators in the table below, we will include the abbreviation that we typically use for each operator.
Note that none of these operators change the length of the bit string.
|LSHIFT-x||LS-x||Each bit in the bit string is shifted over by x positions to the left. If its shift causes it to go out of bounds, that bit will be lost ("shifted out"); a
|RSHIFT-x||RS-x||Each bit in the bit string is shifted over by x positions to the right. If its shift causes it to go out of bounds, that bit will be lost ("shifted out"); a
|LCIRC-x||LC-x||Each bit in the bit string is shifted over by x positions to the left. If its shift causes it to go out of bounds, then that bit will circulate to the other end (the right) rather than being lost.||
|RCIRC-x||RC-x||Each bit in the bit string is shifted over by x positions to the right. If its shift causes it to go out of bounds, then that bit will circulate to the other end (the left) rather than being lost.||
So, while SHIFTs may cause there to be different bits, CIRCs only change the order of the existing bits.
Also, because of the way these operators work, you can significantly simplify operations depending on the length of the bit string.
For example, LCIRC-19
10001 is just equivalent to LCIRC-4. This means that we can calculate that the resultant bit string
00011 very quickly.
Here are some sample problems that you can use to practice bit-string flicking. Full solutions are provided.
This requires knowing all of the bit string operators and how they work. Refer to the Operators section if needed.
(Note: This is from North Hollywood ACSL.)
The following solution is broken down into smaller steps to help improve understanding:
(Note: This is from the ACSL Wiki.)
Note that the CIRC operation involves circulating by multiple positions beyond one cycle. However, if you think about it,
LC-5 01101 is just
01101, since one full cycle would have been done. So, accounting for these full cycles,
LC-23 01101 would go through 4 full cycles (since
23 // 5 = 4); thus, it is equivalent to
A similar idea applies to
RC-5 on a 5-bit bit string would just be 1 full cycle that doesn't have any impact on the bit string. So,
RC-14 would go through 2 full cycles (since
14 // 5 = 2); so, it is equal to
RC-4 (for a 5-bit bit string, at least).
Knowing this, we can now reduce our problem to simpler terms and then solve.
( ( RC-14 ( LC-23 01101 ) ) | ( LS-1 10011 ) & ( RS-2 10111 ) )
( ( RC-4 ( LC-3 01101 ) ) | ( LS-1 10011 ) & ( RS-2 10111 ) )
( ( RC-4 01011 ) | ( LS-1 10011 ) & ( RS-2 10111 ) )
( 10110 | ( LS-1 10011 ) & ( RS-2 10111 ) )
( 10110 | 00110 & ( RS-2 10111 ) )
( 10110 | 00110 & 00101 )
( 10110 | 00100 )
Note the precedence in step 5; AND (&) comes before OR (|).
Solving these types of problems take on a different method of solving,
as you are given an equation but not one of the bitstrings, which you then need to solve for. To depict this mystery bitstring, we typically use letters. So, if we had a mystery bitstring that is 5 bits long, then you could display that as
Working with letters for the first time can take a bit of adjusting, since letters are in no way similar to
1. So, please refer to the following table below to understand how calculations work out:
Many of these concepts are ripped straight from the Boolean Algebra page. If you understand those concepts, you understand this.
||A||This is just our way of differentiating between
||a||Similarly, negating the negated version of
||Regardless of what
||a||Since one of the operands is already 0, then whether this operation returns a 0 or 1 all depends on
||1||Regardless of what
Now, using this table, please try the following problems:
(Note: This is from the ACSL Wiki.)
Let's first mark
abcde. Now, we can carry on:
At this point, you can now solve for a few variables.
d correlates with
1 correlates with
1; notice that while variables are not involved, this is a good way to ensure that you correctly evaluated the bit string. (Note that it is also possible to have no answers, so if you're 100% sure you did everything correctly but two constants don't line up, there are no solutions. Typically ACSL has solutions, so you probably won't need to worry about this.)
A is equal to 1; so,
a is equal to
b is equal to
0, and the final
0 correlates with 0.
a = 0,
b = 0, and
d = 0. We don't know about
e, but their values don't actually matter. This is because regardless of what they are, the equation will always be reduced to what we have in Step 4 (the variables are annihilated somewhere along the line).
Thus, our answer is
00*0*, with the
* standing for any value (
1). During the ACSL contest, you should write these solutions out manually (unless noted otherwise) as:
(Note: This is from someone else's Quizlet.)
Again, we will mark
Now, the chances that we calculated this correctly are fairly high since the last two bit pairs match correctly (
E = 1,
A = 0, and
B = 1.
This translates to
a = 1, and
$0$. The values of
d don't matter and thus can either be
So, our answer is
10**0 with the
* standing for any value (
1). Fully written out, this would be:
Authors: Kelly Hong, Raymond Zhao