Difference between revisions of "Bit-String Flicking"

From ACSL Category Descriptions
Jump to navigation Jump to search
Line 6: Line 6:




Bit-String Flicking
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators


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.   
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.   
Line 75: Line 75:
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.   
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.   


References
== Sample Problems ==


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”.
Problem: Evalue the following expression:  
 
<syntaxhighlight inline>
Sample Problems
 
Evaluate the following expression:
 
    (RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))
 
The expression evaluates as follows:
(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))
(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))
= (RSHIFT-1 (LCIRC-4 01011))
</syntaxhighlight>
= (RSHIFT-1 10101) = 01010
 
 
 
List all possible values of x (5 bits long) that solve the following equation.
 
    (LSHIFT-1 (10110 XOR
    (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).
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.
 
 
 
Evaluate the following expression:
 
    ((RCIRC-14 (LCIRC-23 01101)) |
    (LSHIFT-1 10011) & (RSHIFT-2 10111))
 
The rules of hierarchy must be followed carefully:
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.
 
 
 
Find all possible values of x for which the following expression has a value of 10100.
 
    (LSHIFT-2 (RCIRC-3 (NOT x)))
 
Let x=abcde and (NOT x)=ABCDE.  Substitute into the expression:
      (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.
 
 
 
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)
 
 
 
Without parentheses, bind from right to left.
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 19:36, 6 August 2018

videos: https://www.youtube.com/watch?v=XNBcO25mgCw

https://www.youtube.com/watch?v=IeMsD3harrE (Basic) https://www.youtube.com/watch?v=jbKw8oYJPs4 (Advanced)


https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

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.

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.

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:

p 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 direction. 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 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:

p 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.

Sample Problems

Problem: Evalue the following expression: (RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))

Retrieved from "http://www.categories.acsl.org/wiki/index.php?title=Bit-String_Flicking&oldid=175"