Difference between revisions of "Bit-String Flicking"

From ACSL Category Descriptions
Jump to navigation Jump to search
(37 intermediate revisions by 4 users not shown)
Line 1: Line 1:
videos:
https://www.youtube.com/watch?v=XNBcO25mgCw


https://www.youtube.com/watch?v=IeMsD3harrE (Basic)
Bit strings (strings of binary digits) are frequently manipulated bit-by-bit using the logical operators  '''not''', '''and''', '''or''', and '''xor'''. Bits strings are manipulated as a unit using '''shift''' and '''circulate''' operators. The bits on the left are called the ''most significant bits'' and those on the right are the ''least significant bits''.  
https://www.youtube.com/watch?v=jbKw8oYJPs4 (Advanced)


Most high-level languages (e.g., Python, Java, C++), support bit-string operations. Programmers typically use bit strings to maintain a set of flags.  Suppose that a program supports 8 options, each of which can be either “on” or “off”.  One could maintain this information using an array of size 8, or one could use a single variable (if it is internally stored using at least 8 bits or 1 byte, which is usually the case) and represent each option with a single bit.  In addition to saving space, the program is often cleaner if a single variable is involved rather than an array.  Bits strings are often used to maintain a set where values are either in the set or not. Shifting of bits is also used to multiply or divide by powers of 2.


Bit-String Flicking
Mastering this topic is essential for systems programming, programming in assembly language, optimizing code, and hardware design.


Bit strings (strings of binary digits) are frequently manipulated using logical operators, shifts, and circulates.  Mastering this topic is essential for systems programming, programming in assembly language, and optimizing code. 
== Operators==


A typical use of bit strings is to maintain a set of flags.  Suppose that associated with a data structure in a program, there are 8 options each of which can be either “on” or “off”.  One could maintain this information using an array of size 8, or one could use a single variable (if it is internally stored using 8 bits or 1 byte, which is usually the case) and use 8 bits to record each option.  In addition to saving space, the program is often cleaner if a single variable is involved rather than an array.  Incidentally, bit strings are usually used to maintain a set where values are either in the set or not.  Many languages such as C++ and Python also support bit-wise operators.
=== Bitwise Operators ===


The logical operators which will be used are: AND (&), OR (|), XOR (), and NOT (~). These operators examine the operand(s) on a bit by bit basis.  For example, (10110 AND 01111) has a value of 00110.  The AND, OR, and XOR are binary operators; the NOT is a unary operator.  The category description of Boolean Algebra/Digital Electronics has a complete description of each logical function. The following chart summarizes this information:
The logical operators are  '''not''' (~ or $\neg$), '''and''' (&), '''or''' (|), and '''xor''' ($\oplus$). These operators should be familiar to ACSL students from the [[Boolean Algebra]] and [[Digital Electronics]] categories.


p
* '''not''' is a unary operator that performs logical negation on each bit. Bits that are 0 become 1, and those that are 1 become 0. For example: ~101110 has a value of 010001.
q
p AND q
p OR q
p XOR q
NOT p
0
0
0
0
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0


Logical shifts (LSHIFT-x and RSHIFT-x) “ripple” the bit string x positions in the indicated directionBits shifted out are lost; zeros are shifted in at the other end. Circulates (RCIRC-x and LCIRC-x) “ripple” the bit string x positions in the specified direction. As each bit is shifted out one end, it is shifted in at the other end.  Thus, for this category, the size of a bit string is fixed; it cannot be lengthened or shortened by any of the logical operators, shifts, or circulates.  If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length. The following table gives some examples of these operations:
* '''and''' is a binary operator that performs the logical '''and''' of each bit in each of its operandsThe '''and''' of two values is 1 only if both values are 1. For example, '''1011011 and 011001''' has a value of '''001001'''. The '''and''' function is often used to isolate the value of a bit in a bit-string or to clear the value of a bit in a bit-string.


