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
操作和名字一样,向左或者向右移动一串bits

直接上例子:
1101101
如果是LSHIFT-3 x 那就是向左移动三位
1101101
然后标红的1(也就是左往右第四个数字)变成了第一个数字。对的没错前面的三个数字就消失了,然后再在1101后面补上三个0(可以理解为消失的数字变成了0出现在了后面),变成1101000

动态演示(左移):
LSHIFT-3 x 1101101
1101101
1011010
0110100
1101000

右移也是一样的,就是往右移动,在前面补0
动态演示(右移):
RSHIFT-3 x 11011010
11011010
01101101
00110110
00011011

现在还有两个操作:
LCIRC-x 和 RCIRC-x
那个CIRC就是circulation (循环)的意思
那其实就是说在移动的时候,前面或者后面 补充的不是0,而是消失的数字

再举例子:
1101101
如果是RCIRC-3x,那么,往右移动的时候,最右边的数字就移到了最左边
1101101
1110110
0111011
1011101
由于左移是一样的操作,在此不多bb,不懂的私聊作者。

最后注意优先级:
NOT > SHIFT and CIRC > AND > XOR > OR
优先级越高,越先进行运算


Boolean Algebra

Background

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:
  6. boolean algebra problem 6

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. boolean algebra solution 5
6. boolean algebra solution 6

注:如果文中有什么问题,欢迎在评论区指出;有不懂的也可以在评论区提问哦!