반응형

2. 기초

반응형

한 워드의 제일 오른쪽 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 = xy

¬(xy) = ¬xy= 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 | (((xr) >> 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)

반응형

이 글을 공유하기

댓글

Designed by JB FACTORY