p
* '''or''' is a binary operator that performs the logical '''or''' of each bit in each of its operands. The '''or''' of two values is 1 only if one or both values are 1. For example, '''1011011 or 011001''' has a value of '''111011'''. The '''or''' function is often use to force the value of a bit in a bit-string to be 1, if it isn't already.
LSHIFT-2 p
RSHIFT-2 p
LCIRC-3 p
RCIRC-3 p
01101
10100
00011
01011
10101
10
00
00
01
01
1110
1000
0011
0111
1101
1011011
1101100
0010110
1011101
0111011


The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR. In other words, all unary operators are performed on a single operator first. Operators with equal precedence are evaluated left to right; all operators bind from right to left.
* '''xor''' is a binary operator that performs the logical '''xor''' of each bit in each of its operands. The '''xor''' of two values is 1 if the values are different and 0 if they are the same. For example, 1011011 xor 011001 = 110010. The '''xor''' function is often used to change the value of a particular bit.


References
All binary operators (and, or, or xor) must operate on bit-strings that are of
the same length. If the operands are not the same
length, the shorter one is padded with 0's on the left as needed. For
example, '''11010 and 1110''' would have value of '''11010 and 01110 = 01010'''.


This topic assumes some previous background in the basic operators using in Boolean algebra (AND, OR, NOT, and XOR).  For an explanation of bit-wise operators that can be used in various programming languages, go to https://code.tutsplus.com/articles/understanding-bitwise-operators--active-11301.  Many other explanations directly related to this topic in video or .pdf format can be found by Google-ing “bit string flicking”.
The following table summarizes the operators:


Sample Problems
::{| class="wikitable" style="text-align: center"
|-
!<math>x</math>
!<math>y</math>
! '''not''' <math>x</math>
!<math>x</math> '''and''' <math>y</math>
!<math>x</math> '''or''' <math>y</math>
!<math>x</math> '''xor''' <math>y</math>
|-
!0
!0
| 1
| 0
| 0
| 0
|-
!0
!1
| 1
| 0
| 1
| 1
|-
!1
!0
| 0
| 0
| 1
| 1
|-
!1
!1
| 0
| 1
| 1
| 0
|}


Evaluate the following expression:
=== Shift Operators ===
 
Logical shifts (LSHIFT-x and RSHIFT-x) “ripple” the bit-string x positions in the indicated direction, either to the left or to the right.  Bits shifted out are lost; zeros are shifted in at the other end. 
 
Circulates (RCIRC-x and LCIRC-x) “ripple” the bit string x positions in the indicated direction.  As each bit is shifted out one end, it is shifted in at the other end. The effect of this is that the bits remain in the same order on the other side of the string.
 
The size of a bit-string  does not change with shifts, or circulates.  If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length. 
 
The following table gives some examples of these operations:
 
::{| class="wikitable" style="text-align: right"
|-
!x
!(LSHIFT-2 x)
!(RSHIFT-3 x)
!(LCIRC-3 x)
!(RCIRC-1 x)
|-
!01101
| 10100
| 00001
| 01011
| 10110
|-
!10
| 00
| 00
| 01
| 01
|-
!1110
| 1000
| 0001
| 0111
| 0111
|-
!1011011
| 1101100
| 0001011
| 1011101
| 1101101
|}
 
=== Order of Precedence ===
 
The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR.  In other words, all unary operators are performed on a single operator first.  Operators with equal precedence are evaluated left to right; all unary  operators bind from right to left.
 
== Sample Problems ==
 
=== Problem 1 ===


    (RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))
Evaluate the following expression:
:(0101110 AND NOT 110110 OR (LSHIFT-3 101010))


'''Solution:'''
The expression evaluates as follows:
The expression evaluates as follows:
(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))
:(0101110 AND '''001001''' OR (LSHIFT-3 101010))
= (RSHIFT-1 (LCIRC-4 01011))
:('''001000''' OR (LSHIFT-3 101010))
= (RSHIFT-1 10101) = 01010
:(001000 OR '''010000''')
:'''011000'''


=== Problem 2 ===


Evaluate the following expression:
:(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))
'''Solution:'''
The expression evaluates as follows, starting at the innermost parentheses:
:(RCIRC-2 01101) => 01011
:(LCIRC-4 01011) => 10101
:(RSHIFT-1 10101) = 01010
=== Problem 3 ===


