여기선 정수의 산술경계 점검만을 다룹니다.

경계점검이란 간단한 예로 x를 부호없는 정수라하면 if ( 10 <= x && x <= 20 )과 같은 것들을 말합니다.

이는 if ( x-10 <= 10 )로 단축될 수 있죠. (이는 if ( x <= 20 )와는 다른 표기입니다.)

x가 11일때 x-10: 1

x가 10일때 x-10: 0

x가  9일때 x-10: 0xFFFFFFFFFFFFFFFF

이렇게 되니깐요.

(저자는 비교 후 분기(compare-branch) 또는 비교 후 트랩(compare-trap) 명령만 관여한다는 점, 수량 인덱싱에서 배열 접근 주소 계산에 필요할 수 있다는 점에서 위 조건문보다 효율적이라고 주장하고있습니다.)

보통은 점검하는 경계가 넓을 수록 후자가 유리하겠고, 좁을 수록 전자가 유리하겠죠.

if ( a <= x && x <= b )와 같은 경우엔 a <= b가 보장된 경우엔 if ( x - a <= b - a )로 대체될 수 있겠죠

정리하면 a,b,x의 부호가 있든 없든 다음이 성립합니다. 물론 비교연산은 부호없는 연산이여야합니다.

a <= b -> if ( a <= x && x <= b )   == if ( x - a <= b - a ) == if ( b - x <= b - a )

a <= b -> if ( a <= x && x <   b )   == if ( x - a <  b - a )

a <= b -> if ( a <   x && x <= b )   == if ( b - x < b - a )

a <   b -> if ( a <   x && x <   b )   = = if ( x - a - 1 < b - a - 1) == if ( b - x - 1 < b - a - 1 )

-------

모호한 비트경계에 대하여

if ( ( a <= x && x <= b ) &&

     ( c <= y && y <= d )   )

와 같은 경우엔 산술적으론 if ( a + c <= x + y && x + y <= b + d )로 

바꾸어 쓸 수 있지만, 부호없는 정수일 경우 a + c가 넘치면(overflow) 사용될 수 없는 구문입니다.

또한 ( c <= x <= d ) ( a<= y<=b)와 같은 연산이 될 수 있어 경계가 정확하지않은 방법이니

주위를 요구합니다.

이 같은 경우엔 경계를 나누어야계산이 가능합니다.

a+c가 넘치지 않고, b+d가 넘친다면 0 <= x + y <= 2**32-1, 그렇지 않다면 a+c<=x+y<=b+d

a-d<0이고, b-c>=0이면 0<=x-y<=2**32-1, 그렇지 않다면 a-d<=x-y<=b-c

로 경우를 나누어야합니다.(&&생략, **연산은 제곱연산과 같습니다.)

-------

비트연산으로 모호한 경계점검하기

x^y <= x|y, x&y<=x===y (===연산은 상태가 같은 비트만 켜는 연산입니다. ~(x^y))

max(x,y)<=x|y, min(x,y)>=x&y는 항상 성립하는 부등식입니다.

또한 ~x == 2**32-1-x도 성립하죠

위 표현을 미루어 볼때 a,b,c,d,x,y연산은

max(a,c) <= x|y <= b+d

0 <= x&y <= min(b,d) (책에 나와있는데로 그대로 쓰긴 썼는데 a와 c에 값에 영향을 안받네요.)

0 <= x^y <= b+d

로 쓸 수 있습니다.

(~b <= ~x <= ~a) && (~d <= ~y <= ~c) 같은표현도 가능합니다.

다음번엔 popcount, nlz에 대하여 알아봅시다.

언제가 될진 모르겠네요