Bit-String Flicking

From helloboyxxx

Definition

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

Bitwise Operators

not (~ or ¬), and (&), or (|), and xor (⊕)

not就是反着来，0变成1，1变成0
e.g. ~100101 = 011010

and就是看两个bit是不是相同的，相同的就是相同的数，不相同就是0
(0 and 0 = 0; 1 and 1 = 0; 1 and 0 = 0; 0 and 1 = 0)
e.g. 1011011 and 011001 = 001001

or就是看两个bit里面有没有1，有就是1，没有就是0
e.g. 1011011 or 011001 = 111011

xor也是看两个bit是不是相同的，相同就是0，不同就是1
e.g. 1011011 xor 011001 = 110010

Shift Operators

LSHIFT-x and RSHIFT-x

1101101

1101101

LSHIFT-3 x 1101101
1101101
1011010
0110100
1101000

RSHIFT-3 x 11011010
11011010
01101101
00110110
00011011

LCIRC-x 和 RCIRC-x

1101101

1101101
1110110
0111011
1011101

NOT > SHIFT and CIRC > AND > XOR > OR

Boolean Algebra

xnor = not xor
~x = not x
xor = ⊕
xnor = ⊙

Laws

 交换律 x + y = y + x x・y = y・x 结合律 (x + y) + z = x + (y + z) x・(y・z) = (x・y)・z 幂等律 x + x = x x・x = x Annihilator Law x + 1 = 1 x・0 = 0 同一律 x + 0 = x x・1 = x 补余律 x + ~x = 1 x・~x = 0 吸收率 x + xy = x x + ~xy = x + y x・(x + y) = x 分配律 x・(y + z) = xy + xz (x + y)・(p + q) = xp + xq + yp + yq (x + y)(x + z)=x + yz 德摩根定律 ~(x + y) = ~x・~y ~(x・y} = ~x + ~y 双重否定律 ~~x = x XOR 和 XNOR 关系 x ⊙ y = ~(x ⊕ y)= x ⊕ ~y =~x ⊕ y

解释

1. 交换律——类似于加减乘除
2. 结合律——类似于加减乘除
3. 幂等律——x and x = x; x or x = x
4. Annihilator Law——x or 1 = 1; x and 0 = 0
5. 同一律——x or 0 = 0; x and 1 = x
6. 补余律——x or not x = 1(if x = 0, not x = 1; if x = 1, not x = 0); x and not x = 0
7. 吸收率——x + xy = x(1 + y) = 1(because 1 + y ≥ 1); (x + y)(x + z) = x・x + x・z + x・y + y・z = x + y・z(x(1 + y + z) = 1)
8. 德摩根定律——可以通过列表证明(不严谨);
严谨证明：
9. not not x = x
10. by definition, xnor is not xor;

Problems

1. Evaluate the following expression:
(0101110 AND NOT 110110 OR (LSHIFT-3 101010))
2. Evaluate the following expression:
(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))
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
4. Evaluate the following expression:
((RCIRC-14 (LCIRC-23 01101)) | (LSHIFT-1 10011) & (RSHIFT-2 10111))
5. Simplify the following expression as much as possible:

Solutions

1. The expression evaluates as follows:
(0101110 AND 001001 OR (LSHIFT-3 101010))
(001000 OR (LSHIFT-3 101010))
(001000 OR 010000)
011000
2. The expression evaluates as follows, starting at the innermost parentheses:
(RCIRC-2 01101) => 01011
(LCIRC-4 01011) => 10101
(RSHIFT-1 10101) = 01010
3. 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 000, where * is an “I-don’t-care”. The four possible values of x are: 00000, 00001, 00100 and 00101.
4. 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
5.
6.