List all possible values of x (5 bits long) that solve the following equation.
List all possible values of x (5 bits long) that solve the following equation.
:(LSHIFT-1 (10110 XOR (RCIRC-3 x) AND 11011)) = 01100


    (LSHIFT-1 (10110 XOR
'''Solution:'''
    (RCIRC-3 x) AND 11011)) = 01100
 
Since x is a string 5 bits long, represent it by abcde.  (RCIRC-3 x) is cdeab which, when ANDed with 11011 gives cd0ab.  This is XORed to 10110 to yield Cd1Ab (the capital letter is the NOT of its lower case).
Since x is a string 5 bits long, represent it by abcde.  (RCIRC-3 x) is cdeab which, when ANDed with 11011 gives cd0ab.  This is XORed to 10110 to yield Cd1Ab (the capital letter is the NOT of its lower case).
Now, (LSHIFT-1 Cd1Ab) = d1Ab0 which has a value of 01100, we must have d=0, A=1 (hence a=0), b=0.  Thus, the solution must be in the form 00*0*, where * is an “I-don’t-care”.  The four possible values of x are: 00000, 00001, 00100 and 00101.
Now, (LSHIFT-1 Cd1Ab) = d1Ab0 which has a value of 01100, we must have d=0, A=1 (hence a=0), b=0.  Thus, the solution must be in the form 00*0*, where * is an “I-don’t-care”.  The four possible values of x are: 00000, 00001, 00100 and 00101.


=== Problem 4 ===
Evaluate the following expression:
: ((RCIRC-14 (LCIRC-23 01101)) | (LSHIFT-1 10011) & (RSHIFT-2 10111))
'''Solution:'''
The problem can be rewritten as
: A | B & C
The AND has higher precedence than the OR. 


