한 워드의 제일 오른쪽 1비트를 끄는 공식 if not 0-> x & (x-1)
한 워드의 제일 오른쪽 0비트를 켜는 공식 if not x -> x | (x + 1)
후행 1비트들을 끄는 공식 if not x -> x & (x+1)
후행 0비트들을 켜는 공식 if not x -> x | (x - 1)
x의 제일 오른쪽 0비트에 해당하는 비트만 1인 워드를 만드는 공식 if not 0 -> ¬x & (x + 1)
x의 제일 오른쪽 1비트에 해당하는 비트만 0인 워드를 만드는 공식 if not 1 -> ¬x | (x - 1)
x의 후행 0비트들에 해당하는 비트들만 1이고 다른 비트들은 0인 워드를 만드는 공식 if not 0 -> ¬x & (x - 1)
x의 후행 1비트들에 해당하는 비트들만 0이고 다른 비트들은 1인 워드를 만드는 공식 if not 1 -> ¬x | (x + 1)
제일 오른쪽 1비트만 남겨두는 공식 if not 0 -> x & (-x)
x의 제일 오른쪽 1비트와 후행 0비트들에 해당하는 비트들만 1인 워드를 만드는 공식 if not 1 -> x ⊕ (x-1)
x의 제일 오른쪽 0비트와 후행 1비트들에 해당하는 비트들만 1인 워드를 만드는 공식 if not 1 -> x ⊕ (x+1)
제일 오른쪽의 연속된 1비트들의 비트열을 끄는 공식 if not 0 -> ( (x | (x-1) ) + 1 ) & x )
확장된 드모르간의 법칙
¬(x+1) = ¬x - 1
¬(x-1) = ¬x + 1
¬-x = x - 1
¬(x⊕y) = ¬x⊕y = x≡y
¬(x≡y) = ¬x≡y= x⊕y
¬(x+y) = ¬x-y
¬(x-y) = ¬x+y
워드를 워드로 사상하는 함수를 워드 병렬적 더하기, 빼기, 논리곱, 논리합, 부정 명령들로 구현하기 위한 필요충분조건은 결과의 각 비트가 각 입력 피연산자의 해당 비트 및 그 오른쪽 비트들에만 의존한다는 것이다.(우에서 좌로 계산 가능성 판정)
r2 = x2 | (x0 & y1) => 결과의 비트2는 입력 피연산자들의 비트2와 그 오른쪽 비트들의 함수이므로, 결과의 비트2는 '우에서 좌로 계산 가능'
주어진 크기의 모든 부분집합을 나열한다고 하자. 만일 부분집합에 해당하는 비트열을, 그것을 하나의 정수로 해석한 수와 1비트 개수가 같은 수들 중 그 수 다음으로 큰 수로 사상하는 함수가 있다면 그런 작업을 손쉽게 수행할 수 있다.
s <- x & -x
r <- s + x
y <- r | (((x⊕r) >> 2) ÷ s)
a. -x = ¬x + 1
b. = ¬(x-1)
c. ¬x = -x - 1
d. -¬x = x + 1
e. ¬-x = x - 1
f. x + y = x - ¬y - 1
g. = (x⊕y) + 2(x&y)
h. = (x | y) + (x&y)
i. = 2(x|y) - (x⊕y)
j. x - y = x + ¬y + 1
k. = (x⊕y) - 2(¬x&y)
l. = (x&¬y) - (¬x&y)
m. = 2(x&¬y) - (x⊕y)
n. x⊕y = (x|y) - (x&y)
o. x&¬y = (x|y) - y
p. = x - (x&y)
q. ¬(x-y) = y - x - 1
r. = ¬x + y
s. x ≡ y = (x&y) - (x|y) -1
t. = (x&y) + ¬(x|y)
u. x | y = (x&¬y) + y
v. x & y = (¬x | y) - ¬x
(x⊕y) ≤ (x|y)
(x&y) ≤ (x≡y)
(x|y) ≥ max(x,y)
(x&y) ≤ min(x,y)
(x|y) ≤ (x+y), 덧셈이 넘치지 않으면
(x|y) > (x+y), 덧셈이 넘치면
|x-y| ≤ (x⊕y)