The evaluation of expression A can be done in a straightforward way:  (LCIRC-23 01101) is the same as (LCIRC-3 01101) which has a value of 01011, and (RCIRC-14 01011) is the same as (RCIRC-4 01011) which has a value of 10110. Another strategy is to offset the left and right circulates.  So, ((RCIRC-14 (LCIRC-23 01101)) has the same value as (LCIRC-9 01101), which has the same value as (LCIRC-4 01101) which is also 11010.


Evaluate the following expression:
Expressions B and C are pretty easy to evaluate:
:B = (LSHIFT-1 10011) = 00110
:C = (RSHIFT-2 10111) = 00101
 
The expression becomes
: A | B & C = 10110 | 00110 & 00101 = 10110 | 00100 = 10110
 
== Video Resources ==
 
The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.
 
{|
|-
| <youtube width="300" height="180">https://youtu.be/IeMsD3harrE</youtube>
| [https://youtu.be/IeMsD3harrE ''Bit String Flicking (Intro)'' ('''CalculusNguyenify''')]
 
A great two-part tutorial on this ACSL category. Part 1 covers bitwise operations AND, OR, NOT, and XOR.


    ((RCIRC-14 (LCIRC-23 01101)) |
|-
    (LSHIFT-1 10011) & (RSHIFT-2 10111))
| <youtube width="300" height="180">https://youtu.be/jbKw8oYJPs4</youtube>
| [https://youtu.be/jbKw8oYJPs4 ''Bit String Flicking Shifts and Circs'' ('''CalculusNguyenify''')]


The rules of hierarchy must be followed carefully:
Part 2 covers logical shifts and circulate operations.
A = (RCIRC-14 (LCIRC-23 01101))
    = (LCIRC-9 01101) = (LCIRC-4 01101)
    = 10110
B = (LSHIFT-1 10011) = 00110
C = (RSHIFT-2 10111) = 00101
D = B & C = 00110 AND 00101 = 00100
Final answer is 10110 OR 00100 = 10110.




|-
| <youtube width="300" height="180">https://youtu.be/XNBcO25mgCw</youtube>
| [https://youtu.be/XNBcO25mgCw ''Bit String Flicking'' ('''Tangerine Code''')]


Find all possible values of x for which the following expression has a value of 10100.
Shows the solution to the problem: (RSHIFT-3 (LCIRC-2 (NOT 10110)))


    (LSHIFT-2 (RCIRC-3 (NOT x)))
|-
| <youtube width="300" height="180">https://youtu.be/8J9AdxU5CW8</youtube>
| [https://youtu.be/8J9AdxU5CW8 ''Bit String Flicking by Ravi Yeluru'' ('''hemsra''')]


Let x=abcde and (NOT x)=ABCDE.  Substitute into the expression:
Walks through two problems from the Junior Division.
      (RCIRC-3 ABCDE) = CDEAB  and
      (LSHIFT-2 CDEAB) = EAB00.
Since EAB00 = 10100, NOT E = 1, NOT A = 0, and NOT B = 1.  Therefore, the string that matches is 10**0.  This answer is valid.


|-
| <youtube width="300" height="180">https://youtu.be/aa_lQ8gft60</youtube>
| [https://youtu.be/aa_lQ8gft60 ''ACSL BitString Flicking Contest 2 Worksheet 1'' ('''misterminich''')]


Solves a handful of problems given in previous years at the Intermediate Division level.


Evaluate the following expression:
|}


(NOT LSHIFT-1 10110 XOR RSHIFT-2 NOT 01101 AND LCIRC-1 RCIRC-3 10110 OR LCIRC-4 RCIRC-2 00110)




<!--
{|
|-
| <youtube width="300" height="180">URL</youtube>
| [URL ''TITLE'' ('''AUTHOR''')]


Without parentheses, bind from right to left.
DESCRIPTION
NOT LSHIFT-1 10110  = 10011
|}
RSHIFT-2 NOT 01101 = 00100
-->
LCIRC-1 RCIRC-3 10110 = 10101
LCIRC-4 RCIRC-2 00110 = 11000
10011 XOR 00100 AND 10101 OR 11000
= 10011 XOR 00100 OR 11000
= 10111 OR 11000                                        = 11111.

Revision as of 18:35, 9 January 2019

Bit strings (strings of binary digits) are frequently manipulated bit-by-bit using the logical operators not, and, or, and xor. Bits strings are manipulated as a unit using shift and circulate operators. The bits on the left are called the most significant bits and those on the right are the least significant bits.

Most high-level languages (e.g., Python, Java, C++), support bit-string operations. Programmers typically use bit strings to maintain a set of flags. Suppose that a program supports 8 options, each of which can be either “on” or “off”. One could maintain this information using an array of size 8, or one could use a single variable (if it is internally stored using at least 8 bits or 1 byte, which is usually the case) and represent each option with a single bit. In addition to saving space, the program is often cleaner if a single variable is involved rather than an array. Bits strings are often used to maintain a set where values are either in the set or not. Shifting of bits is also used to multiply or divide by powers of 2.

Mastering this topic is essential for systems programming, programming in assembly language, optimizing code, and hardware design.

Operators

Bitwise Operators

The logical operators are not (~ or $\neg$), and (&), or (|), and xor ($\oplus$). These operators should be familiar to ACSL students from the Boolean Algebra and Digital Electronics categories.

  • not is a unary operator that performs logical negation on each bit. Bits that are 0 become 1, and those that are 1 become 0. For example: ~101110 has a value of 010001.
  • and is a binary operator that performs the logical and of each bit in each of its operands. The and of two values is 1 only if both values are 1. For example, 1011011 and 011001 has a value of 001001. The and function is often used to isolate the value of a bit in a bit-string or to clear the value of a bit in a bit-string.
  • or is a binary operator that performs the logical or of each bit in each of its operands. The or of two values is 1 only if one or both values are 1. For example, 1011011 or 011001 has a value of 111011. The or function is often use to force the value of a bit in a bit-string to be 1, if it isn't already.
  • xor is a binary operator that performs the logical xor of each bit in each of its operands. The xor of two values is 1 if the values are different and 0 if they are the same. For example, 1011011 xor 011001 = 110010. The xor function is often used to change the value of a particular bit.

All binary operators (and, or, or xor) must operate on bit-strings that are of the same length. If the operands are not the same length, the shorter one is padded with 0's on the left as needed. For example, 11010 and 1110 would have value of 11010 and 01110 = 01010.

The following table summarizes the operators:

[math]x[/math] [math]y[/math] not [math]x[/math] [math]x[/math] and [math]y[/math] [math]x[/math] or [math]y[/math] [math]x[/math] xor [math]y[/math]
0 0 1 0 0 0
0 1 1 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0

Shift Operators

Logical shifts (LSHIFT-x and RSHIFT-x) “ripple” the bit-string x positions in the indicated direction, either to the left or to the right. Bits shifted out are lost; zeros are shifted in at the other end.

Circulates (RCIRC-x and LCIRC-x) “ripple” the bit string x positions in the indicated direction. As each bit is shifted out one end, it is shifted in at the other end. The effect of this is that the bits remain in the same order on the other side of the string.

The size of a bit-string does not change with shifts, or circulates. If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length.

The following table gives some examples of these operations:

x (LSHIFT-2 x) (RSHIFT-3 x) (LCIRC-3 x) (RCIRC-1 x)
01101 10100 00001 01011 10110
10 00 00 01 01
1110 1000 0001 0111 0111
1011011 1101100 0001011 1011101 1101101

Order of Precedence

The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR. In other words, all unary operators are performed on a single operator first. Operators with equal precedence are evaluated left to right; all unary operators bind from right to left.

Sample Problems

Problem 1

Evaluate the following expression:

(0101110 AND NOT 110110 OR (LSHIFT-3 101010))

Solution: The expression evaluates as follows:

(0101110 AND 001001 OR (LSHIFT-3 101010))
(001000 OR (LSHIFT-3 101010))
(001000 OR 010000)
011000

Problem 2

Evaluate the following expression:

(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))

Solution: The expression evaluates as follows, starting at the innermost parentheses:

(RCIRC-2 01101) => 01011
(LCIRC-4 01011) => 10101
(RSHIFT-1 10101) = 01010

Problem 3

List all possible values of x (5 bits long) that solve the following equation.

(LSHIFT-1 (10110 XOR (RCIRC-3 x) AND 11011)) = 01100

Solution: Since x is a string 5 bits long, represent it by abcde. (RCIRC-3 x) is cdeab which, when ANDed with 11011 gives cd0ab. This is XORed to 10110 to yield Cd1Ab (the capital letter is the NOT of its lower case). Now, (LSHIFT-1 Cd1Ab) = d1Ab0 which has a value of 01100, we must have d=0, A=1 (hence a=0), b=0. Thus, the solution must be in the form 00*0*, where * is an “I-don’t-care”. The four possible values of x are: 00000, 00001, 00100 and 00101.

Problem 4

Evaluate the following expression:

((RCIRC-14 (LCIRC-23 01101)) | (LSHIFT-1 10011) & (RSHIFT-2 10111))

Solution: The problem can be rewritten as

A | B & C

The AND has higher precedence than the OR.

The evaluation of expression A can be done in a straightforward way: (LCIRC-23 01101) is the same as (LCIRC-3 01101) which has a value of 01011, and (RCIRC-14 01011) is the same as (RCIRC-4 01011) which has a value of 10110. Another strategy is to offset the left and right circulates. So, ((RCIRC-14 (LCIRC-23 01101)) has the same value as (LCIRC-9 01101), which has the same value as (LCIRC-4 01101) which is also 11010.

Expressions B and C are pretty easy to evaluate:

B = (LSHIFT-1 10011) = 00110
C = (RSHIFT-2 10111) = 00101

The expression becomes

A | B & C = 10110 | 00110 & 00101 = 10110 | 00100 = 10110

Video Resources

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

Bit String Flicking (Intro) (CalculusNguyenify)

A great two-part tutorial on this ACSL category. Part 1 covers bitwise operations AND, OR, NOT, and XOR.

Bit String Flicking Shifts and Circs (CalculusNguyenify)

Part 2 covers logical shifts and circulate operations.


Bit String Flicking (Tangerine Code)

Shows the solution to the problem: (RSHIFT-3 (LCIRC-2 (NOT 10110)))

Bit String Flicking by Ravi Yeluru (hemsra)

Walks through two problems from the Junior Division.

ACSL BitString Flicking Contest 2 Worksheet 1 (misterminich)

Solves a handful of problems given in previous years at the Intermediate Division level.